Scheduling jobs with general learning functions

Abstract

This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to job normal processing times.

Keywords

Scheduling / single machine / learning effect / makespan / total completion time

References

[1] Badiru A.B.. Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management, 1992, 39: 176-188.

[2] Bachman A., Janiak A.. Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 2004, 55: 257-264.

[3] Biskup D.. Single-machine scheduling with learning considerations. European Journal of Operational Research, 1999, 115: 173-178.

[4] Biskup D.. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 2008, 118: 315-329.

[5] Biskup D., Simons D.. Common due date scheduling with autonomous and induced learning. European Journal of Operational Research, 2004, 159: 606-616.

[6] Cheng T.C.E., Wang G.. Single machine scheduling with learning effect considerations. Annals of Operations Research, 2000, 98: 273-290.

[7] Koulamas C., Kyparisis G.J.. Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 2007, 178: 402-407.

[8] Mosheiov G.. Scheduling problems with a learning effect. European Journal of Operational Research, 2001, 132: 687-693.

[9] Mosheiov G.. Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 2001, 52: 1165-1169.

[10] Mosheiov G., Sidney J.B.. Scheduling with general job-dependent learning curves. European Journal of Operational Research, 2003, 147: 665-670.

[11] Toksar M.D., Guner E.. Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration. Computers & Operations Research, 2009, 36: 2394-2417.

[12] Wu C.-C., Lee W.-C.. Single-machine and flowshop scheduling with a general learning effect model. Computers and Industrial Engineering, 2009, 56: 1553-1558.