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

作     者：钟雪灵 王国庆 王雄志 ZHONG Xueling;WANG Guoqing;WANG Xiongzhi

作者机构：广东金融学院计算机系广东广州510520 暨南大学管理学院广东广州510632 华南农业大学经济管理学院广东广州510642 

出 版 物：《武汉大学学报（工学版）》 (Engineering Journal of Wuhan University)

年 卷 期：2011年第44卷第1期

页      面：133-136页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：广东省自然科学基金项目(编号:8451064201000819) 

主　　题：单机排序 准备时间 强制工期 空闲时间 最大提前完工时间 

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