• 论文 • 上一篇    下一篇

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

钟雪灵1, 王国庆2, 程明宝3, 李晓春4   

  1. 1. 广东金融学院计算机系; 2. 暨南大学管理学院, 3. 广东工业大学 管理学院, 4. 华南师范大学南海校区
  • 收稿日期:2009-03-11 出版日期:2011-07-25 发布日期:2011-09-27

钟雪灵, 王国庆, 程明宝, 李晓春. 带强制工期的可中断平行机排序问题[J]. 系统科学与数学, 2011, 31(7): 794-803.

ZHONG Xueling, WANG Guoqing, CHENG Mingbao, LI Xiaochun. PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES[J]. Journal of Systems Science and Mathematical Sciences, 2011, 31(7): 794-803.

PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES

ZHONG Xueling1, WANG Guoqing2, CHENG Mingbao3, LI Xiaochun4   

  1. 1. Department of Computer, Guangdong University of Finance; 2. Department of Business Administration, Jinan University; 3. School of Management, Guangdong University of Technology; 4. Nanhai Campus, South China Normal University
  • Received:2009-03-11 Online:2011-07-25 Published:2011-09-27
讨论了在$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 preemptive 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.

MR(2010)主题分类: 

()
[1] 王磊,张玉忠,王成飞. 机器具有学习效应的供应链排序问题[J]. 系统科学与数学, 2013, 33(7): 799-806.
[2] 范静. 工件带就绪时间的单机供应链排序问题[J]. 系统科学与数学, 2011, 31(11): 1439-1443.
阅读次数
全文


摘要