单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.

The pre-sequencing of jobs for single machine scheduling problem

In the scheduling problem,in order to find a processing sequence of jobs,sometimes need to renumber the original jobs,i.e.,pre-sequencing them.For example,when using dynamic programming to solve the single machine scheduling problem with precedence constrains,the jobs need to be pre-sequenced such that the sequence number of the predecessor job is less than the sequence number of its successor job and such that some objective function is optimal.For the chain structure precedence constrains,an algorithm is given and proven that the algorithm is optimal.For the tree structure precedence constrains,an algorithm also presented and proved that the algorithm is optimal for some special tree structure precedence constrains.