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

Cheng, T. C. Edwin; Wang, Guoqing

Ann. Oper. Res. 98, 273-290 (2000).

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.

MSC:

68M20

Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

scheduling; sequencing; learning; single machine scheduling problem