کنفرانس بین المللی محاسبات نرم

صفحه اصلی / ششمین کنفرانس بین المللی محاسبات نرم

الگوریتم‌های حریصانه و فراابتکاری برای مسئله زمان‌بندی کارها در ماشین‌های یکسان با گراف تعارض بلوک

نویسندگان :

وحید سارانی¹ نرجس سابقی²

1- دانشگاه ولایت 2- دانشگاه ولایت

کلمات کلیدی :

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

چکیده :

این پژوهش به تحلیل مسئله زمان‌بندی کارها بر روی ماشین‌های موازیِ یکسان در حضور محدودیت‌های گرافی می‌پردازد، جایی که روابط تعارض میان وظایف با استفاده از ساختار گراف تعارض بلوک مدل‌سازی می‌شوند. در این گراف، گره‌ها نشانگر کارها و بلوک‌ها بازنمایی‌کننده مجموعه‌هایی از کارهای ناسازگارند که نمی‌توانند به‌طور هم‌زمان به یک ماشین تخصیص یابند. به عنوان نمونه‌ای ازکاربرد این مسئله می‌توان به زمان‌بندی آموزش مهارت‌های مختلف به کارکنان یک سازمان اشاره کرد، به‌گونه‌ای که اعضای یک تیم نمی‌توانند هم‌زمان تحت آموزش یک مربی قرار گیرند و برخی از کارکنان ممکن است در چند گروه مشترک عضویت داشته باشند، که این امر سبب بروز تعارض در تخصیص منابع آموزشی می‌شود. به منظور حل این مسئله، دو رویکرد متمایز مورد بررسی قرار گرفته است (۱- الگوریتم حریصانه ۲-تقریب که از ساختار گراف بلوک برای تقسیم بازگشتی مسئله و ارائه حدود تضمین شده بهینگی استفاده می‌کند؛ ۲- الگوریتم ژنتیک مبتنی بر رنگ‌آمیزی گراف‌ها). برای ارزیابی کارایی روش‌ها، تابعی طراحی شده است که نمونه‌های تصادفی از گراف‌های بلوکی با اندازه و تراکم‌های متنوع تولید می‌کند تا عملکرد الگوریتم‌ها در شرایط ساختاری متفاوت سنجیده شود. نتایج حاصل از آزمایش‌های عددی نشان می‌دهد که الگوریتم حریصانه از منظر پیچیدگی زمانی و سادگی پیاده‌سازی عملکرد برتری دارد، در حالی که الگوریتم‌های فراابتکاری، به ویژه الگوریتم ژنتیک در دستیابی به مقادیر کمتر و دستیابی به تعادل بهتر میان بار ماشین‌ها نتایج قابل‌توجهی ارائه می‌دهند. تحلیل مقایسه‌ای روش‌های ارائه شده، نشان می‌دهد که ادغام مفاهیم نظری الگوریتم‌های تقریبی با قابلیت‌های جستجوی تصادفی فراابتکاری می‌تواند مسیر نوینی برای طراحی رویکردهای کارا در مسائل زمان‌بندی ترکیبی فراهم آورد.