TY - JOUR

T1 - An algorithm for sequencing jobs to minimize total tardiness

AU - Li, Der Chiang

AU - Li, Te Yuan

PY - 1988/9

Y1 - 1988/9

N2 - A theoretical framework and an efficient algorithm are presented to solve the problem of sequencing jobs on a single processor. The objective achieved is minimum total tardiness. Jobs must be independent, with deterministic processing times. A brief review of the literature concerning sequencing to achieve minimum total tardiness is presented. This review shows that Emmons’ algorithm generally results in a partial schedule, and an enumerative method, branch and bound method or dynamic programming method, was then applied to help obtain a complete sequence. Thus Emmons’ algorithm is applied as a precursor to several enumerative algorithms. Furthermore, to certain problems (i. e., LPSD: jobs which have the property of a longer processing time but a shorter due date), Emmons’ theorems would not apply before branching the problems. The algorithm presented in this paper effectively applies the partitioning method to eliminate the need for enumerative methods. A set of necessary conditions for an optimal sequence is presented with proofs in the theory section. This is followed by a statement of the algorithm. The algorithm is illustrated with an example problem taken from Ref. [7]. Computational results are then presented which show the efficiency of the algorithm relative to dynamic programming.

AB - A theoretical framework and an efficient algorithm are presented to solve the problem of sequencing jobs on a single processor. The objective achieved is minimum total tardiness. Jobs must be independent, with deterministic processing times. A brief review of the literature concerning sequencing to achieve minimum total tardiness is presented. This review shows that Emmons’ algorithm generally results in a partial schedule, and an enumerative method, branch and bound method or dynamic programming method, was then applied to help obtain a complete sequence. Thus Emmons’ algorithm is applied as a precursor to several enumerative algorithms. Furthermore, to certain problems (i. e., LPSD: jobs which have the property of a longer processing time but a shorter due date), Emmons’ theorems would not apply before branching the problems. The algorithm presented in this paper effectively applies the partitioning method to eliminate the need for enumerative methods. A set of necessary conditions for an optimal sequence is presented with proofs in the theory section. This is followed by a statement of the algorithm. The algorithm is illustrated with an example problem taken from Ref. [7]. Computational results are then presented which show the efficiency of the algorithm relative to dynamic programming.

UR - http://www.scopus.com/inward/record.url?scp=0024103903&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024103903&partnerID=8YFLogxK

U2 - 10.1080/02533839.1988.9677117

DO - 10.1080/02533839.1988.9677117

M3 - Article

AN - SCOPUS:0024103903

VL - 11

SP - 653

EP - 659

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 6

ER -