×
Yin, Yunqiang; Xu, Dehua; Wang, Jiayin

Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect. (English) Zbl 1201.90093

Appl. Math. Modelling 34, No. 11, 3623-3630 (2010).
Summary: We bring into the scheduling field a general learning effect model where the actual processing time of a job is not only a general function of the total actual processing times of the jobs already processed, but also a general function of the job’s scheduled position. We show that the makespan minimization problem and the sum of the \(k\)th power of completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.

Cited in 15 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

scheduling; learning effect; single-machine
PDF BibTeX XML Cite
\textit{Y. Yin} et al., Appl. Math. Modelling 34, No. 11, 3623--3630 (2010; Zbl 1201.90093)
Full Text: DOI

References:

[1] Badiru, A. B., Computational survey of univariate and multivariate learning curve models, IEEE Trans. Eng. Manage., 39, 176-188 (1992)
[2] Jaber, Y. M.; Bonney, M., The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: past, present, and future, Int. J. Prod. Econ., 59, 93-102 (1999)
[3] Biskup, D., Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115, 173-178 (1999) · Zbl 0946.90025
[4] Cheng, T. C.E.; Wang, G., Single-machine scheduling with learning effect considerations, Ann. Oper. Res., 98, 273-290 (2000) · Zbl 0967.68019
[5] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, J. Oper. Res. Soc., 257-263 (2004) · Zbl 1095.90033
[6] Chen, P.; Wu, C.-C.; Lee, W.-C., A bi-criteria two-machine flowshop scheduling problem with a learning effect, J. Oper. Res. Soc., 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, Appl. Math. Comput., 184, 945-949 (2007) · Zbl 1143.90011
[8] Eren, T.; Guner, E., Minimizing total tardiness in a scheduling problem with a learning effect, Appl. Math. Model., 31, 1351-1361 (2007) · Zbl 1145.90021
[9] Lee, W.-C.; Wu, C.-C., Minimizing total completion time in a two-machine flowshop with a learning effect, Int. J. Prod. Econ., 88, 85-92 (2004)
[10] Lee, W.-C.; Wu, C.-C., A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33, 4, 2159-2163 (2009) · Zbl 1205.90128
[11] Lee, W.-C.; Wu, C.-C.; Sung, H.-J., A bi-criterion single-machine scheduling problem with learning considerations, Acta Inform., 40, 303-315 (2004) · Zbl 1137.90500
[12] Lin, B. M.T., Complexity results for single-machine scheduling with positional learning effects, J. Oper. Res. Soc., 58, 1099-1102 (2007) · Zbl 1278.90164
[13] Mosheiov, G., Scheduling problems with a learning effect, Eur. J. Oper. Res., 132, 687-692 (2001) · Zbl 1017.90051
[14] Mosheiov, G., Parallel machine scheduling with a learning effect, J. Oper. Res. Soc., 52, 1165-1169 (2001) · Zbl 1178.90159
[15] Mosheiov, G.; Sidney, J. B., Scheduling with general job-dependent learning curves, Eur. J. Oper. Res., 147, 665-670 (2003) · Zbl 1037.90529
[16] Wang, J.-B., A note on scheduling problems with learning effects and deteriorating jobs, Int. J. Syst. Sci., 827-832 (2006) · Zbl 1126.90347
[17] Wang, J.-B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 397-402 (2007)
[18] Wang, X.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan, Eur. J. Oper. Res., 178, 57-70 (2007) · Zbl 1110.90045
[19] Wang, J.-B.; Xia, Z.-Q., Flow-shop scheduling with a learning effect, J. Oper. Res. Soc., 56, 1325-1330 (2005) · Zbl 1082.90041
[20] Wu, C.-C.; Lee, W.-C.; Chen, T., Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations, Comput. Ind. Eng., 52, 124-132 (2007)
[21] Wu, C.-C.; Lee, W.-C.; Wang, W.-C., A two-machine flowshop maximum tardiness scheduling problem with a learning effect, Int. J. Adv. Manuf. Technol., 31, 743-750 (2007)
[22] Zhao, C.-L.; Zhang, Q.-L.; Tang, H.-Y., Machine scheduling problems with learning effects, dynamics of continuous, discrete and impulsive systems, Ser. A: Math. Anal., 11, 741-750 (2004)
[23] 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
[24] 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
[25] Kuo, W.-H.; Yang, D.-L., Single-machine scheduling problems with the time-dependent learning effect, Comput. Math. Appl., 53, 1733-1739 (2007) · Zbl 1152.90451
[26] Lee, W.-C.; Wu, C.-C.; Hsu, P.-H., A single-machine learning effect scheduling problem with release times, Omega, 38, 3-11 (2010)
[27] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E.; Liu, L. L., Single-machine scheduling with a time-dependent learning effect, Int. J. Prod. Econ., 111, 802-811 (2008)
[28] Wu, C.-C.; Lee, W.-C., A note on the total completion time problem in a permutation flowshop with a learning effect, Eur. J. Oper. Res., 192, 1, 343-347 (2009) · Zbl 1180.90144
[29] Koulamas, C.; Kyparisis, G. J., Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res., 178, 402-407 (2007) · Zbl 1107.90018
[30] Wu, C.-C.; Lee, W.-C., Single-machine scheduling problems with a learning effect, Appl. Math. Model., 32, 1191-1197 (2008) · Zbl 1172.90415
[31] 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, Inf. Sci., 178, 2476-2487 (2008) · Zbl 1172.90397
[32] Wu, C.-C.; Lee, W.-C., Single-machine and flowshop scheduling with a general learning effect model, Comput. Ind. Eng., 56, 1553-1558 (2009)
[33] Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Inf. Sci., 179, 2416-2425 (2009) · Zbl 1166.90342
[34] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188, 315-329 (2008) · Zbl 1129.90022
[35] Yang, D.-L.; Kuo, W.-H., Single-machine scheduling with an actual time-dependent learning effect, J. Oper. Res. Soc., 58, 1348-1353 (2007) · Zbl 1154.90505
[36] Townsend, W., The single-machine problem with quadratic penalty function of completion times: a branch-and-bound solution, Manage. Sci., 24, 530-533 (1978) · Zbl 0371.90065
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.