×

The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model. (English) Zbl 1248.90052

Summary: In this paper, we analyse the single processor total weighted completion time scheduling problem with the learning effect, where the processing time of each job is a non-increasing function dependent on the sum of the normal processing times of preceding jobs. We prove that the considered problem is at least NP-hard. Moreover, a pseudopolynomial time dynamic programming algorithm that optimally solves the problem with a step learning function (curve) is constructed. Furthermore, fast approximation algorithms for the general version of the problem, where job processing times are described by arbitrary functions dependent on the sum of the normal job processing times, are provided. Their efficiency is verified numerically and for Weighted Shortest Processing Times algorithm a worst case analysis is also performed.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
68T05 Learning and adaptive systems in artificial intelligence
90C39 Dynamic programming

Software:

Tabu search
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[2] 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
[3] Buşoniu, L.; Babuška, R.; De Schutter, B., A comprehensive survey of multiagent reinforcement learning, IEEE transactions on systems, man, and cybernetics – part C: applications and reviews, 38, 156-172, (2008)
[4] Cheng, T.C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of operations research, 98, 273-290, (2000) · Zbl 0967.68019
[5] 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
[6] 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
[7] Fernandez-Breis, J.T.; Castellanos-Nieves, D.; Valencia-Garci, R., Measuring individual learning performance in group work from a knowledge integration perspective, Information sciences, 179, 339-354, (2009)
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[9] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Norwell, MA · Zbl 0930.90083
[10] 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, 5, 287-326, (1979) · Zbl 0411.90044
[11] 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)
[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 the learning effect in multi-agent optimization, Expert systems with applications, 38, 5974-5980, (2011)
[15] Janiak, A.; Rudek, R., Scheduling jobs under an aging effect, Journal of the operational research society, 61, 1041-1048, (2010) · Zbl 1196.90048
[16] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[17] 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
[18] Kuo, W.-H.; Yang, D.-L., Minimizing the makespan in a single machine scheduling problem with a time-based learning effect, Information processing letters, 97, 64-67, (2006) · Zbl 1184.68131
[19] Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, European journal of operational research, 174, 1184-1190, (2006) · Zbl 1103.90341
[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] Kuo, W.-H.; Yang, D.-L., Single-machine scheduling problems with the time-dependent learning effect, Computers and mathematics with applications, 53, 1733-1739, (2007) · Zbl 1152.90451
[22] Kuo, W.-H.; Yang, D.-L., Note on single-machine and flowshop scheduling with a general learning effect model and some single-machine and m-machine flowshop scheduling problems with learning considerations, Information sciences, 180, 3814-3816, (2010) · Zbl 1194.90041
[23] Lai, P.-J.; Lee, W.-C., Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects, Omega, the international journal of management science, 39, 467-471, (2011)
[24] Lee, J.H.; Ha, S.H., Recognizing yield patterns through hybrid applications of machine learning techniques, Information sciences, 179, 844-850, (2009)
[25] Lee, W.-C.; Lai, P.-J., Scheduling problems with general effects of deterioration and learning, Information sciences, 181, 1164-1170, (2011) · Zbl 1208.90072
[26] Lee, W.-C.; Lai, P.-J.; Wu, C.-C., Erratum to some single-machine and m-machine flowshop scheduling problems with learning considerations [inform. sci. 179 (2009) 3885-3892], Information sciences, 180, 1073, (2010)
[27] Lee, W.-C.; Wu, C.-C., Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information sciences, 179, 3885-3892, (2009) · Zbl 1179.90141
[28] Lee, W.C.; Lai, P.J.; Wu, C.C., Erratum to ‘single-machine and flowshop scheduling with a general learning effect model’, Computers & industrial engineering, 59, 181, (2010)
[29] Nawaz, M.; Enscore, Jr E.E.; Ham, I.A., A heuristic algorithm for m-machine, n-jobs flow-shop sequencing problem, Omega, 11, 91-95, (1983)
[30] Wang, J.-B.; Ng, C.T.D.; Cheng, T.C.E.; Liu, L.L., Single-machine scheduling with a time-dependent learning effect, International journal of production economics, 111, 802-811, (2008)
[31] Wang, J-B.; Sun, L.; Sun, L., Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effects, Applied mathematical modelling, 34, 2813-2819, (2010) · Zbl 1201.90088
[32] Wang, J-B.; Wang, D.; Zhang, G-D., Single-machine scheduling with learning functions, Applied mathematics and computation, 216, 1280-1286, (2010) · Zbl 1187.90145
[33] Whiteson, S.; Stone, P., Adaptive job routing and scheduling, Engineering applications of artificial intelligence, 17, 855-869, (2004)
[34] Wright, T.P., Factors affecting the cost of airplanes, Journal of aeronautical sciences, 3, 122-128, (1936)
[35] Wu, C.-C.; Lee, W.-C., Single-machine scheduling problems with a learning effect, Applied mathematical modelling, 32, 1191-1197, (2008) · Zbl 1172.90415
[36] Wu, C.-C.; Lee, W.-C., Single-machine and flowshop scheduling with a general learning effect model, Computers & industrial engineering, 56, 1553-1558, (2009)
[37] Yang, S.-J.; Yang, D.-L., Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities, Omega, 38, 528-533, (2010)
[38] Yelle, L.E., The learning curve: historical review and comprehensive study, Decision science, 10, 302-328, (1979)
[39] Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information sciences, 179, 2416-2425, (2009) · Zbl 1166.90342
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.