Scheduling Jobs with Linear Model of Simultaneous Ageing and Learning Effects
DOI:
https://doi.org/10.7494/dmms.2011.5.1.37Keywords:
sequencing, single machine, learning effect, ageing effect, computational complexityAbstract
In the paper, we introduce some new scheduling model in which learning and aging effects are both considered simultaneously. In this model the actual processing time of the jobs depends only on its position in a schedule and can be described by the piecewise linear function. For single-processor problem with introduced model, we show that the problem of minimizing the makespan criterion for independent jobs with release dates is strongly NPhard, but some special cases of this problem are polynomially solvable. Based on those special cases, we propose 4 heuristic algorithms and we experimentally examine their usefulness for solving the general problem.References
Bachman A. & Janiak A. (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 55(3), 257–264. DOI: http://doi.org/10.1057/palgrave.jors.2601689.
Bachman A., Janiak A. & Kovalyov M.Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81(2), 81–84. DOI: http://doi.org/10.1016/S0020-0190(01)00196-X.
Badiru A.B. (1992). Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management, 39(2), 176–188. DOI: http://doi.org/10.1109/17.141275.
Biskup D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173–178. DOI: http://doi.org/10.1016/S0377-2217(98)00246-X.
Biskup D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2), 315–329. DOI: http://doi.org/10.1016/j.ejor.2007.05.040.
Carlson J.G. & Rowe A.J. (1976). How much does forgetting cost? Industrial Engineering, 8(9), 40–47.
Cheng T.C.E., Ding Q. & Lin B.M.T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152(1), 1–13. DOI: http://doi.org/10.1016/S0377-2217(02)00909-8.
Cheng T.C.E., Lee W.-C. & Wu C.-C. (2010). Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Computers & Industrial Engineering, 58(2), 326–331. DOI: http://doi.org/10.1016/j.cie.2009.11.008.
Cheng T.C.E. & Wang G. (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research, 98(1–4), 273–290. DOI: http://doi.org/10.1023/A:1019216726076.
Cheng T.C.E., Wu C.-C. & Lee W.-C. (2008). Some scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering, 54(4), 972–982. DOI: http://doi.org/10.1016/j.cie.2007.11.006.
Dutton J.M. & Thomas A. (1984). Treating progress functions as a managerial opportunity. Academy of Management Review, 9(2), 235–247. DOI: http://doi.org/10.5465/amr.1984.4277639.
Gawiejnowicz S. & Kononov A. (2010). Complexity and approximability of scheduling resumable proportionally deteriorating jobs. European Journal of Operational Research, 200(1), 305–308. DOI: http://doi.org/10.1016/j.ejor.2008.12.014.
Jaber M.Y. & Bonney M. (1999). The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: Past, present, and future. International Journal of Production Economics, 59(1–3), 93–102. DOI: http://doi.org/10.1016/S0925-5273(98)00027-9.
Janiak A., Janiak W. & Lichtenstein M. (2007). Resource management in machine scheduling problems: A survey. Decision Making in Manufacturing and Services, 1(2), 59–89. DOI: http://doi.org/10.7494/dmms.2007.1.2.59.
Janiak A., Krysiak T. & Trela R. (2011). Scheduling problems with learning and ageing effects: A survey. Decision Making in Manufacturing and Services, 5(1), 19–36. DOI: http://doi.org/10.7494/dmms.2011.5.1.19.
Janiak A. & Śnieżyk A. (2004). Scheduling with position-dependent processing times. In: Bubnicki Z., Hryniewicz O. & Węglarz J. (Eds.), Badania operacyjne i systemowe 2004. Zastosowania. Akademicka Oficyna Wydawnicza EXIT, Warszawa, 177–188.
Janiak A. & Śnieżyk A. (2005). Single processor scheduling with the linear aging effect, ready times and the makespan criterion. In: Domek S. & Kaszyński R. (Eds.), Proceedings of the 11th IEEE International Conference on Methods and Models in Automation and Robotics (MMAR 2005), Międzyzdroje, Poland, 29 August–1 September 2005. ZAPOL, Szczecin, 1073–1077.
Janiak A. & Rudek R. (2010). Scheduling jobs under an aging effect. Journal of the Operational Research Society, 61(6), 1041–1048. DOI: http://doi.org/10.1057/jors.2009.30.
Ji P., Lee W.B. & Li H. (1997). A new algorithm for the assignment problem: An alternative to the Hungarian method. Computers & Operations Research, 24(11), 1017–1023. DOI: http://doi.org/10.1016/S0305-0548(97)00019-1.
Jordan R. (1965). How to Use the Learning Curve. Materials Management Institute.
Kuo W.-H. & Yang D.-L. (2006). Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. European Journal of Operational Research, 174(2), 1184–1190. DOI: http://doi.org/10.1016/j.ejor.2005.03.020.
Lee W.-C. (2004). A note on deteriorating jobs and learning in single-machine scheduling problems. International Journal of Business and Economics, 3(1), 83–89.
Mosheiov G. (2001a). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52(10), 1165–1169. DOI: http://doi.org/10.1057/palgrave.jors.2601215.
Mosheiov G. (2001b). Scheduling problems with a learning effect. European Journal of Operational Research, 132(3), 687–693. DOI: http://doi.org/10.1016/S0377-2217(00)00175-2.
Mosheiov G. & Sidney J.B. (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147(3), 665–670. DOI: http://doi.org/10.1016/S0377-2217(02)00358-2.
Nawaz M., Enscore E.E. Jr. & Ham I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. DOI: http://doi.org/10.1016/0305-0483(83)90088-9.
Papadimitriou C.H. & Steiglitz K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ.
Shabtay D. & Steiner G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155(13), 1643–1666. DOI: http://doi.org/10.1016/j.dam.2007.02.003.
Sun L. (2009). Single-machine scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering, 57(3), 843–846. DOI: http://doi.org/10.1016/j.cie.2009.02.014.
Toksarı M.D., İşleyen S.K., Güner E. & Baykoç Ö.F. (2010). Assembly line balancing problem with deterioration tasks and learning effect. Expert Systems with Applications, 37(2), 1223–1228. DOI: http://doi.org/10.1016/j.eswa.2009.06.005.
Wang J.-B. (2007). Single-machine scheduling problems with the effects of learning and deterioration. Omega, 35(4), 397–402. DOI: http://doi.org/10.1016/j.omega.2005.07.008.
Wang J.-B., Huang X., Wang X.-Y., Yin N. & Wang L.-Y. (2009). Learning effect and deteriorating jobs in the single machine scheduling problems. Applied Mathematical Modelling, 33(10), 3848–3853. DOI: http://doi.org/10.1016/j.apm.2009.01.004.
Wang J.-B. & Liu L.-L. (2009). Two-machine flow shop problem with effects of deterioration and learning. Computers & Industrial Engineering, 57(3), 1114–1121. DOI: http://doi.org/10.1016/j.cie.2009.05.002.
Wright T.P. (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 3(4), 122–128. DOI: http://doi.org/10.2514/8.155.
Yang D.-L. & Kuo W.-H. (2009). Single-machine scheduling with both deterioration and learning effects. Annals of Operations Research, 172(1), 315–327. DOI: http://doi.org/10.1007/s10479-009-0615-3.
Yang S.-J. & Yang D.-L. (2010). Single-machine scheduling problems with aging/deteriorating effect under an optional maintenance activity consideration. INFOR: Information Systems and Operational Research, 48(3), 171–179. DOI: http://doi.org/10.3138/infor.48.3.171.
Yin Y., Xu D., Sun K. & Li H. (2009). Some scheduling problems with general position-dependent and time-dependent learning effects. Information Sciences, 179(14), 2416–2425. DOI: http://doi.org/10.1016/j.ins.2009.02.015.
