ندا سینا - دانشگاه آزاد اسلامی واحد ساری، دانشکده کامپیوتر
امید غلامی - دانشگاه آزاد اسلامی واحد نور، مرکز محمودآباد، دانشکده کامپیوتر

در این مقاله به مساله زمانبندی کا ر کارگاهی منعطف Flexible Job-Shop scheduling(پرداخته شده است. در مساله زمانبندی کار کارگاهی تعدادnکار باید ازmماشین سرویس دریافت نمایند. یک اشتقاق از مساله زمانبندی کار کارگاهی، مساله زمانبندی کا ر کارگاهی منعطف میباشد که در آن بیش از یک ماشین )ماشینهای موازی یکسان( برای پردازش کار موجود است. بدین ترتیب زمانبند این انعطاف پذیری را دارد که به جای اجرای کار روی یک ماشین، ماشینی را از یک مجموعه برای اجرا انتخاب نماید. هدف کمینهسازی زمان تکمیل تمامی کارها در محیط زمانبندی کا ر کارگاهی منعطف[ 12 ] میباشد. برای حل این مساله از الگوریتم معروف انتقال گلوگاه)Shifting bottleneck([ 4در مساله زمانبندی کا ر کارگاهی کمک گرفته شده است. با توسعهای که در الگوریتم انتقال گلوگاه[ 5] داده شده در هر مرحله از ساخت گراف مختلط حل مساله زمانبندی کار کارگاهی، با اعمال تغییراتی در گراف، این پاسخ را به پاسخی مناسب برای زمانبندی کار کارگاهی با ماشنیهای موازی تبدیل مینماید. کارایی الگوریتم پیشنهادی توسط محکهای استاندارد سنجیده شده است و با کارهای دیگر مقایسه شده است که نشان از کارا بودن روش پیشنهادی دارد

زمانبندی کا ر کارگاهی، ماشینهای موازی یکسان، گراف مختلط،انتقال گلوگاه، زمان تکمیل آخرین کار