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

A Genetic Local Search Algorithm for Generalized Job Shop Scheduling Problem with Controllable Processing Times

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

Although incorporating complexities and flexibilities of real world manufacturing systems into classic scheduling problems results in problems with greater complexity, it has immense theoretical and practical importance due to its impressive effect on system performance. In this research, three basic assumptions of a job shop scheduling problem have been revised to develop a model with three types of flexibility which fits into many cases of real manufacturing environments;sequencing flexibility, machine flexibility, and processing time flexibility. In this paper, after describing the problem and formulating it as a mathematical program, we have proposed an efficient genetic local search algorithm to solve the problem. In the proposed algorithm first, problem-specific elements including population initialization, crossover, and mutation are designed for genetic algorithm. Then, a novel local search procedure has been developed and incorporated into genetic algorithm to enhance its search ability. In experimental study, the performance of the proposed algorithm to find optimal and near-optimal solutions has been demonstrated based on some test problems which are built by incorporating processing time flexibility into a number of problems adopted from the literature.