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

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

کلیدواژه ها:

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