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

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

Keywords:

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