×

Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations. (English) Zbl 1170.90387

Summary: Scheduling with learning effects has attracted growing attention of the scheduling research community. A recent survey classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the first model and when the normal job processing times are large in the second model. Motivated by this observation, we propose a new learning model where the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. The use of the logarithm function is to model the phenomenon that learning as a human activity is subject to the law of diminishing return. Under the proposed learning model, we show that the scheduling problems to minimize the makespan and total completion time can be solved in polynomial time. We further show that the problems to minimize the maximum lateness, maximum tardiness, weighted sum of completion times and total tardiness have polynomial-time solutions under some agreeable conditions on the problem parameters.

MSC:

90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI

References:

[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 effect, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022
[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] Eren, T.; Güner, E., A bicriterion flowshop scheduling with a learning effect, Applied mathematical modelling, (2007)
[7] Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect, Applied mathematics and computation, (2008)
[8] Eren, T., A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect, Applied mathematics and computation, (2008)
[9] Fernandez-Breis, J.T.; Castellanos-Nieves, D.; Valencia-Garcí, R., Measuring individual learning performance in group work from a knowledge integration perspective, Information sciences, 179, 339-354, (2009)
[10] Heiser, J.; Render, B., Operations management, (1999), Prentice Hall Upper Saddle River, NJ
[11] Janiak, A.; Rudek, R., The learning effect: getting to the core of the problem, Information processing letters, 103, 183-187, (2007) · Zbl 1184.68405
[12] Janiak, A.; Rudek, R., A new approach to the learning effect: beyond the learning curve restrictions, Computers and operations research, (2007)
[13] Janiak, A.; Rudek, R., Viewpoint on: complexity results for single-machine scheduling with positional learning effects, Journal of the operational research society, 59, 1430, (2008)
[14] Janiak, A.; Rudek, R., Experience-based approach to scheduling problems with the learning effect, IEEE transactions on systems, man, and cybernetics part A, (2008)
[15] Janiak, A.; Janiak, W.A.; Rudek, R.; Wielgus, A., Solution algorithms for the makespan minimization problem with the general learning model, Computers and industrial engineering, (2008)
[16] 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
[17] Koulamas, C.; Kyparisis, G.J., Single-machine scheduling problems with past-sequence-dependent setup times, European journal of operational research, 187, 1045-1049, (2008) · Zbl 1137.90498
[18] Kang, M.; Kang, D.I.; Suh, J.; Lee, J., An energy-efficient real-time scheduling scheme on dual-channel networks, Information sciences, 178, 2553-2563, (2008)
[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] 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)
[21] 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
[22] Lee, J.H.; Ha, S.H., Recognizing yield patterns through hybrid applications of machine learning techniques, Information sciences, 179, 844-850, (2009)
[23] Luh, G.C.; Chueh, C.H., A multi-modal immune algorithm for the job-shop scheduling problem, Information sciences, (2008)
[24] Lin, B.M.T., Complexity results for single-machine scheduling with positional learning effects, Journal of the operational research society, 58, 1099-1102, (2007) · Zbl 1278.90164
[25] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, European journal of operational research, 147, 665-670, (2003) · Zbl 1037.90529
[26] Park, S.J.; Cho, K.H., Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems, Information sciences, 178, 3393-3401, (2008) · Zbl 1142.90409
[27] Pinedo, M., Scheduling: theory, algorithms, and systems, (2002), Prentice Hall Upper Saddle River, NJ · Zbl 1145.90394
[28] Russell, R.; Taylor, B.W., Operations management: multimedia version, (2000), Prentice Hall Upper Saddle River, NJ
[29] Smith, W.E., Various optimizers for single state production, Naval research logistic quarterly, 3, 59-66, (1956)
[30] 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)
[31] Wang, J.B.; Ng, C.T.; 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)
[32] Wright, T.P., Factors affecting the cost of airplanes, Journal of aeronautical science, 3, 122-128, (1936)
[33] Wu, C.C.; Lee, W.C., A note on the total completion time problem in a permutation flowshop with a learning effect, European journal of operational research, 192, 343-347, (2009) · Zbl 1180.90144
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.