حل مسئله زمان بندی ماشینهای موازی نامرتبط با اهداف کل زودکرد وزنی و کل دیرکرد وزنی با استفاده از الگوریتم جستجوی پراکنده چند هدفه

Abstract

در این مقاله، یک مدل ریاضی جدید برای حل مسئله زمان بندی ماشینهای موازی نامرتبط1 با اهداف کل زودکرد وزنی و کل دیرکرد وزنی معرفی گردیده است. در ضمن به دلیل اهمیت زمانهای آمادهسازی وابسته به توالی2 در بحث ماشینهای موازی، این محدودیت نیز در مدل مذکور در نظر گرفته شده است. با توجه به وجود تضاد بین دو تابع هدف مذکور، استفاده از روشهای کلاسیک بهینه سازی جهت دست یابی به جوابهای بهینه، سراسری یا موضعی امری غیر ممکن بوده و بنابراین برای حل مسئله، از روشی موسوم به بهینهسازی چندمعیاره استفاده میگردد. با توجه به پیچیدگی محاسباتی مسئله فوق، یک الگوریتم فرا ابتکاری مبتنی بر روش جستجوی پراکنده چند هدفه3 (MOSS) برای دست یابی به جوابهای بهینه غالب (پارتو) پیشنهاد میشود. هم چنین به منظور دست یابی به جوابهای اولیه با کیفیت و پراکنده برای الگوریتم پیشنهاد شده، از یک روش جستجوی ممنوع نخبهگرا? (ETS) استفاده میشود. برای صحهگذاری بر عمل کرد الگوریتم پیشنهادی، مسائل متعددی طراحی گردیده و کارایی این الگوریتم، بر پایه برخی شاخصهای طراحی شده، با الگوریتم جستجوی ممنوع ارائه شده، مورد مقایسه قرار میگیرد. نتایج محاسباتی نشان میدهند که الگوریتم پیشنهاد شده، به طور مؤثری عمل میکند.