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

Memetic Algorithm for Flexible Job Shop Scheduling with Preemption

مسيله زمانبندي كارِ كارگاهي منعطف Flexible Job Shop)) ، حالت توسعه يافته زمانبندي كارِ كارگاهي Job Shop)) ‌است كه در آن هر عمليات مي‌تواند توسط بيش از يك ماشين از ميان مجموعه ماشين‌هاي‌ موجود انجام شود. اين مسيله در زمره مسايل NP-hard طبقه بندي مي‌شود و براي حل آن با دو زير مساله مواجه هستيم. نخست اينكه، نحوه تخصيص هر فعاليت به ماشيني از ميان ماشين‌هاي‌ موجود كه قادر به پردازش فعاليت مورد نظر است تعيين شود و سپس توالي فعاليت‌هاي‌ تخصيص يافته مشخص گردد. واضح است كه دستيابي به پاسخ بهينه، حتي در ابعاد كوچك دشوار و بسيار زمان‌بر است در اين مقاله يك الگوريتم ممتيك جهت كمينه كردن حداكثر زمان تكميل و بدست آوردن جواب بهينه مسايل كوچك و بهترين جواب مسايل متوسط و بزرگ ارايه مي شود.در اين مقاله همچنين به منظور بهبود جواب هاي حاصل از الگوريتم ممتيك و كاهش حداكثر زمان تكميل فرض ايجاد وقفه در انجام كارها را نيز در نظر مي گيريم.

Flexible job shop scheduling problem )FJSP( is an extension of the classical job shop scheduling problem which allows an operation to be processed by any machine from a given set. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. However, it is quite difficult to achieve an optimal solution to this problem in medium and large size problems with traditional optimization approaches. In this paper a memetic algorithm (MA) or flexible job shop scheduling with overlapping in operation is proposed that solves the FJSP to minimize makespan time and obtain the optimum solution for small problem and best solution for medium and large scale problems. In this paper we also used preemption to improve the results of memetic algorithm and reduce the makespan.