×

Single-machine group scheduling with general deterioration and learning effects. (English) Zbl 1243.90055

Summary: We consider single-machine group scheduling problems with effects of learning and deterioration at the same time. By effects of learning and deterioration, we mean that the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent and time-dependent learning effects. The objective of scheduling problems is to minimize the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.

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, J. Oper. Res. Soc., 50, 711-720 (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, Eur. J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023
[3] Gawiejnowicz, S., Time-Dependent Scheduling (2008), Springer: Springer Berlin, (ISBN 978-3-540-69445-8) · Zbl 1155.90004
[4] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188, 315-329 (2008) · Zbl 1129.90022
[5] 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
[6] Wu, C.-C.; Lee, W.-C., Single-machine group-scheduling problems with deteriorating setup times and job-processing times, Int. J. Prod. Econ., 115, 128-133 (2008)
[7] Wu, C.-C.; Lee, W.-C., Single-machine scheduling problems with a learning effect, Appl. Math. Model., 32, 1191-1197 (2008) · Zbl 1172.90415
[8] Wang, J.-B.; Lin, L.; Shan, F., Single-machine group scheduling problems with deteriorating jobs, Int. J. Adv. Manuf. Tech., 39, 808-812 (2008)
[9] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Comput. Oper. Res., 35, 2684-2693 (2008) · Zbl 1180.90143
[10] Y. Yan, D.-Z. Wang, D.-W. Wang, H.-F. Wang, Single-machine group scheduling problems with deterioration and learning effects, IEEE Proc. Seventh World Congr. Intell. Control Automat., 2008, pp. 4933-4936.; Y. Yan, D.-Z. Wang, D.-W. Wang, H.-F. Wang, Single-machine group scheduling problems with deterioration and learning effects, IEEE Proc. Seventh World Congr. Intell. Control Automat., 2008, pp. 4933-4936.
[11] Wang, J.-B., Single machine scheduling with a time-dependent learning effect and deteriorating jobs, J. Oper. Res. Soc., 60, 583-586 (2009) · Zbl 1163.90515
[12] Wang, J.-B.; Liu, L.-L., Two-machine flow shop problem with effects of deterioration and learning, Comput. Ind. Eng., 57, 1114-1121 (2009)
[13] 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)
[14] Wang, J.-B.; Wang, D.; Wang, L.-Y.; Lin, L.; Yin, N.; Wang, W.-W., Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Comput. Math. Appl., 57, 9-16 (2009) · Zbl 1165.90471
[15] Lee, W.-C.; Wu, C.-C., Some single-machine and \(m\)-machine flowshop scheduling problems with learning considerations, Infor. Sci., 179, 3885-3892 (2009) · Zbl 1179.90141
[16] 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
[17] Eren, T., A note on minimizing maximum lateness in an \(m\)-machine scheduling problem with a learning effect, Appl. Math. Comput., 209, 186-190 (2009) · Zbl 1156.90360
[18] Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect, Appl. Math. Comput., 208, 355-358 (2009) · Zbl 1155.90380
[19] Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Infor. Sci., 179, 2416-2425 (2009) · Zbl 1166.90342
[20] 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, Infor. Sci., 179, 3127-3135 (2009) · Zbl 1170.90387
[21] Janiak, A.; Rudek, R., Experience based approach to scheduling problems with the learning effect, IEEE Trans. Syst., Man, Cybern.-Part A, 39, 344-357 (2009)
[22] Janiak, A.; Janiak, W. A.; Rudek, R.; Wielgus, A., Solution algorithms for the makespan minimization problem with the general learning model, Comput. Ind. Eng., 56, 1301-1308 (2009)
[23] Zhu, V. C.Y.; Sun, L.-Y.; Sun, L.-H.; Li, X., Single machine scheduling time-dependent jobs with resource-dependent ready times, Comput. Ind. Eng., 58, 84-87 (2010)
[24] 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. Ind. Eng., 58, 58-63 (2010)
[25] Wang, J.-B., Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan, Int. J. Adv. Manuf. Technol., 48, 719-723 (2010)
[26] Wang, J.-B., A note on single-machine scheduling with decreasing time-dependent job processing times, Appl. Math. Model., 34, 294-300 (2010) · Zbl 1185.90098
[27] Wang, J.-B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 34, 309-313 (2010) · Zbl 1185.90099
[28] Wang, J.-B.; Wang, D.; Zhang, G.-D., Single-machine scheduling with learning functions, Appl. Math. Comput., 216, 1280-1286 (2010) · Zbl 1187.90145
[29] Wang, J.-B.; Sun, L.-H.; Sun, L.-Y., Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Appl. Math. Model., 34, 2813-2819 (2010) · Zbl 1201.90088
[30] Wang, J.-B.; Sun, L.-H.; Sun, L.-Y., Single machine scheduling with a learning effect and discounted costs, Int. J. Adv. Manuf. Technol., 49, 1141-1149 (2010)
[31] Wang, J.-B.; Sun, L.-H.; Sun, L.-Y., Scheduling jobs with an exponential sum-of-actual-processing-time based learning effect, Comput. Math. Appl., 60, 2673-2678 (2010) · Zbl 1205.90138
[32] Wang, J.-B.; Sun, L.-H.; Sun, L.-Y., Single-machine total completion time scheduling with a time-dependent deterioration, Appl. Math. Model., 35, 1506-1511 (2011) · Zbl 1211.90092
[33] Wang, J.-B.; Wang, M.-Z., Single machine multiple common due dates scheduling with general job-dependent learning curves, Comput. Math. Appl., 60, 2998-3002 (2010) · Zbl 1207.90059
[34] Wang, J.-B.; Wang, M.-Z., A revision of machine scheduling problems with a general learning effect, Math. Comput. Model., 53, 330-336 (2011) · Zbl 1211.90093
[35] Wang, J.-B.; Li, J.-X., Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects, Appl. Math. Model., 35, 1388-1395 (2011) · Zbl 1211.90091
[36] Huang, X.; Wang, M.-Z., Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties, Appl. Math. Model., 35, 1349-1353 (2011) · Zbl 1211.90085
[37] Yang, S.-H.; Wang, J.-B., Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, Appl. Math. Comput., 217, 4819-4826 (2011) · Zbl 1230.90104
[38] Huang, X.; Wang, M.-Z.; Wang, J.-B., Single machine group scheduling with both learning effects and deteriorating jobs, Comput. Ind. Eng., 60, 750-754 (2011)
[39] Wang, J.-B.; Wang, J.-J., Single-machine scheduling jobs with exponential learning functions, Comput. Ind. Eng., 60, 755-759 (2011)
[40] Wu, Y.-B.; Wang, M.-Z.; Wang, J.-B., Some single-machine scheduling with both learning and deterioration effects, Appl. Math. Model., 35, 3731-3736 (2011) · Zbl 1221.90052
[41] Wang, X.-Y.; Wang, M.-Z.; Wang, J.-B., Flow shop scheduling to minimize makespan with decreasing linear deterioration, Comput. Ind. Eng., 60, 840-844 (2011)
[42] Wang, J.-B.; Wang, C., Single-machine due-window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 35, 4017-4022 (2011) · Zbl 1221.90050
[43] Wang, J.-B.; Wei, C.-M., Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties, Appl. Math. Comput., 217, 8093-8099 (2011) · Zbl 1230.90103
[44] J.-B. Wang, J.-J. Wang, P. Ji, Scheduling jobs with chain precedence constraints and deteriorating jobs, J. Oper. Res. Soc. doi:10.1057/jors.2010.120; J.-B. Wang, J.-J. Wang, P. Ji, Scheduling jobs with chain precedence constraints and deteriorating jobs, J. Oper. Res. Soc. doi:10.1057/jors.2010.120
[45] J.-B. Wang, M.-Z. Wang, Single-machine scheduling with nonlinear deterioration, Optimization Lett. doi:10.1007/s11590-010-0253-3; J.-B. Wang, M.-Z. Wang, Single-machine scheduling with nonlinear deterioration, Optimization Lett. doi:10.1007/s11590-010-0253-3
[46] J.-B. Wang, M.-Z. Wang, Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects, Ann. Oper. Res. doi:10.1007/s10479-011-0923-2; J.-B. Wang, M.-Z. Wang, Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects, Ann. Oper. Res. doi:10.1007/s10479-011-0923-2 · Zbl 1233.90174
[47] J.-B. Wang, P. Ji, T.C.E. Cheng, D. Wang, Minimizing makespan in a two-machine flow shop with effects of deterioration and learning, Optimization Lett. doi:10.1007/s11590-011-0334-y; J.-B. Wang, P. Ji, T.C.E. Cheng, D. Wang, Minimizing makespan in a two-machine flow shop with effects of deterioration and learning, Optimization Lett. doi:10.1007/s11590-011-0334-y · Zbl 1259.90039
[48] S.P. Mitrofanov, Scientific principles of group technology, National Lending Library, London, UK, 1966.; S.P. Mitrofanov, Scientific principles of group technology, National Lending Library, London, UK, 1966.
[49] Potts, C. N.; Van Wassenhove, L. N., Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity, J. Oper. Res. Soc., 43, 395-406 (1992) · Zbl 0756.90050
[50] Webster, S.; Baker, K. R., Scheduling groups of jobs on a single machine, Oper. Res., 43, 692-703 (1995) · Zbl 0857.90062
[51] 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
[52] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051
[53] 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.