الگوریتم ترکیبی شبیه سازی تبرید موازی ـ ژنتیک برای حداقل کردن تعدادکارهای دیرکرددار دریک فلوشاپ دوماشین پویا

دراین مقاله مساله زمان بندی یک فلوشاپ دوماشین پویا و با هدف کمینه سازی تعدادکارهای دیرکرددار بررسی شده است درابتدا پیچیدگی مساله بررسی و نشان داده شده که این مساله NP-hard است لذا برای حل مساله مورد نظر یک رویکرد ترکیبی از شبیه سازی تبرید موازی و ژنتیک و یک الگوریتم ابتکاری ارایه شده است برای تولید جمعیت اولیه دررویکرد ترکیبی از الگوریتم ابتکاری پیشنهادی نیز بهره گرفته شده است برای نشان دادن کارایی الگوریتم های پیشنهادی نتایج آنها با جوابهای بهینه بدست آمده توسط روش شاخه و کران مقایسه شده است نتایج محاسباتی نشان میدهد که رویکرد ترکیبی ارایه شده تمام مسائل با اندازه کوچک و بیش از95درصد از مسائل با اندازه متوسط را به صورت بهینه حل می نماید که این امر کارایی و قدرت بالای رویکرد ارایه شده را نشان میدهد همچنین نشانداده شد که متوسط نسبت جواب بهینه به الگوریتمترکیبی و ابتکاری با هدف S 1-Ui به ترتیب حداکثر 1/01 و 1/12 برابر میب اشد که درمقایسه با الگوریتم های ارایه شده درتحقیقات مرتبط با کارهای دیرکرددار نسبت کوچکی می باشد.

کلیدواژه ها:

فلوشاپ دوماشین پویا ، تعدادکارهای دیرکرد دار ، الگوریتم شبیه سازی تبرید موازی ـ ژنتیک ، الگوریتم ابتکاری