一类带特殊序约束的三台机流水作业排序问题

摘要

研究单位工件、有序约束的三台机流水作业排序问题,目标是极小化工件的最大完工时间。在序约束关系形成最长链图结构的情形下,首先对其顶点(工件)集进行自然分层,然后在相邻顶点层之间尽可能寻找一对相容工件,最后将每一层工件在三台流水作业机上进行最优排序,并由一对相容工件衔接相邻层,得到最坏情况界不超过3/2的多项式时间近似算法。通过构造实例进一步证明了界是紧的。