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

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

کلیدواژه ها:

الگوریتم فرا ابتکاری ، زمانبندی تک ماشینه ، مجذور زمان های تاخیر ، الگوریتم حریصانه ، جستجوی تکرای ، الگوریتم ژنتیک ،