A hybrid algorithm for the one machine sequencing problem to minimize total tardiness

V. Srinivasan

Naval Research Logistics Quarterly, 1971, vol. 18, issue 3, 317-327

Abstract: 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 n 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 less than linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 second on UNIVAC 1108 computer.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/nav.3800180304

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:18:y:1971:i:3:p:317-327

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().