Mathematical Modeling and Solving the no-Wait Flow Shop Scheduling Problem Considering the Release Times and Preventive Maintenance Activities

Document Type : Research Paper

Authors

1 Industrial Engineering, Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran

2 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran

10.22084/ier.2024.5564

Abstract

Due to the special position of the no-wait flow shop scheduling in production centers, this problem has received much attention in recent years. In this type of scheduling, there is no waiting time between the processing of a job on consecutive machines. This problem is raised in many industries, including the production of perishable foods. One common assumption in this problem is the availability of tasks at the zero moment. In many cases, some tasks have a non-zero release time. Also, in the field of operation scheduling, one of the common assumptions is the availability of machines in the planning horizon. It is clear that in practice, a machine is temporarily unavailable due to various reasons such as breakdown or preventive maintenance activities. Due to the importance of this issue, in the present study the no-wait flow shop scheduling problem considering the task release times and the preventive maintenance is investigated. For the mentioned problem, a Mixed Integer Non Linear Programing (MINLP) model is presented. The General Algebraic Modeling System (GAMS) software is used to solve the model. Also, in order to verify the validity of the presented model, sensitivity analysis has been performed on the important parameters. Due to the complexity of the model and the NP- hardness of the proposed problem, the Hybrid Harmony Search (HHS) metaheuristic algorithm is proposed to solve large-scale problems. In order to evaluate the performance of the proposed algorithm, numerical sample problems are solved using this algorithm, the GAMS software as well as the classic Harmony Search and the Improved Beam Search (IBS) algorithm. Computational results confirm the effectiveness of the proposed algorithm for the considered problem

Keywords

Main Subjects

References

  • Johnson, S.M., Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1954. 1(1): p. 61-68.
  • Abdel-Basset, M., et al., A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem. Future Generation Computer Systems, 2018. 85.
  • الفت، لعیا (2017). حداقل دیرکرد در زمان‌بندی مسائل جریان کارگاهی با موعد تحویل میانی. پژوهش‌های نوین در تصمیم‌گیری، دوره 2⸲ شماره ۳⸲ صفحه ۲۵-۴۷.
  • علاقه‌بندها (2018). مدل‌سازی زمان‌بندی و اندازه انباشته اقتصادی در جریان کارگاهی جایگشتی توزیع‌شده با کارخانه‌های متفاوت⸲ پژوهش‌های نوین در تصمیم‌گیری، دوره ۳⸲ شماره ۳⸲ صفحه ۱۲۹-۱۵۵.
  • Hall, N.G. and C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process. Operations research, 1996. 44(3): p. 510-525.
  • Hartmanis, J., Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson). Siam Review, 1982. 24(1): p. 90.
  • Pourhejazy, P., et al., Improved beam search for optimizing no-wait flowshops with release times. IEEE Access, 2020. 8: p. 148100-148124.
  • Pan, Q.-K., M.F. Tasgetiren, and Y.-C. Liang, A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers & Operations Research, 2008. 35(9): p. 2807-2839.
  • Riahi, V. and M. Kazemi, A new hybrid ant colony algorithm for scheduling of no-wait flowshop. Operational Research, 2018. 18(1): p. 55-74.
  • Gao, J., M. Gen, and L. Sun, Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing, 2006. 17(4): p. 493-507.
  • Miyata, H.H., M.S. Nagano, and J.N. Gupta, Integrating preventive maintenance activities to the no-wait flow shop scheduling problem with dependent-sequence setup times and makespan minimization. Computers & Industrial Engineering, 2019. 135: p. 79-104.
  • قندی بیدگلی، سمیه و بنرودی، ریحانه (2023). مدل‌سازی ریاضی و حل مسأله زمان‌بندی جریان کارگاهی انعطاف‌پذیر با جریان‌های معکوس و محدودیت دسترسی به ماشین‌ها. نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید, دوره ۱۰⸲ شماره ۲۱⸲ صفحه ۱-۱۷.
  • Chen, D.-S., R.G. Batson, and Y. Dang, Applied integer programming. Hoboken, NJ, 2010.
  • Branda, A., et al., Metaheuristics for the flow shop scheduling problem with maintenance activities integrated. Computers & Industrial Engineering, 2021. 151: p. 106989.
  • Wang, L., Q.-K. Pan, and M.F. Tasgetiren, Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert Systems with Applications, 2010. 37(12): p. 7929-7936.
  • Geem, Z.W., J.H. Kim, and G.V. Loganathan, A new heuristic optimization algorithm: harmony search. simulation, 2001. 76(2): p. 60-68.
  • Nagano, M.S. and H.H. Miyata, Review and classification of constructive heuristics mechanisms for no-wait flow shop problem. The International Journal of Advanced Manufacturing Technology, 2016. 86: p. 2161-2174.
  • Gangadharan, R. and C. Rajendran, Heuristic algorithms for scheduling in the no-wait flowshop. International Journal of Production Economics, 1993. 32(3): p. 285-290.
  • Rajendran, C., A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society, 1994. 45(4): p. 472-478.
  • Nawaz, M., E.E. Enscore Jr, and I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 1983. 11(1): p. 91-95.
  • Li, X., Q. Wang, and C. Wu, Heuristic for no-wait flow shops with makespan minimization. International Journal of Production Research, 2008. 46(9): p. 2519-2530.
  • Framinan, J.M. and R. Leisten, An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega, 2003. 31(4): p. 311-317.
  • Li, X. and C. Wu, Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments. Science in China Series F: Information Sciences, 2008. 51(7): p. 896-909.
  • Rajendran, C. and H. Ziegler, An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. European Journal of Operational Research, 1997. 103(1): p. 129-138.
  • Deng, G., H. Yang, and S. Zhang, An enhanced discrete artificial bee colony algorithm to minimize the total flow time in permutation flow shop scheduling with limited buffers. Mathematical Problems in Engineering, 2016. 2016.
  • Mahdavi, M., M. Fesanghary, and E. Damangir, An improved harmony search algorithm for solving optimization problems. Applied mathematics and computation, 2007. 188(2): p. 1567-1579.
  • قندی بیدگلی، سمیه و امینی، مرضیه (2021). ارائه مدل زمان‌بندی چندعاملی در محیط جریان کارگاهی با فرض زوال‌پذیری کارها، زمان‌های آماده‌سازی وابسته به توالی و زمان آزادسازی کارها با استفاده از الگوریتم ازدحام ذرات چندهدفه. نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید⸲ دوره ۹⸲ شماره ۱۸⸲ صفحه ۵۹-۷۹.
  • Vallada, E., R. Ruiz, and J.M. Framinan, New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 2015. 240(3): p. 666-677.
  • Reeves, C.R. Genetic algorithms and neighbourhood search. in Evolutionary Computing: AISB Workshop Leeds, UK, April 11–13, 1994 Selected Papers. 2005. Springer.
  • Taillard, E., Benchmarks for basic scheduling problems. european journal of operational research, 1993. 64(2): p. 278-285.
  • Lin, S.-W. and K.-C. Ying, Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics. Omega, 2016. 64: p. 115-125.
  • Kruskal, W.H. and W.A. Wallis, Use of ranks in one-criterion variance analysis. Journal of the American statistical Association, 1952. 47(260): p. 583-621.
  • Derrac, J., et al., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011. 1(1): p. 3-18.
Journal of Industrial Engineering Research in Production Systems
Volume 11, Issue 23
March 2024
Pages 39-55

Files

Share

How to cite

Statistics