A Hybrid Algorithm for the One Machine Sequencing Problem to Minimize Total Tardiness

摘要

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up only linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 seconds on UNIVAC 1108 computer. (Author)