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

Preemptive Scheduling with Deadlines on Single Machine

作　　者：钟雪灵[1] 王国庆[2] 程明宝[3] 

机构地区：[1]广东金融学院计算机系,广州510520 [2]暨南大学管理学院,广州510632 [3]广东工业大学管理学院,广州510520

出　　处：《应用数学学报》2012年第1期108-119,共12页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(71101064);教育部人文社会科学研究项目基金(09YJC630088)资助项目

摘　　要：工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的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.

关 键 词：单机排序 准备时间 强制工期 空闲时间 提前完工时间和 

分 类 号：O223[理学—运筹学与控制论]