论文部分内容阅读
本文研究的是同类机具有相同加工时间和工期的排序问题，对下列三种目标函数为极小化加权提前与延误惩罚的模型给出了多项式时间算法。
(1)．Gur Mosheiov和Uri Yovel(2004)［28］研究了同型机环境的P｜dj=d，Pj=1|∑αjEj+βjTj+γd,给出了O(n4)的算法。本文对于两台同类机的情况，即问题Q2 |pj=p；dj=d|l∑n j=1 αjEj+βjTj+γd，将其转化为一个指派问题，并给出了O(n4)的算法。
(2)．对于目标函数中含有延误工件数因子γjUj，本文考虑了机器固定为m台的同类机模型，即Qm|pj=p；dj=d|∑ n j=1 αjEj+βjTj=γjUj。对此问题本文将其转化为一个指派问题，并给出了O((n+2m)4)的算法。
(3)．Kahlbacher和Cheng(1993)[20]对问题P|dj=d|∑wjUj+∑αEj给出了O(n4)的算法。本文考虑了只有两台同型机时的情况，即问题Q2|dj=d|∑n j=1 αEj+βjUj。对于该问题也可以将其转化为一个指派问题，并得到了O(n4)的算法。