Journal of East China Normal University(Natural Sc ›› 2007, Vol. 2007 ›› Issue (1): 51-55.

• Article • Previous Articles     Next Articles

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

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

CLC Number: