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

Single Machine Scheduling with Deadlines to Minimize Maximum Earliness

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

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

出　　处：《系统管理学报》2010年第5期584-588,共5页Journal of Systems & Management

摘　　要：讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序。This paper discusses the problem that n jobs with their own deadlines have to be processed on a single machine considering the idle insert.The objective is to find a job sequence and determine jobs＇ starting times so as to minimize the maximum earliness.Since tardy jobs are prohibited,it＇s possible that there is no feasible sequence for the problem.We consider the feasibility primarily.If the problem is feasible,we first pre-determine a sequence and develop an algorithm to compute jobs＇ starting times,and then judge whether it＇s optimal or not.If optimality can＇t be determined directly,a polynomial time algorithm is developed to achieve optimality through attempting to adjust the jobs constantly from the pre-determined sequence initially.

关 键 词：单机排序 强制 空闲时间 最大提前完工时间 

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