حل مساله زمان بندي جريان كارگاهي برگشت پذير بدون وقفه

Solving Re-entrant No-wait Flow Shop Scheduling Problem

در اين مقاله زمانبندي مساله جريان كارگاهي برگشت ­پذير بدون وقفه با هدف كمينه ­سازي حداكثر زمان تكميل كارها بررسي مي­ شود. محيط هاي جريان كارگاهي برگشت ­پذير به نوعي چيدمان جريان كارگاهي گفته مي­ شود كه در آن حداقل يك كار مي ­بايست يك يا چند مرحله را بيش از يكبار ملاقات كند. در مسائل جريان كارگاهي بدون وقفه مراحل انجام يك كار بر روي ماشين ها از ابتدا تا انتها بدون وقفه انجام مي­ شوند. ادغام هردوي اين خصوصيات در بسياري از صنايع مانند صنايع رباتيك دارد كاربرد دارد كه در ادبيات بصورت مجزا مورد بررسي قرار نگرفته است. در اين مقاله براي مساله زمان بندي جريان كارگاهي برگشت پذير بدون وقفه مدل رياضي ارائه شده است. براي مسايل با ابعاد كوچك نتايج حاصل از نرم ­افزار GAMS با نتايج حاصل از الگوريتم­ هاي ژنتيك و شبيه­ سازي تبريد مقايسه گرديده است و براي ابعاد بزرگ نتايج حاصل از الگوريتم ­هاي ژنتيك و شبيه­ سازي تبريد با يكديگر مقايسه گرديده ­اند. نتايج محاسباتي نشان داد كه در كل الگوريتم SA نسبت به GA، از لحاظ بدست آوردن جواب بهينه يا نزديك به بهينه الگوريتمي كاراتر مي‌باشد.

In this study we consider the production environment of re-entrant flow-shop (RFS) with the objective of minimizing make span of the jobs. In a RFS, at least one job should visit at least one of the machines more than once. In a no-wait flow shop-scheduling problem, when the process of a specific job begins on the first machine, it should constantly be processed without waiting in the line of any machine until its processing is completed on the last one. Integration of the properties of both of these environments, which is applied in many industries such as robotic industries, is not investigated separately. In the paper, we present a simulated annealing (SA) and a genetic algorithm (GA) based on heuristics for the problem. First, we develop the mathematical model for the problem, and then we present the suggested algorithms. For small scale, results of GA and SA are compared to GAMS. For large-scale problems, results of GA and SA are compared to each other. Computational results show that both SA ad GA algorithms perform properly but totally, SA is likely to turn out well in finding better solutions especially in large-scale problems.