Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine. (English) Zbl 1221.90057

Summary: Group technology is important to manufacturing as it helps increase the efficiency of production and decrease the requirement of facilities. In this paper we investigate group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine setting. The learning phenomenon is implemented to model the setup time of groups. Three models of deteriorating for the job processing time within a group are examined. We show that all the problems studied are polynomially solvable with or without the presence of certain conditions where the objective is to find an optimal schedule for minimizing the makespan. We also investigate the minimization of the total completion time. We proved that one of the deterioration models examined in this study can also be solved in a polynomial time algorithm under certain conditions.


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


[1] Biskup, D., Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115, 173-178 (1999) · Zbl 0946.90025
[2] Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98, 273-290 (2000) · Zbl 0967.68019
[3] Mosheiov, G.; Sidney, J. B., Scheduling with general job-dependent learning curves, Eur. J. Oper. Res., 147, 665-670 (2003) · Zbl 1037.90529
[4] Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, Eur. J. Oper. Res., 174, 1184-1190 (2006) · Zbl 1103.90341
[5] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188, 315-329 (2008) · Zbl 1129.90022
[6] Janiak, A.; Rudek, R., Experience based approach to scheduling problems with the learning effect, IEEE Trans. Syst. Man Cybernet. Part A, 39, 344-357 (2009)
[7] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051
[8] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, Eur. J. Oper. Res., 47, 56-64 (1990) · Zbl 0717.90034
[9] Mosheiov, G., Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine, Comput. Ind. Eng., 28, 869-879 (1995)
[10] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: Review and extensions, J. Oper. Res. Soc., 50, 711-720 (1999) · Zbl 1054.90542
[11] Cheng, T. C.E.; Ding, O.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023
[12] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, J. Oper. Res. Soc., 55, 257-264 (2004) · Zbl 1095.90033
[13] Gawiejnowicz, S., Time-dependent Scheduling (2008), Springer-Verlag Inc.: Springer-Verlag Inc. New York · Zbl 1155.90004
[14] Ham, I.; Hitomi, K.; Yoshida, T., Group Technology: Applications to Production Management (1985), Kluwer-Nijhoff: Kluwer-Nijhoff Boston
[15] Guo, A.-X.; Wang, J.-B., Single machine scheduling with deteriorating jobs under the group technology assumption, Int. J. Pure Appl. Math., 18, 225-231 (2005) · Zbl 1139.90365
[16] Xu, F.; Guo, A.-X.; Wang, J.-B.; Shan, F., Single machine scheduling problem with linear deterioration under group technology, Int. J. Pure Appl. Math., 28, 401-406 (2006) · Zbl 1152.90474
[17] Kuo, W.-H.; Yang, D.-L., Single-machine group scheduling with a time-dependent learning effect, Comput. Oper. Res., 33, 2099-2112 (2006) · Zbl 1086.90025
[18] Wang, J.-B.; Guo, A.-X.; Shan, F.; Jiang, B.; Wang, L.-Y., Single machine group scheduling under decreasing linear deterioration, J. Appl. Math. Comput., 24, 283-293 (2007) · Zbl 1148.90326
[19] Wu, C.-C.; Shiau, Y.-R.; Lee, W.-C., Single-machine group scheduling problems with deterioration consideration, Comput. Oper. Res., 35, 1652-1659 (2008) · Zbl 1211.90094
[20] Lee, W.-C.; Wu, C.-C., A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33, 2159-2163 (2009) · Zbl 1205.90128
[21] Wang, J.-B.; Gao, W. J.; Wang, L. Y.; Wang, D., Single machine group scheduling with general linear deterioration to minimize the makespan, Int. J. Adv. Manuf. Technol., 43, 146-150 (2009)
[22] Yang, S.-J.; Yang, D.-L., Single-machine scheduling simultaneous with position-based and sum-of-processing-times-based learning considerations under group technology assumption, Appl. Math. Model., 35, 2068-2074 (2011) · Zbl 1217.90156
[23] Wang, J.-B., Single machine scheduling with time-dependent learning effect and deteriorating jobs, J. Oper. Res. Soc., 60, 583-586 (2009) · Zbl 1163.90515
[24] Toksar, M. D.; Oron, D.; Güner, E., Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning, Math. Comput. Model., 50, 401-406 (2009) · Zbl 1185.90097
[25] Wang, J.-B.; Huang, X.; Wang, X.-Y.; Yin, N.; Wang, L.-Y., Learning effect and deteriorating jobs in the single machine scheduling problems, Appl. Math. Model., 33, 3848-3853 (2009) · Zbl 1205.90137
[26] Huang, X.; Wang, J.-B.; Wang, L.-Y.; Gao, W.-J.; Wang, X.-R., Single machine scheduling with time-dependent deterioration and exponential learning effect, Comput. Indus. Eng., 58, 58-63 (2010)
[27] Sun, L., Single-machine scheduling problems with deteriorating jobs and learning effects, Comput. Indus. Eng., 57, 843-846 (2009)
[28] Wang, J.-B., Single machine scheduling with learning effect and deteriorating jobs, Comput. Indus. Eng., 57, 1452-1456 (2009)
[29] Yang, S.-J.; Yang, D.-L., Single-machine group scheduling problems under the effects of deterioration and learning, Comput. Indus. Eng., 58, 754-758 (2010)
[30] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
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.