带强制工期的可中断单机排序问题

Preemptive Scheduling with Deadlines on Single Machine

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

The scheduling problem with deadlines requires that each job have 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 stored and lead to extra holding cost unavoidably. Based on that, this paper discusses the problem that n jobs with their own release times and deadlines have to be processed on single machine considering the idle insert. The objective is to find a preemptive job sequence so as to minimize the total earliness. The computational complexity is considered firstly, and the problem is proved NP-complete through the induction of even-odd partition problem. Then, the special case of common processing time is discussed. Since tardy jobs are prohibited, it＇s possible that there is no feasible sequence for the problem. We develop a polynomial time algorithm to test feasibility and achieve optimality for the feasible problem.