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

PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES

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

机构地区：[1]广东金融学院计算机系,广州510520 [2]暨南大学管理学院,广州510632 [3]广东工业大学管理学院,广州510520 [4]华南师范大学南海校区,佛山528225

出　　处：《系统科学与数学》2011年第7期794-803,共10页Journal of Systems Science and Mathematical Sciences

基　　金：教育部人文社会科学研究项目基金(09YJC630088)

摘　　要：讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.This paper discusses the problem that n jobs with their own deadlines have to be processed on identical machines considering the idle insert. The objective is to find a preemp- tive job sequence so as to minimize the total earliness. 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 common deadline is discussed. Since tardy jobs are prohibited, it＇s possible that there is no feasible sequence for the problem. The feasibility is considered primarily. If the problem is feasible, a polynomial time algorithm is developed to achieve optimality.

关 键 词：平行机排序 强制工期 空闲时间 提前完工时间和 

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