Single-machine and two-machine flowshop scheduling with general learning functions. (English) Zbl 1107.90018

Summary: We show that the \(O(n \log n)\) (where \(n\) is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Baker, K., Introduction to Sequencing and Scheduling (1974), John Wiley: John Wiley New York
[2] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[3] Dondeti, V. R.; Mohanty, B. B., Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs, European Journal of Operational Research, 105, 509-524 (1998) · Zbl 0955.90029
[4] Lee, W.-C.; Wu, C.-C., Minimizing total completion time in a two-machine flowshop with a learning effect, International Journal of Production Economics, 88, 85-93 (2004)
[5] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051
[6] Ow, P. S., Focused scheduling in proportionate flowshops, Management Science, 31, 852-869 (1985) · Zbl 0609.90067
[7] Smith, M. L.; Panwalkar, S. S.; Dudek, R. A., Flowshop sequencing problem with ordered processing time matrices, Management Science, 21, 544-549 (1975) · Zbl 0302.90025
[8] Zhao, C. L.; Zhang, Q. L.; Tang, H. G., Machine scheduling problems with learning effects, Dynamics of Continuous, Discrete and Impulsive Systems, Series A: Mathematical Analysis, 11, 741-750 (2004) · Zbl 1142.90413
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.