Scheduling jobs with linear model of simultaneous ageing and learning effects

• Autorzy: Janiak A. , Lichtenstein M. , Rusoń A.
• Języki publikacji: EN

Abstrakty

EN

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 NP-hard, 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.

Słowa kluczowe

EN

sequencing; single machine; learning effect; ageing effect; computational complexity

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2011
• Tom: Vol. 5, no. 1-2
• Strony: 37--48
• Opis fizyczny: Bibliogr. [38] poz., rys., wykr., tab.

Twórcy

autor

Janiak A.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50 372 Wrocław, Poland

autor

Lichtenstein M.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50 372 Wrocław, Poland

autor

Rusoń A.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Z. Janiszewskiego 11/17, 50 372 Wrocław, Poland

Bibliografia

• Bachman, A. and Janiak, A., 2004. Scheduling jobs with position dependent processing times. Journal of the Operational Research Society 55, 257–264.
• Bachman, A., Janiak, A. and Kovalyov, M. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters 81(2), 81–84.
• Badiru, A., 1992. Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management 39(2), 176–188.
• Biskup, D., 1999. Single-machine scheduling with learning considerations. European Journal of Operational Research 115, 173–178.
• Biskup, D., 2008. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research 188(2), 315–329.
• Carlson, J., Rowe, A., 1976. How much does forgetting cost. Industrial Engineering 8(9), 40 47.
• Cheng, T., Ding, Q. and Lin, B., 2004. A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research 152(1), 1–13.
• Cheng, T., Lee, W. and Wu, C., 2010. Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Computers & Industrial Engineering 58(2), 326–331.
• Cheng, T. and Wang, G., 2000. Single machine scheduling with learning effect considerations. Annals of Operations Research 98(1), 273–290.
• Cheng, T., Wu, C. and Lee, W., 2008. Some scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering 54(4), 972–982.
• Dutton, J. and Thomas, A., 1984. Treating progress functions as a managerial opportunity. Academy of Management Review pp. 235–247.
• Gawiejnowicz, S. and Kononov, A., 2010. Complexity and approximability of scheduling resumable proportionally deteriorating jobs. European Journal of Operational Research 200(1), 305–308.
• Jaber, M., 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.
• Janiak, A., Janiak, W. and Lichtenstein, M., 2007. Resource management in machine scheduling problems: A survey. Decision Making in Manufacturing and Services 1, 59–89.
• Janiak, A., Krysiak, T. and Trela, R., 2011. Scheduling problems with learning and ageing effects: A survey. Decision Making in Manufacturing and Services 5, to appear.
• Janiak, A., Śnieżyk, A., 2004. Scheduling with position dependent processing times. In Z. Bubnicki, O. Hryniewicz and J.Węglarz (eds), Badania operacyjne i systemowe 2004. Zastosowania, Akademicka Oficyna Wydawnicza EXIT, Warszawa, Poland, pp. 177–188.
• Janiak, A., Śnieżyk, A., 2005a. Single processor scheduling with the linear aging efect, ready times and the makespan criterion. Proceedings of 11th IEEE International Conference on Methods and Models in Automation and Robotics, pp. 25–28.
• Janiak, A., Śnieżyk, A., 2005b. Single processors scheduling with the linear aging effect, ready times and makespan criterion. Proceedings of 11th IEEE International Conference on Methods and Models in Automation and Robotics, pp. 1073–1078.
• Janiak, A., Rudek, R., 2010. Scheduling jobs under an aging effect. Journal of the Operational Research Society 61(6), 1041–1048.
• Ji, P., Lee, W. B. and Li, H., 1997. A new algorithm for the assignment problem: An alternative to the hungarian method. Computers Operational Research 24(11), 1017–1023.
• Jordan, R., 1965. How to use the learning curve. Materials Management Institute.
• Kuo, W., Yang, D., 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.
• Lee, W., 2004. A note on deteriorating jobs and learning in single-machine scheduling problems. International Journal of Business 3(1), 83–89.
• Mosheiov, G., 2001a. Parallel machine scheduling with a learning effect. Journal of the Operational Research Society 52(10), 1165–1169.
• Mosheiov, G., 2001b. Scheduling problems with a learning effect. European Journal of Operational Research 132(3), 687–693.
• Mosheiov, G., Sidney, J., 2003. Scheduling with general job-dependent learning curves. European Journal of Operational Research 147(3), 665–670.
• Nawaz, M., Enscore, E. E. and Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega 11(1), 91–95.
• Papadimitrou, C., 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.
• Sun, L., 2009. Single-machine scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering 57(3), 843–846.
• Toksari, M., Isleyen, S., Guner, E. and Baykoc, O., 2010. Assembly line balancing problem with deterioration tasks and learning effect. Expert Systems with Applications 37(2), 1223–1228.
• Wang, J., 2007. Single-machine scheduling problems with the effects of learning and deterioration. Omega 35(4), 397–402.
• Wang, J., Huang, X., Wang, X., Yin, N. and Wang, L., 2009. Learning effect and deteriorating jobs in the single machine scheduling problems. Applied Mathematical Modelling 33(10), 3848–3853.
• Wang, J. and Liu, L., 2009. Two-machine flow shop problem with effects of deterioration and learning. Computers & Industrial Engineering 57(3), 1114–1121.
• Wright, T., 1936. Factors affecting the cost of airplanes. Journal of Aeronautical Science 3(4), 122–128.
• Yang, D. and Kuo, W., 2009. Single-machine scheduling with both deterioration and learning effects. Annals of Operations Research 172(1), 315–327.
• Yang, S. and Yang, D., 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.
• Yin, Y., Xu, D., Sun, K. and Li, H., 2009. Some scheduling problems with general position-dependent and time-dependent learning effects. Information Sciences 179(14), 2416–2425.