极小化最大提前完工费用的可中断排序问题  

Preemptive Scheduling to Minimize Maximum Earliness Cost

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

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

出　　处：《运筹学学报》2010年第4期83-91,100,共10页Operations Research Transactions

摘　　要：讨论了带截止期限的n个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为O(n^2)的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为O(n^2)的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.This paper discusses the problem that n jobs with their own deadlines and precedence constraints have to be processed on a single machine considering the idle insert.The objective is to find a preemptive job sequence and determine jobs＇ starting times so as to minimize the maximum earliness cost.Firstly,we consider two special cases：（1） common deadline and precedence constraints;（2） arbitrary deadlines and no precedence constraint.The O（n^2） algorithms are provided respectively.Then the general case of arbitrary deadlines and precedence constraints is considered based on the two special cases,and an O（n^2） algorithm is developed too.Since tardy jobs are prohibited, it＇s possible that there is no feasible sequence for the problem.We consider the feasibility primarily.

关 键 词：运筹学 单机排序 截止期限 优先约束 空闲时间 最大提前完工费用 

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