Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. (English) Zbl 1172.90397

Summary: We introduce a new scheduling model with learning effects in which the actual processing time of a job is a function of the total normal processing times of the jobs already processed and of the job’s scheduled position. We show that the single-machine problems to minimize makespan and total completion time are polynomially solvable. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. Finally, we present polynomial-time optimal solutions for some special cases of the \(m\)-machine flowshop problems to minimize makespan and total completion time.


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


[1] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[3] Chen, P.; Wu, C. C.; Lee, W. C., A bi-criteria two-machine flowshop scheduling problem with a learning effect, Journal of the Operational Research Society, 57, 1113-1125 (2006) · Zbl 1171.90394
[4] Cheng, M. B.; Sun, S. J.; Yu, Y., A note on flow shop scheduling problems with a learning effect on no-idle dominant machines, Applied Mathematics and Computation, 184, 945-949 (2007) · Zbl 1143.90011
[5] Chen, R. S.; Hsiang, C. H., A study on the critical success factors for corporations embarking on knowledge community-based e-learning, Information Sciences, 177, 570-586 (2007)
[6] Eren, T.; Güner, E., Minimizing total tardiness in a scheduling problem with a learning effect, Applied Mathematical Modelling, 31, 1351-1361 (2007) · Zbl 1145.90021
[8] Heiser, J.; Render, B., Operations Management (1999), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[10] Koulamas, C.; Kyparisis, G. J., Single-machine and two-machine flowshop scheduling with general learning functions, European Journal of Operational Research, 178, 402-407 (2007) · Zbl 1107.90018
[11] Lee, C. S.; Jiang, C. C.; Hsieh, T. C., A genetic fuzzy agent using ontology model for meeting scheduling system, Information Sciences, 176, 1131-1155 (2006) · Zbl 1092.68644
[12] Lee, W. C.; Wu, C. C.; Sung, H. J., A bi-criterion single-machine scheduling problem with learning considerations, Acta Informatica, 40, 303-315 (2004) · Zbl 1137.90500
[13] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051
[14] Mosheiov, G.; Sidney, J. B., Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147, 665-670 (2003) · Zbl 1037.90529
[15] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 1145.90394
[16] Russell, R.; Taylor, III. B.W., Operations Management: multimedia version (2000), Prentice Hall: Prentice Hall Upper Saddle River, NJ
[17] Smith, W. E., Various optimizers for single state production, Naval Research Logistic Quarterly, 3, 59-66 (1956)
[18] Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A. H., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness, Information Sciences, 177, 5072-5090 (2007) · Zbl 1121.90340
[19] Wang, G. Q.; Cheng, T. C.E., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273-290 (2000) · Zbl 0967.68019
[20] Wang, J. B., Single-machine scheduling problems with the effects of learning and deterioration, OMEGA - The international Journal of Management Science, 35, 397-402 (2007)
[21] Wang, J. B.; Xia, Z. Q., Flow-shop scheduling with a learning effect, Journal of the Operational Research Society, 56, 1325-1330 (2005) · Zbl 1082.90041
[22] Wright, T. P., Factors affecting the cost of airplanes, Journal of Aeronautical Science, 3, 122-128 (1936)
[23] Yelle, L. E., The learning curve: historical review and comprehensive survey, Decision Science, 10, 302-328 (1979)
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.