华东师范大学学报(自然科学版) ›› 2007, Vol. 2007 ›› Issue (1): 51-55.

• 数学 • 上一篇    下一篇

带有前后约束的延误排序问题的近似算法

张树霞1,2, 唐国春3   

  1. 1. 华东师范大学 数学系, 上海 200062; 2. 解放军镇江船艇学院 船艇指挥系, 江苏镇江 212003; 3. 上海第二工业大学 管理工程研究所, 上海 201209
  • 收稿日期:2005-08-30 修回日期:2006-03-23 出版日期:2007-01-25 发布日期:2007-01-25
  • 通讯作者: 张树霞

Approximation Algorithm for the Total Tardiness Scheduling(Chinese)

ZHANG Shu-xia1,2, TANG Guo-chun3   

  1. 1. Department of Mathematics, East China Normal University, Shanghai 200062, China; 2. Department of Watercraft Command, Zhenjiang Watercraft College, Zhenjiang 212003, China; 3. Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China
  • Received:2005-08-30 Revised:2006-03-23 Online:2007-01-25 Published:2007-01-25
  • Contact: ZHANG Shu-xia

摘要： 把工件之间不带前后约束的延误排序的后移算法移植到带有前后约束的情况, 提出一个多项式时间的近似算法. 这个算法可以快速地得到这种延误问题的近似解.

关键词: 延误问题, Emmons条件, 前后约束, 近似算法, 延误问题, Emmons条件, 前后约束, 近似算法

Abstract: For the total tardiness scheduling with precedence constraints, an approximation algorithm with polynomial complexity was presented by
transplanting the backward-shift algorithm of the case without precedence constraints. The new algorithm can get an approximation solution for the scheduling quickly.

Key words: Emmons conditions, precedence constraints, approximation algorithm, total tardiness scheduling, Emmons conditions, precedence constraints, approximation algorithm

中图分类号: