مدلسازي و حل زمانبندي سيستم توليد كارگاهي در شرايط عدم انتظار سفارشات جهت كمينه‌ سازي حداكثر زمان تكميل: رويكرد تجزيه توالي سفارشات و جدول‌ بندي زماني

Modeling and Solution of Job Shop Scheduling with No-Wait Orders to Minimize Makespan: A Decomposition Approach based on Order Sequencing and Timetabling

شرط عدم انتظار در مساله‌ي زمانبندي توليد كارگاهي، حالت خاصي از مساله‌ي عمومي زمانبندي سيستم توليد كارگاهي است كه در آن هيچ زمان انتظاري بين فرآيندها و هيچ انقطاعي در حين فرآيندهاي كارها، مجاز نمي‌باشد. بعبارت ديگر، از زمانيكه اولين فرآيند هر كار شروع شود، تا زمان تكميل آن كار، هيچ توقفي وجود ندارد. در ادبياتِ مسائل زمانبندي، اين مساله به عنوان يك مساله‌ي قوياً np-hard معروف شده است. لذا ارايه راه حل براي اين مساله به عنوان يك زمينه تحقيقاتي در ادبيات مسايل زمانبندي مورد توجه قرار دارد. رويكردهايي كه جهت حل اين مساله ارائه شده است عموماً مساله‌ي اصلي را به دو زيرمساله‌ي تعيين توالي كارها و جدول‌بندي زماني تجزيه مي‌كنند. در اين تحقيق، ما پس از بررسي و تحليل رويكردهاي مبتني بر الگوريتم ژنتيك جهت حل اين مساله، به ارائه‌ي يك روش جديد مي‌پردازيم. بعد از معرفي مساله‌ي اصلي و رويكردهاي حل آن، به بررسي و تحليل رويكردهاي حل آن پرداخته و نقاط ضعف و قوت آن‌ها را ارزيابي مي‌نمائيم. در نهايت بر اساسِ پيشنهاداتي كه جهت بهبود كيفيت جواب‌هاي حاصل از رويكردهاي حل ارائه خواهد شد، يك الگوريتم ژنتيك با كارآئي نسبي بالا پيشنهاد ميشود. در نهايت مقايسات انجام شده با رويكردهاي متداول ادبيات بر روي مسايل نمونه، كارآيي رويكرد پيشنهادي را مورد بررسي و تحليل قرار مي‌دهد.

Job shop scheduling problem with no-wait is a special case of general job shop scheduling problem where there is no waiting time between operations and within jobs. In other words, when the operation of each order starts, there is no stop. In literature of scheduling problems, this problem has been known as NP-hard problem. The proposed approach for solving such problems generally decompose the problem into two sub problems: sequencing and timetabling. In this paper, after analyzing the genetic algorithm based approaches presented in literature, we will present a new approach. After introducing the main problem and solution approaches, we will investigate the solution approaches and evaluate their limitations and advantages. Finally a GA based on the improvements will be presented which exhibits relatively high efficiency.