摘要：研究了基于实际应用背景提炼出的工件加工时间是其开工时间的线性函数的无空闲流水作业排序问题。在机器分别具有某些优势关系的情形下,探讨了目标函数为极小化最大完工时间和极小化总完工时间之和的情况。对于每种情况,分别给出了工件按某种规则排序为最优序的多项式时间算法。

关键词：排序 流水作业 占优机器 依赖于开始时间的加工时间 

单位：广东工业大学管理学院 广东广州510520