极小化最大提前完工时间的两平行机排序问题

Two Identical Machines Scheduling to Minimize Maximum Earliness

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.

This paper discusses the problem that n jobs with their own deadlines have to be processed on two parallel identical machines considering the idle insert,in which the objective is to find a job sequence so as to minimize the maximum earliness.Since tardy jobs are prohibited,it＇s possible that there is no feasible sequence for the problem.We consider the feasibility primarily.We prove that determining the problem＇s feasibility is NP-complete in the ordinary sense through subset sum problem.If the problem is feasible,we also prove the problem is NP-hard in the ordinary sense through partition problem.Finally,we identify the common processing time case by introducing its corresponding polynomial solution.