ارائه مدل حل مسئله برنامه ‏ریزی زمانبندی کار کارگاهی چند مسیره سبز با هدف بهینه کردن زمان اتمام کا‏رها و مصرف انرژی با الگوریتم فراابتکاری وال

محورهای موضوعی : مدیریت صنعتی

سیمین عروجی ¹ , حجت نبوتی ²

1 - گروه مهندسی صنایع، واحد ساوه، دانشگاه آزاد اسلامی، ساوه، ايران
2 - گروه مهندسی صنایع، دانشگاه آزاد اسلامی واحد ساوه

تاریخ دریافت : 1403/01/12 تاریخ پذیرش : 1403/03/11 تاریخ انتشار : 1403/07/29

کلید واژه: الگوریتم بهینه سازی وال, برنامه‏ریزی کارکارگاهی, آلودگی محیط زیست, میزان مصرف انرژی,

چکیده مقاله :

مسئله مورد مطالعه در این پژوهش، بسط گسترده‏تری از مسئله کارکارگاهی چند مسیره می‌باشد که دارای ویژگی بررسی میزان مصرف انرژی می‌باشد. بدین ترتیب هدف تعیین توالی عملیات و تخصیص کار به ماشین‏ها بگونه‌ای است تا مجموع وزنی زمان تحویل کارها و همچنین میزان صرف انرژی کارها کمینه گردد. باید توجه داشت لحاظ فرض مذکور اگرچه موجب پیچیدگی بیشتر مسئله می‌گردد ولی شرایط را به محیط‏های تولیدی واقعی نزدیکتر می‌سازد. با توجه به پیچیدگی مسئله فوق و عدم امکان حل مسئله بصورت ریاضی، استفاده از الگوریتم های فراابتکاری مورد توجه قرارگرفت. در این‏ پژوهش به حل مسئله مدل غیرخطی با الگوریتم فراابتکاری مبتنی بر الگوریتم بهینه سازی گروه ذرات و الگوریتم وال پرداخته شده است. برای بررسی کارایی الگوریتم‏های بیان شده یکی از 30 مسئله معروف مورد بررسی قرار گرفته و کارایی هریک از الگوریتم‏های بیان شده مقایسه است و به این‏ نتیجه رسیدیم که به کمک الگوریتم وال ، نسبت به الگوریتم ازدحام ذرات زمان اتمام کلیه کارها در این مسئله کوتاه‏تر خواهد شد.

چکیده انگلیسی:

The sequence of work operations on production machines plays a crucial role in managing the volume of jobs in process and ensuring the timely fulfillment of customer demand. One of the most common production models is the workshop model. This research focuses on an extension of the multi-path job shop problem, specifically examining energy consumption, which is directly linked to environmental pollution. The objective is to determine the sequence of operations and assign jobs to machines in a way that minimizes the weighted sums of delivery time and energy consumption. It is important to note that while this assumption complicates the problem, it also aligns more closely with real-world production environments. Given the complexity of this issue and the time required to solve it exactly, this study emphasizes the use of meta-heuristic algorithms. We discuss the solution of the nonlinear model using two meta-heuristic algorithms: the Particle Swarm Optimization (PSO) algorithm and the Wall algorithm. To evaluate the effectiveness of these algorithms, we examined one of the 30 well-known benchmark problems. Our findings indicate that the Wall algorithm reduced the total time to complete all tasks by 18% compared to the Particle Swarm Optimization algorithm. The proposed Wall algorithm demonstrates superior capability in solving these complex problems. Moreover, in terms of CPU time, both algorithms produced satisfactory results within an acceptable timeframe.

منابع و مأخذ:

Abedini, A., Li, W., Badurdeen, F., & Jawahir, I. (2020). A metric-based framework for sustainable production scheduling. Journal of Manufacturing Systems, 54, 174-185.
Aggoune, R. (2004). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research, 153(3), 534-543.
Amiri, M. F., & Behnamian, J. (2020). Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm. Journal of cleaner production, 251, 119734.
Breit, J. (2006). A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint. Computers & Operations Research, 33(8), 2143-2153.
Girish, B., & Jawahar, N. (2009). Scheduling job shop associated with multiple routings with genetic and ant colony heuristics. International journal of production research, 47(14), 3891-3917.
Golmakani, H. R., & Birjandi, A. R. (2014). Multiple route job shop scheduling using particle swarm optimisation approach. International Journal of Procurement Management, 7(2), 119-144.
Golmakani, H. R., & Namazi, A. (2014). An artificial immune algorithm for multiple-route job shop scheduling problem with preventive maintenance constraints. International Journal of Operational Research, 19(4), 457-478.
Jabbarizadeh, F., Zandieh, M., & Talebi, D. (2009). Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints. Computers & Industrial Engineering, 57(3), 949-957.
Kubzin, M. A., & Strusevich, V. A. (2006). Planning machine maintenance in two-machine shop scheduling. Operations Research, 54(4), 789-800.
Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. Advances in engineering software, 95, 51-67.
Moradi, E., Fatemi Ghomi, S., & Zandieh, M. (2010). An efficient architecture for scheduling flexible job-shop with machine availability constraints. The International Journal of Advanced Manufacturing Technology, 51, 325-339.
Nabovati, H. (2021). A Developed Cuckoo Search Algorithm for Solving a new Model of the Machine and Vehicle Scheduling. Journal of Strategic Management in Industrial Systems, 16(56), 48 to 56.
Nabovati, H., Haleh, H., & Vahdani, B. (2020). Multi-objective invasive weeds optimisation algorithm for solving simultaneous scheduling of machines and multi-mode automated guided vehicles. European Journal of Industrial Engineering, 14(2), 165-188. doi:10.1504/ejie.2020.105696
Naderi, B., Zandieh, M., & Aminnayeri, M. (2011). Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Applied Soft Computing, 11(2), 2094-2101.
Naderi, B., Zandieh, M., & Fatemi Ghomi, S. (2009). Scheduling sequence-dependent setup time job shops with preventive maintenance. The International Journal of Advanced Manufacturing Technology, 43, 170-181.
Ruiz, R., García-Díaz, J. C., & Maroto, C. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research, 34(11), 3314-3330.
Saddikuti, V., & Pesaru, V. (2019). NSGA based algorithm for energy efficient scheduling in cellular manufacturing. Procedia Manufacturing, 39, 1002-1009.
Yang, D.-L., Hsu, C.-J., & Kuo, W.-H. (2008). A two-machine flowshop scheduling problem with a separated maintenance constraint. Computers & Operations Research, 35(3), 876-883.
Zribi, N., El Kamel, A., & Borne, P. (2008). Minimizing the makespan for the MPM job-shop with availability constraints. International Journal of Production Economics, 112(1), 151-160.

متن کامل:



 

 

 

 

 

 

ارائه مدل حل مسئله برنامه‏ریزی زمانبندی کارکارگاهی چند مسیره سبز
 با هدف بهینه کردن زمان اتمام کا‏رها و مصرف انرژی
 با الگوریتم فراابتکاری وال

 

سیمین عروجی

 گروه مهندسی صنایع، واحد ساوه، دانشگاه آزاد اسلامی، ساوه، ايران

حجت نبوتی (نویسنده مسؤل)

دانشیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی شرق، دانشگاه گیلان، رودسر، ایران

Email: [e-mail]     

 

                     تاریخ دریافت: 12/01/1403  * تاریخ پذیرش 11/03/1403

 

         چکيده

توالی عملیات کارها بر روی ماشین‏آلات تولید نقش انكار ناپذیر در حجم کار درجریان ساخت و برآورده کردن به موقع تقاضای مشتریان دارد. یكی از رایج ترین مدلهای تولیدی، مدلهای کارکارگاهی هستند. مسئله مورد مطالعه در این پژوهش، بسط گسترده‏تری از مسئله کارکارگاهی چند مسیره می‌باشد که دارای ویژگی بررسی میزان مصرف انرژی که ارتباط مستقیم با آلودگی محیط زیست دارد، می‌باشد. بدین ترتیب هدف تعیین توالی عملیات و تخصیص کار به ماشین‏ها بگونه‌ای است تا مجموع وزنی زمان تحویل کارها و همچنین میزان صرف انرژی کارها کمینه گردد. باید توجه داشت لحاظ فرض مذکور اگرچه موجب پیچیدگی بیشتر مسئله می‌گردد ولی شرایط را به محیط‏های تولیدی واقعی نزدیکتر می‌سازد. با توجه به پیچیدگی مسئله فوق و زمان بر بودن حل مسئله بصورت دقیق، استفاده از الگوریتم های فراابتکاری مورد توجه قرارگرفت. در این‏ پژوهش به حل مسئله مدل غیرخطی با الگوریتم فراابتکاری مبتنی بر الگوریتم بهینه سازی گروه ذرات و الگوریتم وال پرداخته شده است. برای بررسی کارایی الگوریتم‏های بیان شده یکی از 30 مسئله معروف مورد بررسی قرار گرفته و به این‏ نتیجه خواهیم رسید که به کمک الگوریتم وال، نسبت به الگوریتم ازدحام ذرات زمان اتمام کلیه کارها با در نظر گرفتن مصرف انرژی 18 درصد کمینه شده است که این‏ نشان دهنده توانایی بالاتر الگوریتم پیشنهادی در حل این مساله می‏باشد و همچنین در خصوص زمان حل هر دو الگوریتم در زمان قابل قبول به نتایج مورد نظر دست یافتند.

کلمات کلیدی: الگوریتم بهینه سازی وال، برنامه‏ریزی کارکارگاهی، آلودگی محیط زیست، میزان مصرف انرژی.

 

 

 

 

 

 

 

 

 

 

1-        مقدمه

 در حل مسائل زمان بندی همواره به این نکته توجه می‏شود که از آنجا که زمان پردازش و تکمیل یک سفارش برابر با بزرگترین زمان پایان رسیدن کار درون آن سفارش است، هدف کمینه کردن زمان تکمیل هرکار و ارسال سفارشات در کوتاهترین زمان می‌باشد. مسئله­ی زمان‏بندی کار کارگاهی تعیین برنامه زمان‏بندی تعدادی عملیات در محیط چند ماشینه است که در آن هر کار مسیر معینی برای پردازش دارد و ممکن است در طول یک مسیر بیش از یک بار به یک ماشین برخورد کند. زمان‏بندی کار کارگاهی شامل سه حالت تک مسیره ، چند مسیره  و انعطاف‏پذیر  می‌شود. در مدل کلاسیک زمان‏بندی کار کارگاهی باید n کار بر روی  mماشین غیرمرتبط تکمیل شوند. تمامی ماشین‏ها از ابتدای افق برنامه‏ریزی در دسترس بوده و قطع فعالیت‌ها مجاز نیست. این مسئله در زمره¬ی مسائل سخت¹ طبقه بندی می‌شود (Nabovati, 2021). تعمیم وسیعتر مسئله کار کارگاهی، مسئله کار کارگاهی چند مسیره است که در آن هر کار می‏تواند از مسیرهای متفاوتی عبور کرده و به اتمام برسد. لزوماً تعداد ماشین‏ها در مسیرهای مختلف برای یک کار برابر نیست. این ساختار در اغلب واحدهای تولیدی منعطف، که در آنها ماشین‏های کنترل عددی قادر به انجام عملیات متفاوتی از یک کار هستند، مشاهده می‌شود. 

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

2- روش ‎شناسی پژوهش

نمونه­هایی از مطالعاتی که پیش از این در زمینه کارکارگاهی به انجام رسیده، در ادامه بیان می‌شود. اگونی² (2004) با استفاده از یک الگوریتم یك جستجو بر مبنای الگوریتم ژنتیک و جستجوی ممنوعه حل مسئله زمان‏بندی ‏جریان کارگاهی با محدودیت نگهداری و تعمیرات پرداخته است که در آن هدف کمینه‏سازی زمان تكمیل کل کارها است. کوبزن و استروسویچ³ (2006) مسئله جریان کارگاهی دو ماشینه به منظور مینیمم کردن حداکثر زمان تكمیل کارها را با فرض اینكه مدت زمان نگهداری و تعمیرات ماشین‏ها به دوره‏ی شروع نگهداری و تعمیرات آنها بستگی دارد، مورد بررسی قرار داده‏اند. بیری⁴ (2006) نیز مسئله زمان‏بندی ‏جریان کارگاهی دو ماشینه وقتی ماشین اول برای یک فاصله زمانی داده شده در دسترس نیست با هدف کمینه‏سازی حداکثر زمان تكمیل کارها مورد مطالعه قرار داده است. رویز⁵ وهمكارانش (2007) مسئله جریان کارگاهی با سه سیاست متفاوت در نگهداری و تعمیرات ماشین‏ها در نظر گرفته و شش روش ابتكاری و فراابتکاری برای حل آن ارائه نموده‏اند. زریب⁶ وهمكارانش(2008)مسئله کارکارگاهی با در نظرگرفتن محدودیت دسترسی روی ماشین‏ها، مورد مطالعه قرار داده‏اند. آنها در مرحله اول یک الگوریتم ابتكاری برمبنای قاعده اولویت برای حل مسئله تخصیص ارائه کرده‌اند که می تواند با الگوریتم جستجوی ممنوعه جواب داده شود. در مرحله دوم یک الگوریتم ژنتیک برای حل مسئله توالی ارائه شده است. یانگ⁷ و همكارانش (2008) مسئله جریان کارگاهی دو ماشینه با این‏ فرض که فعالیت نگهداری و تعمیرات باید در یک زمان ثابت بعداز تكمیل حداقل یک تعداد ثابت از کارها انجام شود، با هدف کمینه‏سازی حداکثر زمان تولید مورد مطالعه قرارداده‏اند. نادری⁸ و همكارانش (2009) مسئله زمان‏بندی ‏کارکارگاهی با زمان آماده سازی وابسته به توالی و محدودیت عدم دسترسی روی ماشین‏ها به منظور مینیم کردن حداکثر زمان تولید با استفاده از دو الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک مورد مطالعه قرار داده‏اند. جباری زاده⁹ و همكارانش (2009) نیز مسئله جریا ن کارگاهی انعطاف پذیر با زمان آماده سازی وابسته به توالی و با لحاظ سه سیاست نگهداری و تعمیرات با استفاده از دو الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک مورد بررسی قرار داده‏اند. گریش¹⁰ و جواهر (2009)، مسئله زمان‏بندی کار کارگاهی چندمسیره، توسط دو روش فراابتکاری، الگوریتم ژنتیک  و الگوریتم کلونی مورچگان، برای جایابی بهینه­ی عملیات­ها به ماشین‏ها با معیار زمان اتمام کار کمینه ارایه کرده اند، در پژوهش ایشان همزمان حل با دو الگوریتم فراابتکاری به حل مسئله می­پردازد که در نتیجه رقابت به زمان حل بین الگوریتم های فراابتکاری برمی‌گردد. مرادی¹¹ و همكارانش (2010) مسئله کارکارگاهی انعطاف‏پذیر با در نظرگرفتن محدودیت دسترسی روی ماشین‏ها، مورد مطالعه قرار داده‏اند. آنها مسئله خود را با الگوریتم ژنتیک حل کردند. نادری¹² و همكارانش (2011) نیز مسئله زمان‏بندی ‏جریان کارگاهی انعطاف پذیر با لحاظ نگهداری و تعمیرات دور های و با هدف حداقل کردن حداکثر زمان تولید مورد مطالعه قرار داده‏اند. آنها دو روش فراابتکاری الگوریتم سیستم ایمنی مصنوعی و الگوریتم ژنتیک برای حل مسئله مذکور ارائه کرده‌اند. حمیدرضا گلمكانی و علی بیرجندی¹³ (2014) به بررسی مسئله کارکارگاهی چند مسیره و با ارائه یک الگوریتم ابتكاری با هدف کمینه سازی زمان اتمام تمام کارها، با استفاده از الگوریتم ابتكاری انتقال گلوگاه، به ارزیابی 43مسئله مشهور در این‏ زمینه می پردازند. حمیدرضاگلمكانی و علی نمازی¹⁴ (2014) مدل جدیدی را برای کارکارگاهی چند مسیره با لحاظ تعمیرات ونگهداری دورهای ثابت و همچنین‏ تعمیرات و نگهداری وابسته به عمر ماشین‏ها، معرفی و به حل آن با روش فراابتکاری سیستم ایمنی مصنوعی پرداختند. ایشان در این‏ پژوهش به بررسی مسائل زمان‏بندی کارکارگاهی چند مسیره در دو حالت با لحاظ کردن تعمیرات و نگهداری و بدون لحاظ کردن آن پرداخته شده است. در نهایت، تعریف مسئله‏ی زمان‏بندی ‏کارکارگاهی چند مسیره با لحاظ تعمیرات و نگهداری انعطاف‏پذیر نیز معرفی و مدل ریاضی آن بیان می‏شود. نتایج حاصل از برتری الگوریتم پیشنهادی بر روی تعدادی از مسائل طراحی شده نیز در انتهای آورده شده‌است. 

سدیکوتی و پسورا¹⁵ (2019) روش‌هایی را برای زمان‏بندی در محیط تولید از جمله تولید سلولی پیشنهاد کرده‌اند. با این حال، مطالعات بسیار کمی در زمینه تولید سلولی با تمرکز بر به حداقل رساندن طول عمر، جریان و مصرف مورد بررسی قرار گرفته است. لذا محققان پیشنهاد می کنند الگوریتم ژنتیک چند هدفه نامغلوب برای برنامه‏ریزی کارآمد انرژی به دلیل تمرکز بر شیوه‏های تولید پایدار و همچنین تأثیرات زیست محیطی اهمیت پیدا کند. همچنین محققان یادآور می شوند که عملکرد عملیاتی سیستم های تولید سلولی بستگی به درصد از دست رفته عملیات و روش برنامه‏ریزی دارد. عابدینی¹⁶ و همکاران (2020)  ناهماهنگی‏هایی در برنامه‏ریزی فروشگاه جریان بین سه هدف به ترتیب به حداقل رساندن کل زمان تکمیل، حداکثر زمان اتمام و واریانس زمان اتمام را بررسی کردند. تجزیه و تحلیل کنترل آماری فرآیندایشان نشان داد که توازن مبادله، کنترل بهتری بر اهداف فردی از نظر متوسط سیستم های تولید چابک و قابل تنظیم مجدد برای مقابله با محصولات و خانواده های مختلف محصولات ایجاد می‏کند. برای طراحی و بهینه سازی سیستم‏های تولید و همچنین انتخاب مطابقت محصول مطلوب، روشهای تجزیه و تحلیل محصول مورد نیاز است. خانواده‏های مختلف محصولات ممکن است از نظر تعداد و ماهیت اجزاء تفاوت زیادی داشته باشند. این واقعیت مانع از مقایسه کارآمد و انتخاب ترکیبات مناسب خانواده محصول برای سیستم تولید شد و روش جدیدی برای تجزیه و تحلیل موجود پیشنهاد شده است. فرجی امیری و بهرامیان¹⁷ (2021)در بحث کارهای کارگاهی که درآن  به بررسی کارکارگاهی انعطاف پذیر با وجود حالت چند سرعته ماشین آلات و میزان مصرف مختلف می پردازد. در جدول 1 به بررسی مقایسه پژوهاشهای انجام شده می پردازیم و مقایسه پژوهش حاضر را در انتهای جودل نشان خواهیم داد.

جدول شماره (1): مقایسه پژوهش های انجام شده کار کارگاهی

روش حل	تابع هدف	نوع مساله	سال	نام محققان
کمینه‏سازی زمان تكمیل کل کارها	الگوریتم ژنتیک و جستجوی ممنوعه	مسئله زمان‏بندی ‏جریان کارگاهی با محدودیت  نگهداری  و تعمیرات	2004	اگونی
کمینه‏سازی حداکثر زمان تكمیل کارها	حل دقیق	مسئله زمان‏بندی ‏جریان کارگاهی دو ماشینه	2006	بیری
کمینه‏سازی حداکثر زمان تكمیل کارها	روش ابتكاری	مسئله جریان کارگاهی	2007	رویز  وهمكاران
کمینه‏سازی حداکثر زمان تكمیل کارها	الگوریتم جستجوی ممنوعه ، الگوریتم ژنتیک	مسئله کارکارگاهی با در نظرگرفتن محدودیت دسترسی روی ماشین‏ها	2008	زریب و همکاران
کمینه‏سازی حداکثر زمان تولید	حل دقیق	مسئله جریان کارگاهی دو ماشینه	2008	یانگ
مینیم کردن حداکثر زمان تولید	الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک	مسئله زمان‏بندی ‏کارکارگاهی با زمان آماده سازی وابسته به توالی	2009	نادری و همكارانش
کمینه‏سازی حداکثر زمان تكمیل کارها	الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک	مسئله جریا ن کارگاهی انعطاف پذیر با زمان آماده سازی وابسته به توالی	2009	جباری زاده  و همكارانش
کمینه‏سازی حداکثر زمان تكمیل کارها	الگوریتم ژنتیک  و الگوریتم کلونی مورچگان	مسئله زمان‏بندی کار کارگاهی چندمسیره	2009	گریش  و جواهر
کمینه‏سازی حداکثر زمان تكمیل کارها	الگوریتم ژنتیک	مسئله کارکارگاهی انعطاف‏پذیر با در نظرگرفتن محدودیت دسترسی روی ماشین‏ها	2010	مرادی  و همكارانش
حداقل کردن حداکثر زمان تولید	الگوریتم سیستم ایمنی مصنوعی و الگوریتم ژنتیک	مسئله زمان‏بندی ‏جریان کارگاهی انعطاف پذیر با لحاظ نگهداری و تعمیرات	2011	نادری و همكارانش
کمینه سازی زمان اتمام تمام کارها	الگوریتم ابتكاری انتقال گلوگاه	مسئله کارکارگاهی چند مسیره	2014	حمیدرضا گلمكانی و علی بیرجندی
کمینه‏سازی حداکثر زمان تكمیل کارها	الگوریتم سیستم ایمنی مصنوعی	مسئله کارکارگاهی چند مسیره با لحاظ تعمیرات ونگهداری دورهای ثابت	2014	حمیدرضاگلمكانی و علی نمازی
حداقل رساندن طول عمر، جریان و مصرف	الگوریتم ژنتیک چند هدفه نامغلوب	زمان‏بندی در محیط تولید	2019	سدیکوتی و پسورا
حداقل رساندن کل زمان تکمیل، حداکثر زمان اتمام و واریانس زمان اتمام	الگوریتم ژنتیک چند هدفه نامغلوب	مسئله زمان‏بندی کار کارگاهی چندمسیره	2020	عابدینی  و همکاران
حداقل رساندن کل زمان تکمیل ماشین	الگوریتم ابتکاری	مسئله کارکارگاهی انعطاف پذیر	2021	فرجی امیری و بهرامیان
کاهش زمان تکمیل با در نظر گرفتن مصرف انرژی	الگوریتم جدید فراابتکاری وال و الگوریتم ازدحام ذرات	مسئله کارکارگاهی سبز با در نظر گرفتن مصرف انرژی	2023	پژوهش حاضر

 

در این پژوهش به دنبال مدل جدیدی هستیم که می‏تواند به صورت مستقیم در صنایعی که شامل تولید کارگاهی هستند مورد استفاده قرار گیرد. همچنین این مدل به عنوان اولین مدل مطرح شده در سیستم سبز کار کارگاهی مورد بررسی است و می تواند شروع جدیدی برای سیستم های بعدی باشد. یک مدل جدید‏تر که فرضیه­ی مطرح شده در مدل پیشین را به مدل واقعی در صنعت نزدیک‏تر می­کند مورد بررسی قرار می­ گیرد، این مدل می تواند در سیستم های تولیدی کارگاهی که شرایط فوق الذکر مطرح شده در مدل را دارند به طور مستقیم مورد بررسی قرار گیرد. و همچنین روش حل جدید الگوریتم فراابتکاری وال با کارایی بالا جهت حل بهینه مسئله بکار گرفته شده و با الگوریتم ازدحام ذرات نتایج مقایسه شده است.

الف) تعاریف و فرضیه ها و علائم

در تمامی مسائل زمان بندی، تعدادی کار و تعدادی ماشین محدود در نظر گرفته می‏شوند‏. n تعداد کارها و m تعداد ماشین ها بوده وi  اندیس کارها و j اندیس مربوط به ماشین‏ها می‌باشد. در مسائل زمان‏بندی ‏فرضیه های مختلفی برای ماشین‏ها و کارها در نظر گرفته شده که در ادامه به بررسی آنها می پردازیم.

•       هیچ ماشینی در یک زمان نمی‏تواند بیش از یک کار را پردازش نماید و هر کار که فرآیندش روی ماشین شروع شود تا اتمام دسته ی مورد نظر آن فرآیند روی همان ماشین قرار دارد.

•       زمانی که عملیات یک کار روی ماشین شروع می‏شود، تا اتمام آن عملیات، عملیات دیگری روی آن ماشین صورت نمی گیرد مگر اینكه در مسئله حالت وقفه تعریف کنیم.

•       ماشین‏ها در طول فرآیند می توانند دچار بیكاری شوند.

•       هیچ ماشینی در طول فرآیند خراب نمی‌شود و همواره در دسترس است.

•       از هر ماشین فقط یک عدد وجود دارد و اجازه نمی دهیم که یک کار برای پردازش ماشینی را از بین ماشین‏ها انتخاب کند مگر اینكه فرض وجود ماشین‏های موازی را تعریف کنیم.

•       تمام کارها شناخته شده‌اند و قبل از زمان‏بندی ‏سازماندهی لازم برای آنها صورت گرفته است.

•       تمام کارها از نظر ارزش با یكدیگر برابر هستند و تمام آنها باید فرآیندهای خود را به اتمام برسانند.

•       هر کاری باید به ماشین مربوطه در اولین زمان ممکن تخصیص یابد تا فرآیندش شروع شود.

•       زمآنهای فرآیند مستقل از زمان‏بندی و نحوه قرار گرفتن کارها در ترتیب مربوطه هستند.

•       اگر یک کار شامل عملیات مختلفی روی ماشین‏های مختلف باشد، هیچگاه نمی‏توانیم دو عملیات پشت سر هم آن کار را به طور همزمان اجرا کنیم

•       زمانی که جهت حمل و نقل کارها بین ماشین‏ها صرف می‌شود قابل صرف نظر کردن است یا به عنوان بخشی از زمان فرایند آن کار روی ماشین قبلی فرض می‏شود.

•       زمان آماده سازی ماشین‏ها برای کارهای متفاوت قابل صرف نظر کردن است و یا به صورت بخشی از فرآیند تعریف می‏شود.

ب) مدل ریاضی

مدل ریاضی مسئله زمان‏بندی کار کارگاهیِ چند مسیره، یک مدل از نوع برنامه‌ریزی غیر خطی عدد صحیح می‌باشد. فرض کنید  معرف تعداد کارها و معرف تعداد ماشین‏ها باشد. برای انجام هر کار  چندین مسیر وجود دارد. تعداد کل مسیرهای کار  را با  و تعداد کل عملیات کار  در مسیر  را با  نشان می‌دهیم.  معرف ماشین مورد نیاز برای انجام عملیات  ام از کار  ام در مسیر  ام و  زمان مورد نیاز برای انجام عملیات  ام از کار  ام در مسیر  ام روی ماشین  ام است.ECi   هزینه انرژی الکتریکی و Tikj زمان مورد نیاز ماشین j برای عملیات k از کار i است. متغیرهای تصمیم‌گیریِ زمان شروع و ختم عملیات  ام از کار  ام در مسیر  ام را به ترتیب با  و  نشان می‌دهیم. جهت مدل‌سازی مسئله، سه نوع متغیر صفر و یک به شرح زیر تعریف می‌شود:

مدل کامل مسئله زمان‏بندی کار کارگاهیِ چند مسیره بصورت زیر خواهد بود:

اگر عملیات  ام از کار  ام در مسیر  زودتر از عملیات  ام از کار  ام در مسیر  انجام شود مقدار یک و در غیر اینصورت صفر
عملیات  ام از کار  ام در مسیر  ام به ماشین  ام اختصاص یابد مقدار یک و در غیر اینصورت صفر
اگر کار  به مسیر  اختصاص یابد مقدار یک و در غیر اینصورت صفر

مجموعه معادلات (2)، صرفاً یک مسیر از میان مسیرهای مختلف را به هرکار تخصیص می‌دهد. مجموعه نامعادلات (3) موجب می‌شود تا هر یک از عملیات تنها وقتی شروع شود که عملیات قبلی‌اش تکمیل شده باشد. مجموعه نامعادلات (4) موجب می‌شود تا زمان اتمام عملیات آخر از هر یک از کارها کمتر یا مساوی با زمان انجام کلیه کارها، ، باشد. مجموعه معادلات (5) تضمین می‌کند تا بین زمان شروع و زمان تکمیل یک کار هیچ توقفی صورت نگیرد. مجموعه معادلات (6) ماشین‏های مورد نیاز برای تکمیل عملیات کارها در یک مسیر مشخص شده را، تعیین می‌کند. مجموعه نامعادلات (7) و (9) با هم تضمین می‌کنند که دو عملیات مختلف از دو کار مختلف بر روی یک ماشین خاص بصورت همزمان صورت نگیرد. معادله )8( به هزینه ی وابسته به زمان و انرژی صرف شده به ازای هر ماشین ساعت را محاسبه می‏کند و در نهایت (10) و (11) نیز معرف نوع متغیرهای تصمیم‌گیری هستند.

ج) روش حل: الگوریتم بهینه سازی وال¹⁸

وال‏ها موجوداتی فوق العاده هستند. آنها به عنوان بزرگترین پستانداران جهان شناخته می‏شوند. وال بالغ می‏تواند تا 30 متر طول و 180 تن وزن داشته باشد. گونه اصلی مختلف از این‏ پستانداران غول پیكر مانند قاتلان، مینک، سای، گاو، راست باله و آبی وجود دارد. وال‏ها بیشتر به عنوان شكارچیان در نظر گرفته می‏شوند. آنها هرگز نمی‏خوابند زیرا باید از سطح اقیانوس ها نفس بكشند. درحقیقت، نیمی از مغز فقط میخوابد. نكته جالب در مورد وال‏ها این‏ است که آنها به عنوان حیوانات بسیار باهوش و دارای احساساس در نظر گرفته می‏شوند. مطابق گفته هاف ون دره گچ ¹⁹، وال ها در مناطقی از مغز خود مانند سلولهای دوقلو، سلولهای مشترکی دارند. این‏ سلول ها مسئول قضاوت، احساساس و رفتارهای اجتماعی در انسانها هستند. به عبارت دیگر سلولهای چرخش ما را از موجودات دیگر متمایز می‏کند. وال ها دو برابر از این‏ سلول ها نسبت به انسان بالغ دارند که عامل اصلی هوشمندی آنهاست. ثابت شده است که وال همانطور که انسان می‏تواند فكر کند، یاد بگیرد، قضاوت کند، ارتباط برقرار کند و حتی احساساتی شود، اما بدیهی است که از سطح هوشمندی بسیار پایین تری برخوردار است. مشاهده شده است که وال‏ها (غالباً والهای قاتل) قادر به توسعه گویش خود هستند. نكته جالب دیگر رفتار اجتماعی وال‏ها است. آنها به تنهایی یا گروهی زندگی می کنند. البته، آنها بیشتر درگروه مشاهده می‏شوند. بعضی از گونه های آنها (به عنوان مثال وال‏های قاتل) در تمام مدت زندگی خود می‏توانند در یک خانواده زندگی کنند. یکی از بزرگترین وال‏ها، وال کوهان دار²⁰  است. یک وال کوهان دار بزرگسال تقریبا به اندازه یک اتوبوس مدرسه است. طعمه­های مورد علاقه آن­ها گله ماهی کریل و کوچک هستند. جالب ترین چیز در مورد وال کوهان دار نحوه شکار خاص او است. این فرایند یافتن غذا روش تغزیه شبکه حبابی نامیده می‌شود. در واقع وال ترجیح می­دهد دسته ماهی های کوچک نزدیکتر به سطح اب را شکار کند. مشاهده شده است که این روش تغذیه با ایجاد حباب های متمایز دایره ای انجام می‌شود. وال‏ها حدود 12 متر به سمت پایین شیرجه رفته و با ایجاد حباب هایی به شکل مارپیچی در اطراف طعمه به سمت سطح شنا می­کنند، دانشمندان دو مانور مرتبط با شبکه حبابی را مشخص کرده و آن­ها را مارپیچ به سمت بالا ²¹ و حلقه های دوتایی²² نامیدند. این روش تغذیه روش خاصی است که تنها در وال‏ها دیده شده است. در الگوریتم وال مانور مارپیچ شبکه­ی حبابی به صورت ریاضی برای انجام بهینه سازی مدل شده است (Mirjalili & Lewis, 2016).

 

 

شکل شماره (1): نحوه‏ی شكار کردن طعمه توسط وال کوهان دار

الگوریتم بهینه سازی وال با مجموعه ای از جواب های تصادفی شروع می‌شود. در هر مرحله عامل­های جستجو موقعیت خود را باتوجه به انتخاب تصادفی عامل جستجو یا بهترین جواب بدست آمده قبلی به روز می­کنند. برای بدست آوردن به ترتیب فاز جستجو و استخراج پارامتر a از 2 به 0 کاهش میابد. برای به روز رسانی عامل های جستجو یک عامل جستجو به طور تصادفی زمانیکه  است انتخاب می‌شود، در حالیکه بهترین جواب زمانیکه  است انتخاب می‌شود. با توجه به مقدار p الگوریتم بهینه سازی وال می‏تواند بین انتخاب مارپیچی یا دورانی سوییچ کند. سرانجام الگوریتم با ارضا شدن معیار توقف پایان میابد.

 

شکل شماره (2): شبه کد الگوریتم وال 

شبه کد الگوریتم وال در شکل 2 ارائه شده است. از نقطه نظر تئوری، الگوریتم وال می تواند به عنوان یک بهینه ساز کلی در نظر گرفته شود زیرا این‏ امر شامل قابلیت اکتشاف و بهره برداری است. علاوه بر این‏، مكانیسم پیشنهادی  این الگوریتم فضای جستجو را در همسایگی بهترین راه حل تعریف می‏کند و به سایر عوامل جستجو اجازه می دهد تا از بهترین سابقه موجود در آن دامنه بهره برداری کنند. تنوع سازگار بردار جستجو A به الگوریتم  وال اجازه میدهد تا به طور هموار بین اکتشاف و بهره برداری حرکت کند: با کاهشA، برخی از تكرارها به کاوش اختصاص می یابد و مابقی به بهره برداری اختصاص می یابد الگوریتم وال تنها دو پارامتر اصلی داخلی را برای تنظیم  A و C در بر می گیرد.

3-       نتایج و بحث

در این‏ قسمت از پژوهش، مسئله زمان‏بندی کارکارگاهی چند مسیره با هدف تعیین توالی انجام کارها بگونه‏ای که زمان اتمام کارها حداقل گردد، مورد بررسی قرار می‌گیرد. هر کار می‏تواند از مسیرهای متفاوتی عبور کرده و به اتمام رسد. تعداد ماشین‏هایی که یک کار در مسیرهای مختلف با آنها مواجه می‌شود لزوماً برابر نیست. به عبارت دیگر، ممکن است در یک مسیر، کارها، با عبور از دو ماشین‏ (هر ماشین‏ یک عملیات) به اتمام رسد ودر مسیری دیگری همان کار با عبور از چهار ماشین‏ (هر ماشین‏ یک عملیات و جمعاً چهار عملیات) انجام شود. واضح است که هر ماشین تنها یک عملیات در هر لحظه می‏تواند انجام دهد.

 در زیر یک نمونه مثال از جداول (Golmakani & Birjandi, 2014) آورده شده. همانطور که مشاهده می‌شود، مسئله زیر دارای7 کار می‌باشد. هر کدام از این‏7کار می‏تواند از دو مسیر1و2 حرکت کرده و پردازش شوند. هرکدام از این‏ مسیرها شامل چند عملیات می باشند که با Oi نشان داده شده‌اند. هر عملیات شامل کار توسط یک ماشین‏ است که در جدول زیر شماره‏ی هر کدام از ماشین‏ها و زمان مورد نیاز پردازش کار مربوطه برروی آن ماشین آورده شده است .

جدول شماره (2): اطلاعات مسئله کارکارگاهی چند مسیره

رابطه (1)
رابطه (2)
رابطه (3)
رابطه (4)
رابطه (5)
رابطه (6)
رابطه (7)
رابطه (8)
رابطه (9)
رابطه (10)
رابطه (11)

LRJSP: 7. 7. 17
		O1		O2		O3		O4		O5
J1	route 1	M1	21	M4	26	M2	17
	route 2	M3	19	M5	13	M6	15	M7	18
J2	route 1	M2	35	M6	32	M3	25	M5	23
	route 2	M5	21	M7	36	M4	25	M6	15	M1	13
J3	route 1	M4	23	M3	32	M2	18	M6	14
	route 2	M7	35	M2	15	M1	21	M4	18
	route 3	M6	25	M7	33	M4	27
J4	route 1	M1	26	M5	42	M4	27
	route 2	M3	21	M5	24	M2	22	M3	20	M1	14
J5	route 1	M2	37	M4	26	M6	43
	route 2	M5	32	M3	25	M1	19	M4	26
	route 3	M4	21	M7	13	M5	28	M3	32	M1	12
J6	route 1	M6	33	M2	36
	route 2	M7	12	M5	24	M4	25
	route 3	M3	24	M2	18	M4	13	M3	16
J7	route 1	M4	22	M2	14
	route 2	M5	18	M1	21

 مطابق جدول شماره 2 دارای هفت کار می باشیم. هر کار از چند مسیر قابل انجام می‌باشد که زمان پردازش مخصوص به خود را داراست، مثلا کار یک دارای دو مسیر می‌باشد که مسیر اول در اولین پردازش بر روی ماشین M1 قرار گرفته که زمان این پردازش 21 واحد زمانی می‌باشد، همچنین این پردازش یک هزینه نیز دارا ست ، این هزینه در جدول جداگانه هزینه هریک از ماشین آلات اعلام شده است. به این ترتیب، برای تمام هفت کار از هر مسیر برای هر پردازش، ماشین‏های مختلف با زمان و هزینه متفاوتی روبه رو خواهیم بود. در این پایان نامه به حل این مساله خواهیم پرداخت. با توجه به تعریف مسئله ی زمان‏بندی کارکارگاهیِ چند مسیره به دو زیر مسئله تخصیص مسیر (تخصیص مسیر به کارها (و تعیین توالی عملیات )تعیین توالی پردازش عملیات کارها روی هر ماشین( تجزیه می‌شود که زیر مسسله تخصیص مسیرها به کارها، به دلیل انعطاف‏پذیری ایجاد شده در کارکارگاهی به وجود می‏آید که شدیداً بر پیچیدگی مسئله می افزاید. هدف کمینه سازی حداکثر زمان تكمیل با سایر مفروضات زیر است.

·       هر ماشین در هر لحظه تنها می‏تواند یک عملیات را پردازش کند.

·       همه‏ی ماشین‏ها از زمان صفر در دسترس اند و خراب نمیشوند.

·       انبار پای کار، مجاز و ظرفیت آن نامحدود است.

·       زمانهای آماده سازی بین عملیات ناچیز است یا شامل زمان پردازش می‌شود و زمان حمل و نقل قابل چشم پوشی است.

·       قطع کردن عملیات مجاز نیست.

 جهت ارزیابی عملكرد الگوریتم‏های پیشنهاد شده، در این‏ قسمت از یک نمونه مسئله مطابق جدول 1 از مسائل (Golmakani & Birjandi, 2014) و توسط الگوریتم های وال و ازدحام ذرات حل شده است. برای کدنویسی و اجرای الگوریتم بكار گرفته شده از برنامه متلب 2018 استفاده شده است. پردازشگر اجرا کننده الگوریتم فرابتكاری، یک کامپیوتر با مشخصات اینتل 7 هسته 2.3 گیکا هرتز و رم 8 گیگا بایت می باشد.

الف) حل مسئله با الگوریتم فراابتکاری وال

نتایج حاصل از حل الگوریتم وال به صورت یک فایل اکسل می‏باشد که در جدول شماره 3 آمده است.

جدول شماره (3): خروجی اکسل حاصل از الگوریتم وال

J	R	O	M	St	Ft
5	1	1	2	0	8
5	1	2	4	8	12
5	1	3	6	12	17
5	1	4	9	17	17
5	1	5	9	17	17
2	1	1	2	8	34
2	1	2	6	34	46
2	1	3	3	46	76
2	1	4	5	76	106
2	1	5	9	106	106
7	1	1	4	12	40
7	1	2	2	40	53
7	1	3	9	106	106
1	1	1	1	0	25
1	1	2	4	40	74
1	1	3	2	74	90
1	1	4	9	106	106
3	3	1	6	46	64
3	3	2	7	64	87
3	3	3	4	87	105
3	3	4	9	106	106
6	3	1	3	76	100
6	3	2	2	100	113
6	3	3	4	113	118
6	3	4	3	118	138
4	1	1	1	25	40
4	1	2	5	106	129
4	1	3	4	129	142
4	1	4	9	142	142
4	1	5	9	142	142

به عنوان مثال برای سطر اول خواهیم داشت: کار شماره 5 ، مسیر شماره 1 را انتخاب می‏کند، این‏ کار در عملیات1 قرار دارد و از ماشین 2 استفاده می‏کند، زمان شروع کار آن روی ماشین 2 در زمان 0 و زمان پایان آن روی همان ماشین زمان 8 میباشد.

زمان اتمام کارها

ماشین­ها

 

                        شکل شماره (3): توالی عملیات  حاصل از الگوریتم وال

حل مسئله با الگوریتم فراابتکاری ازدحام ذرات: نتایج حاصل از حل الگوریتم ازدحام ذرات به صورت یک فایل اکسل می‏باشد که در جدول شماره 4 آمده است (Nabovati, Haleh, & Vahdani, 2020).

جدول شماره (4): خروجی اکسل حاصل از الگوریتم ازدحام ذرات

J	R	O	M	St	Ft
5	1	1	2	0	8
5	1	2	4	8	12
5	1	3	6	12	17
5	1	4	9	17	17
5	1	5	9	17	17
6	3	1	3	0	24
6	3	2	2	24	38
6	3	3	4	38	42
6	3	4	3	42	62
7	2	1	5	0	49
7	2	2	1	49	70
7	2	3	9	70	70
7	2	4	9	70	70
2	1	1	2	38	64
2	1	2	6	64	76
2	1	3	3	76	106
2	1	4	5	106	136
2	1	5	9	136	136
3	1	1	4	42	60
3	1	2	3	106	118
3	1	3	2	118	135
3	1	4	6	135	148
1	1	1	1	70	95
1	1	2	4	95	129
1	1	3	2	135	151
1	1	4	9	151	151
4	2	1	3	118	126
4	2	2	5	136	144
4	2	3	2	151	157
4	2	4	3	157	163
4	2	5	1	163	166

 

شکل شماره (4) توالی عملیات جواب های حاصل از الگوریتم ازدحام ذرات

ماشینها

زمان اتمام کارها

 

در نمودارهای گان بالا زمان اتمام کارها برای تمامی ماشین ها در هردو الگوریتم با رنگ قرمز مشخص‏ شده است. زمان اتمام کارها با الگوریتم ازدحام ذرات پرندگان برابر با 169 می باشد در حالیکه زمان اتمام کارها با الگوریتم وال برابر با 142 است. خط عمودی نمودار گان شماره ماشین و خط افقی زمان انجام کارها را نشان می دهد. روی هر یک از بخش های توالی نشان داده شده در نمودار گان شماره آن توالی نوشته شده است، برای مثال برای ماشین 2،O151   به این‏ معنی است که عملیات 1 مربوط به کار 5 از مسیر 1 حرکت می‏کند، این  عملیات روی ماشین 2 در لحظه 0 شروع شده و در زمان 8 به پایان می‏رسد. به همین ترتیب برای سایر بخش ها می‏توان توالی عملیات را تفسیرکرد.

 

شکل شماره (5): مقایسه زمان اتمام تمامی کارها با در نظر گرفتن مصرف انرژی در دو الگوریتم WOA و PSO

شكل 5 مقدار متوسط حاصل از حل  با دو روش را نشان میدهد. از آنجا که تابع هدف مسئله از نوع مینیمم سازی است، هر چه مقدار تابع هدف کمتر باشد، به جواب بهتری رسیده‏ایم.  همانطور که مشاهده می‏شود مقدار تابع هدف حاصل از الگوریتم وال پیشنهادی از مقدار کمتری نسبت  به حل با استفاده از الگوریتم ازدحام ذرات برخودار است که این‏ نشان دهنده توانایی بالاتر الگوریتم پیشنهادی در حل مسائل می‏باشد.

 

شکل شماره (6): مقایسه زمان حل مسئله توسط دو الگوریتم WOA و PSO

در شكل 6 متوسط زمان صرف شده برای حل توسط الگوریتم وال و الگوریتم ازدحام ذرات پیشنهادی باهم مقایسه شده است . این‏ نمودار به وضوح نشان میدهد که نرم افزار متلب برای حل الگوریتم ازدحام ذرات به زمان کمتری نیاز دارد.(3.76ثانیه) این‏ درحالتی است که زمان حل الگوریتم وال توسط نرم افزار متلب برابر با 5.04 ثانیه  می‏باشد.

پیشنهادات برای تحقیقات آینده

در اغلب مسائل زمان‏بندی، با هدف کاستن از پیچیدگی مسائل، بسیاری از شرایط و محدودیت‏های محیط‏های تولید واقعی نادیده گرفته می‏شود. در صورتیكه این‏ شرایط و محدودیت‏ها در مسائل زمان‏بندی ‏لحاظ شوند، برنامه‏ریزی حاصل، برنامه مفیدتر و موثرتری خواهد بود. البته شایان ذکر است که این‏ فرآیند موجب بسیارپیچیده‏تر شدن و سختر شدن حل مسئله می‏شود. موارد ذیل در این زمینه پیشنهاد می گردد:

·       اضافه کردن زمان‏های آماده سازی و توقفات وابسته فنی برای هر ماشین

·       در نظر گرفتن زمان‏های آماده سازی

·       لحاظ کردن محدودیت انبارها، تعمیرات نگهداری پیش‏بینانه و همچنین‏ زمان تعمیرات برای هرماشین.

4-       منابع

Abedini, A., Li, W., Badurdeen, F., & Jawahir, I. (2020). A metric-based framework for sustainable production scheduling. Journal of Manufacturing Systems, 54, 174-185.

Aggoune, R. (2004). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research, 153(3), 534-543.

Amiri, M. F., & Behnamian, J. (2020). Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm. Journal of cleaner production, 251, 119734.

Breit, J. (2006). A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint. Computers & Operations Research, 33(8), 2143-2153.

Girish, B., & Jawahar, N. (2009). Scheduling job shop associated with multiple routings with genetic and ant colony heuristics. International journal of production research, 47(14), 3891-3917. 

Golmakani, H. R., & Birjandi, A. R. (2014). Multiple route job shop scheduling using particle swarm optimisation approach. International Journal of Procurement Management, 7(2), 119-144.

Golmakani, H. R., & Namazi, A. (2014). An artificial immune algorithm for multiple-route job shop scheduling problem with preventive maintenance constraints. International Journal of Operational Research, 19(4), 457-478.

Jabbarizadeh, F., Zandieh, M., & Talebi, D. (2009). Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints. Computers & Industrial Engineering, 57(3), 949-957.

Kubzin, M. A., & Strusevich, V. A. (2006). Planning machine maintenance in two-machine shop scheduling. Operations Research, 54(4), 789-800. 

Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. Advances in engineering software, 95, 51-67.

Moradi, E., Fatemi Ghomi, S., & Zandieh, M. (2010). An efficient architecture for scheduling flexible job-shop with machine availability constraints. The International Journal of Advanced Manufacturing Technology, 51, 325-339.

Nabovati, H. (2021). A Developed Cuckoo Search Algorithm for Solving a new Model of the Machine and Vehicle Scheduling. Journal of Strategic Management in Industrial Systems, 16(56), 48 to 56.

Nabovati, H., Haleh, H., & Vahdani, B. (2020). Multi-objective invasive weeds optimisation algorithm for solving simultaneous scheduling of machines and multi-mode automated guided vehicles. European Journal of Industrial Engineering, 14(2), 165-188. doi:10.1504/ejie.2020.105696

Naderi, B., Zandieh, M., & Aminnayeri, M. (2011). Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Applied Soft Computing, 11(2), 2094-2101.

Naderi, B., Zandieh, M., & Fatemi Ghomi, S. (2009). Scheduling sequence-dependent setup time job shops with preventive maintenance. The International Journal of Advanced Manufacturing Technology, 43, 170-181.

Ruiz, R., García-Díaz, J. C., & Maroto, C. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research, 34(11), 3314-3330.

Saddikuti, V., & Pesaru, V. (2019). NSGA based algorithm for energy efficient scheduling in cellular manufacturing. Procedia Manufacturing, 39, 1002-1009.

Yang, D.-L., Hsu, C.-J., & Kuo, W.-H. (2008). A two-machine flowshop scheduling problem with a separated maintenance constraint. Computers & Operations Research, 35(3), 876-883. 

Zribi, N., El Kamel, A., & Borne, P. (2008). Minimizing the makespan for the MPM job-shop with availability constraints. International Journal of Production Economics, 112(1), 151-160. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Presenting a Problem-Solving Model for Green Multi-Route Workshop Scheduling with the Aim of Optimizing Work Completion Time and Energy Consumption with Whale's Meta-Heuristic Algorithm.

 

Simin Orji

Department of Industrial Engineering, Saveh Branch, Islamic Azad University, Saveh, Iran

Hojat Nabovati (Corresponding Author)

Department of Industrial Engineering, Saveh Branch, Islamic Azad University, Saveh, Iran

E-mail: [e-mail]

 

Abstract

The sequence of work operations on production machines plays a crucial role in managing the volume of jobs in process and ensuring the timely fulfillment of customer demand. One of the most common production models is the workshop model. This research focuses on an extension of the multi-path job shop problem, specifically examining energy consumption, which is directly linked to environmental pollution. The objective is to determine the sequence of operations and assign jobs to machines in a way that minimizes the weighted sums of delivery time and energy consumption. It is important to note that while this assumption complicates the problem, it also aligns more closely with real-world production environments. Given the complexity of this issue and the time required to solve it exactly, this study emphasizes the use of meta-heuristic algorithms. We discuss the solution of the nonlinear model using two meta-heuristic algorithms: the Particle Swarm Optimization (PSO) algorithm and the Wall algorithm. To evaluate the effectiveness of these algorithms, we examined one of the 30 well-known benchmark problems. Our findings indicate that the Wall algorithm reduced the total time to complete all tasks by 18% compared to the Particle Swarm Optimization algorithm. The proposed Wall algorithm demonstrates superior capability in solving these complex problems. Moreover, in terms of CPU time, both algorithms produced satisfactory results within an acceptable timeframe.

Keywords: Whale optimization algorithm, Job-shop planning, environmental pollution, energy consumption.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        

 

        

---

[1]  

1.       [2]  Aggoune, 2004

2.       [3]  Kubzin & Strusevich, 2006

3.       [4]  Breit, 2006

4.       [5]  Ruiz, García-Díaz, & Maroto, 2007

5.       [6]  Zribi, El Kamel, & Borne, 2008

6.       [7]  Yang, Hsu, & Kuo, 2008

7.       [8]    Naderi, Zandieh, & Fatemi Ghomi, 2009

8.       [9]    Jabbarizadeh, Zandieh, & Talebi, 2009

9.       [10]   Girish & Jawahar, 2009

10.       [11] Moradi, Fatemi Ghomi, & Zandieh, 2010

11.       [12] Naderi, Zandieh, & Aminnayeri, 2011

12.       [13] Golmakani & Birjandi, 2014

13.       [14] Golmakani & Namazi, 2014

14.       [15] Saddikuti & Pesaru, 2019

15.       [16] Abedini, Li, Badurdeen, & Jawahir, 2020

16.       [17] Amiri & Behnamian, 2020

17.       [18] Whale Optimization Algorithm (WOA)

18.       [19] HafVan

19.       [20] Megaptera novaeangliae

20.       [21] Upward spirals

21.       [22] Double loops