حداقل كردن تعداد كارهاي داراي ديركرد در مسيله دو ماشين با ورود غير همزمان

Minimizing the Number of Tardy Jobs in a Two-Machine flowshop problem with Non-Simultaneous Job Entrance

در اين مقاله مسيله زمان‌بندي فلوشاپ دو ماشين با در نظر گرفتن ورود غير همزمان و با هدف كمينه‌سازي تعداد كارهاي داراي ديركرد بررسي شده است. در ابتدا پيچيدگي مساله بررسي و ثابت شده كه مساله NP hard است. بنابراين براي حل مسيله فوق يك الگوريتم ابتكاري كه قابليت حل مسايل با ابعاد خيلي بزرگ را دارد، ارايه شده است. همچنين به منظور حل بهينه مسيله از روش شاخه و كران با در نظر گرفتن الگوريتم ابتكاري به عنوان حد بالا بهره گرفته شده است. نتايج محاسباتي نشان مي‌‌دهد كه رويه شاخه‌و‌كران مسايل با ابعاد 28 فعاليت در گروه High و 20 فعاليت در گروه Low را در زمان منطقي و به طور كامل حل مي‌كند، كه اين امر كارآيي حد بالا، حدود پايين و اصول غلبه ارايه شده براي مسيله را نشان مي‌دهد. همچنين نشان داده شد كه متوسط نسبت جواب بهينه به الگوريتم ابتكاري با هدف ?(1-Ui) حداكثر 11/1 برابر مي‌باشد كه در مقايسه با الگوريتم‌هاي ارايه شده در تحقيقات مرتبط با كارهاي داراي ديركرد نسبت كوچكي مي‌باشد. اين نسبت نشان دهنده كارايي بالاي الگوريتم ابتكاري است. با توجه به كارآيي بالاي الگوريتم ابتكاري، مسايل نمونه با ابعاد بزرگ نيز حل و نتايج آن ارايه شده است

In this paper, minimizing the number of tardy jobs in two-machine flowshop scheduling with non-simultaneous job entrance is discussed. It is proven that the complexity of the problem is NP_hard. Therefore, a heuristic algorithm is proposed to solve the large scale problems. Besides, an exact branch and bound algorithm with utilizing heuristic algorithm as upper bound proposed to achieve optimal solution. Computational results demonstrate that branch and bound method solves problems with 28 jobs in the set High and 20 jobs in the set Low in a reasonable time. Results show the capability of the proposed upper bound, lower bounds and dominance rules. Also, it is shown that the average ratio of optimal solution to the heuristic one with the objective ?(1-Ui) is at most 1.11 which is smaller in contrast with other researches in the literature. This ratio proves efficacy of the proposed heuristic algorithm. Finally, according to efficiency of the presented approach, sample problems with large dimensions were solved and their results were displayed.