Article ID: | iaor2002199 |
Country: | Netherlands |
Volume: | 98 |
Issue: | 1 |
Start Page Number: | 273 |
End Page Number: | 290 |
Publication Date: | Dec 2000 |
Journal: | Annals of Operations Research |
Authors: | Cheng T.C. Edwin, Wang Guoqing |
In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.