Single machine scheduling with learning effect considerations. (English) Zbl 0967.68019

Summary: 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.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI