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

ُُFlexible job shop scheduling using improved cuckoo search algorithm by Markov clustering and Levy flight

با توجه به پيچيدگي بالاي مسائل زمان‌بندي، روش‌هاي كلاسيك جواب‌گوي حل اين مسئله نيستند، بنابراين امروزه از الگوريتم‌هاي فرااكتشافي در حل آن استفاده مي­شود. در اين مقاله الگوريتم بهينه‌سازي فاخته به‌عنوان يكي از جديدترين و قوي‌ترين روش‌هاي بهينه‌سازي تكاملي براي حل مسئله زمان‌بندي كاركارگاهي انعطاف‌پذير استفاده شده است. در الگوريتم پيشنهادي براي بهبود پاسخ‌ها، ترتيب ورود جمعيت اوليه بر اساس الگوريتم NEH-D، كه مبتني بر كاهش زمان اجراي هر يك از كارها است، تعيين شده است. سپس ماشين‌هاي فعال توسط خوشه‌بندي ماركوف گروه‌بندي مي‌گردند، تا در هر مرحله از عمليات، انتخاب ماشين از بين ماشين‌هاي فعال صورت گيرد. بنابراين تعداد جواب‌ها‌ي انتخابي براي الگوريتم جستجوي فاخته محدود مي­گردد، تا سرعت اجراي الگوريتم فاخته افزايش يابد. درنهايت نيز از الگوريتم جستجوي فاخته براي تخصيص ماشين‌ها به كارها و از پرواز لوي براي بهبود در الگوريتم فاخته جهت جستجوي سراسري در كنار جستجوي محلي استفاده شده است. الگوريتم پيشنهادي بر روي مجموعه داده استاندارد Kacem، Brandimarte و داده‌ها‌ي مقالات مرتبط ارزيابي شده است. نتايج تجربي نشان مي‌دهد، كه الگوريتم پيشنهادي سرعت بالاتري در رسيدن به جواب نهايي و همچنين همگرايي بالايي در جواب‌ها‌ دارد.

Considering the high complexity of scheduling problems, classic approaches fail to find the solution efficiently. Therefore, meta-heuristic algorithms are used for this purpose. In this paper, Cuckoo optimization algorithm (COA) is used as one of the novel and most effective evolutionary optimization algorithms for flexible job shop scheduling. In the proposed approach, for better solutions, the initial population is determined using NEH-D algorithm, which considers the completion time minimization of each job. Then active machines are grouped using Markov clustering, so that the assigned machine is chosen from the active ones, hoping that the possible solutions of COA are bounded and the execution speed of the algorithm is increased. Finally, COA is applied for job-machine assignment and Levy flight is used to improve the global search of the algorithm. The proposed approach is evaluated on standard datasets such as Kacem, Brandimarte and other related data. The experimental results show that the proposed algorithm is capable of finding the final solution with lower computational complexity and has higher convergence rate.