无空闲占优机器的加工时间可变流水作业排序

摘要

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