Article ID: | iaor20052140 |
Country: | Netherlands |
Volume: | 157 |
Issue: | 3 |
Start Page Number: | 784 |
End Page Number: | 790 |
Publication Date: | Sep 2004 |
Journal: | European Journal of Operational Research |
Authors: | Ghosh Jay B., Akturk M. Selim, Gunes Evrim D. |
Keywords: | heuristics |
We consider a single machine sequencing problem subject to tool wear, where the objective is to minimize the total completion time. We briefly describe the problem and discuss its properties, complexity and solution. Mainly, however, we focus on the performance of the shortest processing time list-scheduling heuristic. We provide theoretical worst-case bounds on SPT performance and also demonstrate its empirical behavior.