مدل‌سازی ریاضی و حل مسأله زمان‌بندی جریان کارگاهی بدون انتظار با درنظر گرفتن زمان آزادسازی و فعالیت‌های نگهداری و تعمیرات پیشگیرانه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 کارشناسی مهندسی صنایع، گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کاشان، کاشان، ایران

2 استادیار گروه مهندسی صنایع، گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کاشان، کاشان، ایران

10.22084/ier.2024.5564

چکیده

به‌دلیل جایگاه ویژه زمان‌بندی جریان کارگاهی بدون انتظار در مراکز تولیدی، این مسأله در سال‌های اخیر بسیار مورد توجه واقع شده‌ است. در این نوع زمان‌بندی، میان پردازش یک کار بر روی ماشین‌های متوالی هیچ‌گونه توقفی صورت نمی‌گیرد. این مسأله در صنایع بسیاری ازجمله تولید مواد غذایی فاسدشدنی مطرح می‌باشد. یکی از فرضیات رایج در این مسأله، دردسترس بودن کارها در لحظه صفر است. در بسیاری از مواقع کارها دارای زمان آزادسازی غیرصفر می‌باشند. همچنین یکی از فرضیات رایج درحوزه زمان‌بندی عملیات، دردسترس بودن ماشین‌ها در افق برنامه‌ریزی است. واضح است که در عمل یک ماشین، به‌دلایل مختلف نظیر وقوع خرابی یا انجام فعالیت‌های نگهداری و تعمیرات پیشگیرانه موقتاً دردسترس نباشد. باتوجه به اهمیت این موضوع، در تحقیق حاضر مسأله زمان‌بندی جریان کارگاهی بدون انتظار با زمان آزادسازی کارها و فعالیت‌های نگهداری و تعمیرات پیشگیرانه بررسی شده است. برای این مسأله یک مدل برنامه‌ریزی غیرخطی عدد صحیح مختلط ارائه گردیده است. برای حل مدل از نرم‌افزار گمز استفاده شده است. همچنین به‌منظور احراز اعتبار مدل ارائه شده⸲ روی پارامترهای مهم مدل تحلیل حساسیت انجام شده است. باتوجه به پیچیدگی مدل و NP-hard بودن مسأله مورد بررسی، جهت حل مسائل با ابعاد بزرگ الگوریتم فراابتکاری جستجوی هارمونی ترکیبی پیشنهاد شده است. به‌منظور ارزیابی عملکرد الگوریتم پیشنهادی، به حل مسائل نمونه عددی با استفاده از این الگوریتم، نرم‌افزار گمز الگوریتم جستجوی هارمونی کلاسیک و همچنین الگوریتم جستجوی پرتوی بهبودیافته پرداخته شده است. نتایج محاسباتی، مؤید کارایی بسیار خوب الگوریتم مذکور برای حل مسأله مورد بررسی می‌باشد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

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

نویسندگان [English]

  • Pariya Khaksari 1
  • Somayeh Ghandi Bidgoli 2
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
چکیده [English]

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

کلیدواژه‌ها [English]

  • No-Wait Flow Shop Scheduling
  • Task Release Time
  • Preventive Maintenance Activity
  • Hybrid Harmony Search (HHS) Algorithm

مراجع

  • 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.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 11، شماره 23
اسفند 1402
صفحه 39-55

فایل ها

هم رسانی

ارجاع به این مقاله

آمار