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

Single machine scheduling problem to minimize maximum earliness

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.基于此,讨论了带准备时间和强制工期的n个工件在单机上加工,在机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,考虑了工件加工时间相等的特殊情形.先讨论问题的可行性,针对可行问题,提出了一个算法在多项式时间内获得最优排序.

The scheduling problem with deadlines requires that each job has to be completed before or on the given due date,namely no tardiness.It can be seen everywhere in practical application.The earliness means the finished jobs need to store and lead to extra holding cost unavoidably.Based on that,this paper discusses the problem that n jobs with ready times and deadlines have to be processed on a single machine.The objective is to find a preemptive job sequence so as to minimize the maximum earliness considering the idle insert.The complexity is considered firstly,and the problem is proved strongly NP-hard through the induction of 3-partition problem.Then,the special case of equal processing time is considered.The feasibility is discussed.If the problem is feasible,a polynomial time algorithm is developed to achieve optimality.