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

摘要：

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

关键词：预排序、单台机器排序、标号

所属期刊栏目：12

分类号：O223(运筹学)

在线出版日期：2012-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：256-259