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

Total Tardiness Minimization in Flow Shop with Intermediate Due Dates

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

In this paper minimization of total tardiness with intermediate due dates in flow shop scheduling is presented. There are some situations in which there is a due date for each intermediate operation of a job such as research and development and consulting projects. Usually each project (job) is carried out through different phases (machines) and there is an associated due date for each phase. Thus the tardiness of each phase should be considered. Due to the complex nature of the tardiness in flow shop problems and since this problem is a NP-hard, three Meta heuristic approaches; Simulated Annealing, Genetic Algorithm and Particle Swarm Optimization have been applied to reach near optimal solution. Extensive computational experiments are performed on 96 generated scenarios. Two indicators were used to evaluate the Meta heuristics. The results indicate that Simulated Annealing and Genetic Algorithm presented better solutions for the given scheduling problem. Moreover considering the CPU time, Genetic Algorithm provided the solution in less time.