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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها

موضوعات

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

Mathematical Modeling and Solving the Flexible Flow Shop Scheduling Problem with Reverse Flows and the Limitation of Access to Machines

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

  • Somayeh Ghandi Bidgoli 1
  • Reyhaneh Bonroodi 2
1 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran
2 2. Master student of Industrial Engineering, Faculty of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran
چکیده [English]

Due to the special position of flow shop scheduling systems in production centers, these issues have received a lot of attention in recent years. One common assumption in these cases is the availability of machines on the planning horizon. In real industrial environments, a machine may be temporarily unavailable for reasons such as the need for preventative maintenance. Due to the importance of this issue, in the present study the flexible flow shop scheduling problem with reverse flows is investigated by considering the activity of preventive maintenance in which there are two flows of jobs (direct and reverse) that cover the same machines in opposite directions. An essential issue for modeling the flexible flow shop-scheduling problem is to consider the limitations of access to machines in order to perform preventive maintenance. The maintenance operation on each machine has a fixed duration and its beginning and end occur in a certain time window. For the mentioned problem, a Mixed Integer NonLinear Programing (MINLP) model is presented. The objective of this model is to minimize the maximal completion time of the jobs (i.e., the ma kespan). Due to the complexity of the model and the NP-hardness of the proposed problem, the Imperialist Competitive Algorithm (ICA) is proposed to solve large-scale problems. In order to evaluate the performance of the proposed algorithm, numerical sample problems in different sizes are solved using this algorithm, the General Algebraic Modeling System (GAMS) software as well as the genetic algorithm. Computational results demonstrate the effectiveness of the Imperialist Competitive Algorithm for the considered problem.

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

  • Flexible Flow Shop Scheduling (FFSS)
  • Reverse Flows
  • The Limitation of Access to Machines
  • Preventive Maintenance (PM)
  • Imperialist Competitive Algorithm (ICA)

مراجع

  • Johnson, S.M., Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1954. 1(1): p. 61-68.
  • 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.
  • 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(03).
  • Lian, Z., Gu, and B. Jiao, A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos, Solitons & Fractals, 2008. 35(5): p. 851-861.
  • Sayadi, M., R. Ramezanian, and N. Ghaffari-Nasab, A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 2010. 1(1): p. 1-10.
  • Luo, Q., et al., Discrete bat algorithm for optimal problem of permutation flow shop scheduling. The Scientific World Journal, 2014. 2014.
  • Arthanary, T., An extension of two machine sequencing problem. Opsearch, 1971. 8: p. 10-22.
  • Lee, T. and Y. Loong, A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 2019. 10(1): p. 67-88.
  • Madhushini, N. and C. Rajendran, Branch-and-bound algorithms for scheduling in an m-machine no-wait flowshop. Sādhanā, 2020. 45(1): p. 1-11.
  • اسدی گنگرچ ابراهیم و نهاوندی نسیم (۱۳۹۴). توسعه روش آزادسازی لاگرانژین برای حل مسأله زمان‌بندی در محیط جریان کارگاهی انعطاف‌پذیر، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، دوره ۳، شماره 6، صفحه 1۳۱-1۲۱.
  • Gholami, M., M. Zandieh, and A. Alem-Tabriz, Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. The International Journal of Advanced Manufacturing Technology, 2009. 42(1): p. 189-201.
  • Acero-Dominguez, M.J. and C. Paternina-Arboleda. Scheduling jobs on a k-stage flexible flow shop using a TOC-based (bottleneck) procedure. in Proceedings of the 2004 IEEE Systems and Information Engineering Design Symposium, 2004. 2004. IEEE.
  • Costa, A., F.A. Cappadonna, and S. Fichera, A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints. The International Journal of Advanced Manufacturing Technology, 2014. 75(5): p. 833-847.
  • Janiak, A., et al., Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International journal of production economics, 2007. 105(2). p. 407-424.
  • بهنامیان, جواد و دیانت, فاطمه (۱۳۹۵). مقایسه سه روش فراابتکاری برای کمینه نمودن زمان چرخه در مسأله زمان‌بندی جریان کارگاهی مختلط دوره‌ای با درنظر گرفتن اثر یادگیری، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، دوره ۴، شماره ۸، صفحه 1۱۷-1۰۵.
  • Wang, X. and L. Tang, A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Computers & Operations Research, 2009. 36(3): p. 907-918.
  • Jolai, F., M. Rabiee, and H. Asefi, A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times. International Journal of Production Research, 2012. 50(24): p. 7447-7466.
  • Cui, Z. and X. Gu, An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems. Neurocomputing, 2015. 148: p. 248-259.
  • شفیعی رودباری، عرفان و همکاران (1399). مدل‌سازی ‌شبکه زنجیره‌تأمین معکوس چندرده‌ای و حل توسط الگوریتم ترکیبی، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، دوره 8، شماره 16، صفحه 185-197.
  • Abdeljaouad, M.A., et al., Job-shop production scheduling with reverse flows. European Journal of Operational Research, 2015. 244(1): p. 117-128.
  • Salema, M.I.G., A.P. Barbosa-Povoa, and A.Q. Novais, Simultaneous design and planning of supply chains with reverse flows: A generic modelling framework. European journal of operational research, 2010. 203(2): p. 336-349.
  • Krikke, H., J. Bloemhof-Ruwaard, and L.N. Van Wassenhove, Concurrent product and closed-loop supply chain design with an application to refrigerators. International journal of production research, 2003. 41(16): p. 3689-3819.
  • Realff, M.J., J.C. Ammons, and D.J. Newton, Robust reverse production system design for carpet recycling. Iie Transactions, 2004. 36(8): p. 767-776.
  • Brennan, L., S.M. Gupta, and K.N. Taleb, Operations planning issues in an assembly/disassembly environment. International Journal of Operations & Production Management, 1994.
  • Soleimaninia, F. and E. Mehdizadeh, Mathematical Modeling and Solving Flexible Job-Shop Production Scheduling with Reverse Flows. Advances in Industrial Engineering, 2018. 52(1): 87-96.
  • Trochu, J., A. Chaabane, and M. Ouhimmou, A two-stage stochastic optimization model for reverse logistics network design under dynamic suppliers’ locations. Waste Management, 2019. 95: p. 569-583.
  • Chileshe, N., R.S. Jayasinghe, and R. Rameezdeen, Information flow-centric approach for reverse logistics supply chains. Automation in Construction, 2019. 106: p. 102858.
  • Aghighi, S., et al., Open-shop production scheduling with reverse flows. Computers & Industrial Engineering, 2021. 153: p. 107077.
  • Schmidt, G., Scheduling on semi-identical processors. Zeitschrift für Operations Research, 1984. 28(5): p. 153-162.
  • [30] Gharbi, A. and M. Haouari, Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics, 2005. 148(1): p. 63-87.
  • Aggoune, R., Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research, 2004. 153(3): p. 534-543.
  • Mauguiere, P., J.-C. Billaut, and J.-L. Bouquard, New single machine and job-shop scheduling problems with availability constraints. Journal of scheduling, 2005. 8(3): p. 211-231.
  • 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.
  • Zribi, N., A. El Kamel, and P. Borne, Minimizing the makespan for the MPM job-shop with availability constraints. International Journal of Production Economics, 2008. 112(1): 151-160.
  • Wang, S. and J. Yu, An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Computers & Industrial Engineering, 2010. 59(3): p. 436-447.
  • Moradi, E., S.F. Ghomi, and M. Zandieh, An efficient architecture for scheduling flexible job-shop with machine availability constraints. The International Journal of Advanced Manufacturing Technology, 2010. 51(1-4): p. 325-339.
  • نهاوندی، نسیم و عباسیان، محمد (1390). مسأله زمان‌بندی کار کارگاهی چندهدفی انعطاف‌پذیر پویا با درنظر گرفتن محدودیت نگهداری و تعمیرات، نشریه بین المللی مهندسی صنایع و مدیریت تولید, جلد 22، شماره 1، صفحه 26-13.
  • Dalfard, V.M. and G. Mohammadi, Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints. Computers & Mathematics with Applications, 2012. 64(6): p. 2111-2117.
  • نمازی، علی و گلمکانی، حمیدرضا (1391). زمان‌بندی کار کارگاهی چندمسیره با درنظر‌گرفتن محدودیت نگهداری و تعمیرات (نت)، نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، جلد 23، شماره 4، صفحه 470-459.
  • Ziaee, M., An efficient heuristic algorithm for flexible job shop scheduling with maintenance constraints. Applied Mathematics and Sciences: An International Journal (MathSJ), 2014. 1(1): p. 19-31.
  • مرتضوی، جواد و همکاران (1397). ارائه مدل ریاضی برای مسأله زمان‌بندی کار کارگاهی انعطاف‌پذیر با محدودیت دسترسی به ماشین‌ها، نخبگان علوم و مهندسی، دوره 3، شماره 1، صفحه 52-61.
  • Branda, A., et al., Metaheuristics for the flow shop scheduling problem with maintenance activities integrated. Computers & Industrial Engineering, 2021. 151: p. 106989.
  • Chen, D.-S., R.G. Batson, and Y. Dang, Applied integer programming. Hoboken, NJ, 2010.
  • Lei, D., et al., An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling. International Journal of Production Research, 2020. 58(2): p. 597-614.
  • Li, M., D. Lei, and J. Cai, Two-level imperialist competitive algorithm for energy-efficient hybrid flow shop scheduling problem with relative importance of objectives. Swarm and Evolutionary Computation, 2019. 49: p. 34-43.
  • Karimi, S., et al., Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm. Applied mathematical modellíng, 2017. 41: p. 667-682.
  • Sadeh, D.H., M. Nooraie, and B. Hajikarimi, Billboard advertising optimization by using imperialist competitive algorithm (Case study: Tehran city). African Journal of Business Management, 2013. 7(36): p. 3706-3713.
  • Biabangard-Oskouyi, A., et al., Application of imperialist competitive algorithm for materials property characterization from sharp indentation test. International Journal of Engineering Simulation, 2009. 10(1): p. 11-12.
  • Atashpaz-Gargari, E. and C. Lucas. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. in 2007 IEEE congress on evolutionary computation. 2007. Ieee
  • قندی بیدگلی، سمیه و کریمی، فرزانه (1399). یک رویکرد بهینه‌سازی مبتنی‌بر شبیه‌سازی جهت بالانس خط مونتاژ دوطرفه مختلط در شرایط تصادفی بودن زمان انجام کارها (مطالعه موردی: شرکت به آفرینان داتیس تیوا)، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، دوره 8، شماره 16، صفحه 213-199.
  • سلیمانی نیا، فاطمه و مهدی زاده، اسماعیل (1397). مدل‌سازی ریاضی و حل مسأله زمان‌بندی تولید کار کارگاهی انعطاف‌پذیر با جریان‌های معکوس، نشریه مهندسی صنایع (دانشکده فنی دانشگاه تهران)، دوره 52، شماره 1، صفحه 96-87 .
  • 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-1.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 10، شماره 21
اسفند 1401
صفحه 1-17

فایل ها

هم رسانی

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

آمار