×

A new approach to the learning effect: Beyond the learning curve restrictions. (English) Zbl 1170.90392

Summary: We bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing \(k\)-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the \(k\)-stepwise function.

MSC:

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

References:

[1] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: review and extensions, Journal of the Operational Research Society, 50, 711-729 (1999) · Zbl 1054.90542
[2] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[3] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[4] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051
[5] Cheng, T. C.E.; Kovalyov, M. Y., Single machine batch scheduling with deadlines and resource dependent processing times, Operations Research Letters, 17, 243-249 (1995) · Zbl 0858.90073
[6] Ng, C. T.; Cheng, T. C.E.; Kovalyov, M. Y.; Lam, S. S., Single machine scheduling with a variable common due date and resource dependent processing times, Computers & Operations Research, 30, 1173-1185 (2003) · Zbl 1047.90022
[7] Bachman, A.; Janiak, A., Scheduling jobs with position dependent processing times, Journal of the Operational Research Society, 55, 257-264 (2004) · Zbl 1095.90033
[8] Mosheiov, G., Parallel machine scheduling with a learning effect, Journal of the Operational Research Society, 52, 1-5 (2001) · Zbl 1178.90159
[9] Mosheiov, G.; Sidney, J. B., Note on scheduling with general learning curves to minimize the number of tardy jobs, Journal of the Operational Research Society, 56, 110-112 (2005) · Zbl 1122.90356
[10] Jaber, Y. M.; Bonney, M., The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: past, present, and future, International Journal of Production Economics, 59, 93-102 (1999)
[11] Jackson, D., Technological change, the learning curve, and profitability (1998), Edward Elgar: Edward Elgar Northampton, MA
[12] Yelle, L. E., The learning curve: historical review and comprehensive study, Decision Sciences, 10, 302-328 (1979)
[13] Young, A., Learning by doing and the dynamic effects of international trade, Quarterly Journal of Economics, 56, 369-405 (1991)
[14] Wright, T. P., Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3, 122-128 (1936)
[15] Mosheiov, G.; Sidney, J. B., Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147, 665-670 (2003) · Zbl 1037.90529
[16] Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273-290 (2000) · Zbl 0967.68019
[17] Jordan, R. B., Learning how to use the learning curve, N.A.A. Bulletin, 39, 27-39 (1958)
[18] Carlson, J. G.; Rowe, R. G., How much does forgetting cost?, Industrial Engineering, 8, 40-47 (1976)
[19] Janiak A, Rudek R. On a general model of the learning effect. In: Proceedings of 11th IEEE international conference on methods and models in automation and robotics, 2005; p. 1115-20.; Janiak A, Rudek R. On a general model of the learning effect. In: Proceedings of 11th IEEE international conference on methods and models in automation and robotics, 2005; p. 1115-20.
[20] Kuo, W.-H.; Yang, D.-L., Single-machine group scheduling with a time-dependent learning effect, Computers & Operations Research, 33, 2099-2112 (2006) · Zbl 1086.90025
[21] 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 Discrete Mathematics, 3, 287-326 (1979) · Zbl 0411.90044
[22] Papadimitrou, C. H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[23] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of computer computations (1992), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[24] Moore, J. M., An \(n\) jobs, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002
[25] Sahni, S. K., Algorithms for scheduling independent tasks, Journal of the ACM, 23, 116-127 (1976) · Zbl 0326.68024
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.