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

مساله ی زمان بندی کار کارگاهی، یکی از شناخته شده ترین و پیچیده ترین مسائل زمان بندی است که در آن می بایست n کار روی m ماشین با حفظ توالی خاصی انجام شود. در مساله ی زمان بندی کار کارگاهی، توالی عملیات هر کار اهمیت دارد و اینکه هر عملیات باید فقط و فقط بر روی یک ماشین خاص پردازش شود. هدف اصلی این مساله، به حداقل رساندن زمان تکمیل کل کارها (makespan) است. تحقیقات زیادی در این زمینه انجام و الگوریتم های مختلفی برای حل بهینه آن ارائه شده است. الگوریتم های تکاملی، از جمله الگوریتم های ارائه شده اخیر است. در این تحقیق، از ترکیب دو الگوریتم ژنتیک و رقابت استعماری استفاده شده است. الگوریتم ژنتیک، همواره به عنوان یکی از کارآمدترین روش ها در مسائل زمان بندی مطرح بوده است. همچنین الگوریتم رقابت استعماری نیز که یک الگوریتم نوپا و طراح آن یک ایرانی است، اخیرا برای این گونه مسائل، استفاده شده است. نتایج اجرای الگوریتم ترکیبی بر روی مجموعه داده های مختلف با الگوریتم های دیگر، مقایسه شده است و نتایج مقایسه نشان داد که الگوریتم ارائه شده در همه نمونه داده های با اندازه کوچکتر عملکرد بسیار بهتری نسبت به الگوریتم های دیگر داشته است. در نمونه داده های با اندازه متوسط، در بیش از نیمی از داده ها عملکرد بهتری داشته است اما در نمونه داده های با اندازه بزرگ، در بیشتر موارد نتوانسته است، مساله را بهینه و makespan را کاهش دهد.

کلیدواژه ها:

مساله ی زمان بندی کار کارگاهی ، makespan ، الگوریتم ژنتیک ، الگوریتم رقابت استعماری