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.
|Number of pages||18|
|Journal||Annals of Operations Research|
|Publication status||Published - 1 Dec 2000|
ASJC Scopus subject areas
- Decision Sciences(all)
- Management Science and Operations Research