Scheduling with job-dependent learning effects and multiple rate-modifying activities. (English) Zbl 1229.90061

Summary: We consider a scheduling problem with job-dependent learning effects and multiple rate-modifying activities. The learning effects manifest such that the processing time of a job is a decreasing function of its position in a sequence. By job-dependent learning effects, we mean that the learning of the jobs is different. A rate-modifying activity is an activity that changes the production rate of a machine. So the actual processing time of a job in our problem is a variable, which depends not only on its position in a sequence but also on whether it is scheduled before or after a rate-modifying activity. We assume that each machine may have multiple rate-modifying activities. The objective is to minimize the total completion time. We show that all the cases of the problem are polynomially solvable.


90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, Journal of the operational research society, 55, 257-264, (2004) · Zbl 1095.90033
[2] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[3] Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022
[4] Brucker, P., Scheduling algorithms, (2001), Springer Berlin · Zbl 1051.90011
[5] Cheng, T.C.E.; Lai, P.J.; Wu, C.C.; Lee, W.C., Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information sciences, 179, 3127-3135, (2009) · Zbl 1170.90387
[6] Cheng, T.C.E.; Wang, G.Q., Single machine scheduling with learning effect considerations, Annals of operations research, 98, 273-290, (2000) · Zbl 0967.68019
[7] Cheng, T.C.E.; Wu, C.C.; Lee, W.C., Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects, Information sciences, 178, 2476-2487, (2008) · Zbl 1172.90397
[8] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of operations research, 5, 287-326, (1979) · Zbl 0411.90044
[9] He, Y.; Ji, M.; Cheng, T.C.E., Single machine scheduling with a restricted rate-modifying activity, Naval research logistics, 52, 361-369, (2005) · Zbl 1090.90084
[10] Janiak, A.; Rudek, R., The learning effect: getting to the core of the problem, Information processing letters, 103, 183-187, (2007) · Zbl 1184.68405
[11] Janiak, A.; Rudek, R., A new approach to the learning effect: beyond the learning curve restrictions, Computers & operations research, 35, 3727-3736, (2008) · Zbl 1170.90392
[12] Janiak, A.; Janiak, W.; Rudek, R.; Wielgus, A., Solution algorithms for the makespan minimization problem with the general learning model, Computers & industrial engineering, 56, 1301-1308, (2009)
[13] Janiak, A.; Rudek, R., Experience-based approach to scheduling problems with the learning effect, IEEE transactions on systems, man and cybernetics, part A, 39, 344-357, (2009)
[14] Janiak, A.; Rudek, R., A note on a makespan minimization problem with a multi-ability learning effect, Omega, 38, 213-217, (2010)
[15] Kuo, W.H.; Yang, D.L., Single-machine group scheduling with time-dependent learning effect, Computers & operations research, 33, 2099-2112, (2006) · Zbl 1086.90025
[16] Kuo, W.H.; Yang, D.L., Single machine scheduling with past-sequence-dependent setup times and learning effects, Information processing letters, 102, 22-26, (2007) · Zbl 1184.68132
[17] Lee, C.Y.; Leon, V.J., Machine scheduling with a rate-modifying activity, European journal of operational research, 128, 119-128, (2001) · Zbl 0983.90020
[18] 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
[19] Lee, W.C.; Wu, C.C., A note on single-machine group scheduling problems with position-based learning effect, Applied mathematical modelling, 33, 2159-2163, (2009) · Zbl 1205.90128
[20] Lodree, E.J.; Geiger, C.D., A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European journal of operational research, 201, 644-648, (2010) · Zbl 1192.90076
[21] Mosheiov, G., Scheduling problems with learning effect, European journal of operational research, 132, 687-693, (2001) · Zbl 1017.90051
[22] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, European journal of operational research, 147, 665-670, (2003) · Zbl 1037.90529
[23] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice Hall Englewood Cliffs, NJ · Zbl 0503.90060
[24] Pinedo, M., Scheduling: theory, algorithms, and systems, (2002), Prentice Hall Upper Saddle River, NJ · Zbl 1145.90394
[25] Wang, J.B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 397-402, (2007)
[26] Wu, C.C.; Lee, W.C., Single-machine and flowshop scheduling with a general learning effect model, Computers & industrial engineering, 56, 1553-1558, (2009)
[27] Zhao, C.L.; Tang, H.Y.; Cheng, C.D., Two-parallel machines scheduling with rate-modifying activities to minimize total completion time, European journal of operational research, 198, 354-357, (2009) · Zbl 1163.90518
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.