ارایه الگوریتم ژنتیک برای حل مسایل زمانبندی چند مرحله ای با ویژگی ماشین های موازی

دراین مقاله، ما به تعمیم زمانبندی مسیله job-shop ، J |r_i |Φ می پردازیم که مسیله job-shop ماشین موازی نامیده می شود و به صورت FJ |r_i |Φ بیان می شود. در مسیله FJ |r_i |Φچندین ماشین یکسان Mk≠ Ø از نوعk ∈{1,2,…,φ} برای پردازش زیرمجموعه متناظر Ok مجموعه عملیات O⊆O_k در دسترس هستند. این انعطاف پذیری به زمانبند امکان کاهش مقدار تابع هدف را می دهد زیرا هر عملیات Q_ij^(μ(ij))∈O_k می تواند بر روی هر ماشینی از نوع k = μ (ij) در مرحله j از کار J_i پردازش شود. بنابراین، مجموعه عملیات Ok ممکن است برای پردازش همزمان به زیرمجموعه های |M_k | تقسیم شوند. در حقیقت، مسیله پیدا کردن زمانبندی بهینه برای پردازش مجموعه عملیات مفروض O در job-shop با تخصیص عملیات Ok به ماشین های Mk برای هر نوع k∈{1,2,…,φ} ترکیب می شود. یک راه حل مسیله FJ |r_i |Φ شامل راه حل هایی از این زیرمسایل می باشد. دو معیار معین در این پایان نامه مد نظر قرار گرفته شده است: به حداقل رساندن زمان تکمیل آخرین کار(makespan) و Cmax. یک کروموزوم خاص در توسعه الگوریتم های ژنتیک مبتنی بر مدل گراف ترکیبی برای حل همزمان زیرمسایل بالا بکار می رود. این کروموزوم ها توانایی تقسیم عملیات Ok و نشان دادن راه حلی برای مسیله FJ |r_i |Φ را دارند. نتایج محاسباتی برای نمونه های مورد آزمایش نشان داد که الگوریتم ژنتیک توسعه یافته، برای مسیله FJ |r_i |C_max موثراست.

Keywords:

زمانبندی کار کارگاهی منعطف , فرا ابتکاری , ماشین های موازی , حداقل رساندن زمان تکمیل آخرین کار