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

A hybrid meta-heuristic algorithm for dual resource constrained flexible job shop scheduling problem

در اين مقاله مسيله زمان‌بندي كار كارگاهي منعطف با در‌نظر‌گرفتن منابع دوگانه محدود انسان و ماشين با هدف كمينه‌سازي معيار حداكثر زمان تكميل كارها مورد بررسي قرار گرفته‌است. مسيله مورد‌مطالعه از گروه مسايل NP-hard است و از ? زير‌مسيله تشكيل شده‌است. مسيله اول تخصيص هر عمليات به يك ماشين از ميان ماشين‌هاي موجود براي انجام آن عمليات، مسيله دوم تخصيص هر عمليات به يك كارگر از ميان كارگرهاي قادر به انجام آن عمليات و مسيله ديگر تعيين توالي عمليات‌ها روي ماشين‌ها با توجه به كارگران در‌نظر گرفته‌شده به‌منظور بهينه‌سازي معيار عملكرد مي‌باشد. ما در اين مقاله مدل رياضي مسيله مورد‌نظر را تهيه و در ادامه يك الگوريتم فراابتكاري تركيبي را براي حل آن ارايه كرده‌ايم. الگوريتم تركيبي توسعه داده‌شده از الگوريتم‌هاي جستجوي همسايگي متغير و شبيه‌سازي تبريد براي جستجوي فضاي جواب استفاده مي‌كند. به‌منظور ارزيابي عملكرد الگوريتم ارايه‌شده، مطالعات محاسباتي با در‌نظر‌گرفتن مسايل نمونه ايجاد‌شده انجام خواهد‌شد. نتايج نشان مي‌دهد كه الگوريتم ارايه‌شده روشي موثر براي حل مسيله زمان‌بندي كار كارگاهي منعطف با منابع دوگانه محدود انسان و ماشين است.

In this paper, the dual-resource constrained flexible job-shop scheduling problem (DRCFJSP) with objective of minimizing the makespan is investigated. Under studied problem is NP-hard and mainly includes three sub-problems. The first one is to assign each operation to a machine out of a set of capable machines, the second one is to determine a worker among a set of skilled workers for processing each operation on the selected machine and the third one deals with sequencing the assigned operations on the machines considering workers in order to optimize the performance measure. In this paper, we provide a mathematical model for this problem and then propose a hybrid meta-heuristic algorithm for solving the problem. The proposed hybrid algorithm uses variable neighborhood search and simulated annealing algorithms to search in the solution space. Computational study with randomly generated test problems is performed to evaluate the performance of the proposed algorithm. The results show the proposed algorithms are effective approaches for solving the DRCFJSP.