Article ID: | iaor1997105 |
Country: | United Kingdom |
Volume: | 23 |
Issue: | 7 |
Start Page Number: | 641 |
End Page Number: | 651 |
Publication Date: | Jul 1996 |
Journal: | Computers and Operations Research |
Authors: | Chand Suresh, Uzsoy Reha, Traub Rodney |
Keywords: | heuristics |
The authors address the problem of scheduling a single machine to minimize the total completion time in the face of dynamic job arrivals. Since the problem is strongly NP-hard, considerable research has been devoted to examining one-pass heuristic procedures for this problem. In this paper the authors present an iterative improvement heuristic which operates by modifying the problem data in a manner that allows one-pass heuristics to generate improved solutions. Computational experiments show that the procedure obtains significant improvements over a variety of one-pass heuristics in modest CPU times.