|
|
|
|
کاربرد رنگ‌آمیزی دایره‌یی گراف و الگوریتم جامعه مورچگان در حل مسیله‌ی زمان‌‌بندی چرخشی کارگاهی باز
|
|
|
|
|
|
|
|
نویسنده
|
مدرس محمد ,قندهاری مهسا
|
|
منبع
|
شريف - 1389 - دوره : 26 - شماره : 1 - صفحه:3 -10
|
|
چکیده
|
در این نوشتار مدلی برای تعیین زمان‌‌بندی بهینه‌ی چرخشی کارگاهی باز طراحی میشود. برای انجام هر عملیات چندین منبع مورد نیاز است که به‌طور هم‌زمان باید از تمامی آن‌ها استفاده شود. این مسئله از لحاظ پیچیدگی محاسباتی در رده‌ی مسائل np-hard قرار دارد. ابتدا نشان می‌‌دهیم که این مسئله را می‌‌توان به مسئله‌ی رنگ‌آمیزی دایره‌یی رئوس یک گراف تبدیل کرد. آنگاه، الگوریتمی در چارچوب روش فرا‌ابتکاری جامعه‌ی مورچگان طراحی میشود که می‌‌تواند در حل مسائل با اندازه‌ی بزرگ‌تر مورد استفاده قرار گیرد. برای بررسی و ارزیابی کارایی الگوریتم پیشنهادی، از یک دسته مسائل با عدد رنگی دایره‌یی غیر‌صحیح استفاده میشود و در نهایت نتایج حاصله با جواب‌ها‌ی به‌دست آمده از روش تحلیلی مقایسه خواهد شد.
|
|
کلیدواژه
|
زمان‌‌بندی ,رنگ‌آمیزی دایره‌یی گراف ,الگوریتم جامعه‌ی مورچگان ,برنامه‌ریزی عملیاتی
|
|
آدرس
|
دانشگاه صنعتی شریف, ایران, دانشگاه صنعتی شریف, ایران
|
|
پست الکترونیکی
|
ghandehary@yahoo.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|