×

Some scheduling problems with general position-dependent and time-dependent learning effects. (English) Zbl 1166.90342

Summary: In scheduling problems with learning effects, most of the research is based on specific learning functions. In this paper, we develop a general model with learning effects where the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. In particular, it is shown that some single machine scheduling problems and \(m\)-machine permutation flowshop problems are still polynomially solvable under the proposed model. These results are significant extensions of some of the existing results on learning effects in the literature.

MSC:

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

References:

[1] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, Journal of the Operational Research Society, 55, 257-263 (2004) · Zbl 1095.90033
[2] Badiru, A. B., Computational survey of univariate and multivariate learning curve models, IEEE Transactions on Engineering Management, 39, 176-188 (1992)
[3] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[4] 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
[5] Biskup, D.; Simons, D., Common due date scheduling with autonomous and induced learning, European Journal of Operational Research, 159, 606-616 (2004) · Zbl 1134.90378
[6] 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
[7] 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
[8] Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273-290 (2000) · Zbl 0967.68019
[9] 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
[10] Eren, T.; Guner, E., Minimizing total tardiness in a scheduling problem with a learning effect, Applied Mathematical Modelling, 31, 1351-1361 (2007) · Zbl 1145.90021
[11] 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
[12] 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)
[13] 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
[14] 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
[15] Kuo, W.-H.; Yang, D.-L., Single-machine group scheduling with a time-dependent learning effect, Computers and Operations Research, 33, 2099-2112 (2006) · Zbl 1086.90025
[16] 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
[17] 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-92 (2004)
[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] 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
[20] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-692 (2001) · Zbl 1017.90051
[21] Mosheiov, G., Parallel machine scheduling with a learning effect, Journal of the Operational Research Society, 52, 1165-1169 (2001) · Zbl 1178.90159
[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] 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
[24] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2008), Springer: Springer New York
[25] 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
[26] Townsend, W., The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution, Management Science, 24, 530-533 (1978) · Zbl 0371.90065
[27] Wang, J.-B., A note on scheduling problems with learning effects and deteriorating jobs, International Journal of Systems Science, 37, 827-832 (2006) · Zbl 1126.90347
[28] Wang, J.-B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 397-402 (2007)
[29] 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)
[30] 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
[31] Wang, X.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan, European Journal of Operational Research, 178, 57-70 (2007) · Zbl 1110.90045
[32] Wu, C.-C.; Lee, W.-C., Single-machine scheduling problems with a learning effect, Applied Mathematical Modeling, 32, 1191-1197 (2008) · Zbl 1172.90415
[33] Wu, C.-C.; Lee, W.-C.; Chen, T., Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations, Computers and Industrial Engineering, 52, 124-132 (2007)
[34] Wu, C.-C.; Lee, W.-C.; Wang, W.-C., A two-machine flowshop maximum tardiness scheduling problem with a learning effect, International Journal of Advanced Manufacturing Technology, 31, 743-750 (2007)
[35] Xu, D.; Cheng, Z.; Yin, Y.; Li, H., Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Computers and Operations Research, 36, 1809-1812 (2009) · Zbl 1179.90166
[36] Xu, D.; Sun, K.; Li, H., Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan, Computers and Operations Research, 35, 1344-1349 (2008) · Zbl 1171.90411
[37] D. Xu, Y. Yin, H. Li, Scheduling jobs under increasing linear machine maintenance time, Journal of Scheduling, doi:10.1007/s10951-008-0057-9.; D. Xu, Y. Yin, H. Li, Scheduling jobs under increasing linear machine maintenance time, Journal of Scheduling, doi:10.1007/s10951-008-0057-9. · Zbl 1231.90222
[38] D. Xu, Y. Yin, H. Li, A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 197 (2009) 825-827.; D. Xu, Y. Yin, H. Li, A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 197 (2009) 825-827. · Zbl 1159.68359
[39] Zhao, C.-L.; Zhang, Q.-L.; Tang, H.-Y., Machine scheduling problems with learning effects, Dynamics of Continuous, Discrete and Impulsive Systems, Series A: Mathematical Analysis, 11, 741-750 (2004) · Zbl 1142.90413
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.