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

زمان بندی نوعی تصمیم گیری است که در جریان آن برنامه زمانی را تعیین می کنند. مسائل زمان بندی از نوع مسائل موسوم به NP – hard می باشند.. شرح مسئله به این صورت است که N قطعه وجود دارد که بر روی M ماشین برنامه ریزی شوند. هر قطعه شامل یک سری اعمال است که باید طبق ترتیب از پیش تعیین شده در هر ماشین صورت گیرد. هر عمل روی یک ماشین مشخص و بازمان پردازش ثابت انجام می گیرد. در واقع هدف در این مسئله تعیین کردن ترتیب انجام اعمال روی ماشین ها به گونه ای است که حداکثر زمان اجرا مینیمم شود. حداکثر زمان اجرا زمان موردنیاز جهت تکمیل شدن کلیه اعمال روی قطعات است. با توجه به نیاز روزافزون جامعه به بهبود عملکرد الگوریتم های زمان بندی و با توجه به اینکه حوزه داخلی و خارجی توجه زیادی به این موضوع نشده است. امروزه تاکنون روش های مختلفی در محدوده قوانین توزیع کننده ساده و سریع تا الگوریتم های پیچیده branch – and – bound برای حل این مسئله پیشنهاد شده است، به دلیل طبیعت ترکیبی بودن مسئله زمان بندی پیدا کردن جواب بهینه برای چنین مسائلی بسیار سخت بوده که جهت حل این مشکل در این مقاله از الگوریتم های تکاملی بهره برده شده است. شبیه سازی روش پیشنهادی و مقایسه آن با کارهای پیشین عملکرد مناسب این روش را نشان داد.

کلیدواژه ها:

زمان بندی ، الگوریتم های تکاملی ، بهینه سازی ، مسائل NP-Hard