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

运筹学学报 ›› 2010, Vol. 14 ›› Issue (4): 83-91.

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

钟雪灵, 王国庆, 程明宝, 李晓春

出版日期:2010-12-15 发布日期:2010-12-15

Preemptive Scheduling to Minimize Maximum Earliness Cost

ZHONG Xue-Ling, WANG Guo-Qing, CHENG Ming-Bao, LI Xiao-Chun

Online:2010-12-15 Published:2010-12-15

摘要/Abstract

摘要： 讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.

Abstract: 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.

钟雪灵, 王国庆, 程明宝, 李晓春. 极小化最大提前完工费用的可中断排序问题[J]. 运筹学学报, 2010, 14(4): 83-91.

ZHONG Xue-Ling, WANG Guo-Qing, CHENG Ming-Bao, LI Xiao-Chun. Preemptive Scheduling to Minimize Maximum Earliness Cost[J]. Operations Research Transactions, 2010, 14(4): 83-91.