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

در این مقاله، مساله زمانبندی تولید کارگاه منعطف (Flexible Job Shop) با تعریف جدیدی از انعطاف پذیری مورد بررسی قرار می گیرد. در این نوع انعطاف پذیری برای مساله فرض می شود که در هر ایستگاه عملیاتی چند ماشین وجود دارند که کارها در هر ایستگاه می توانند به یکی از آنها تخصیص داده شود. تابع هدف کمینه سازی بازه ساخت (make span) است. ابتدا مدل ریاضی مساله ارائه شده و سپسNP-hard بودن مساله نشان داده می شود. بعلت NP-hard بودن مساله استفاده از روش های دقیق برای حل آن در زمان چندجمله ای ممکن نیست و باید از الگوریتمهای ابتکاری برای حل آن استفاده نمود. به این منظور دو الگوریتم ابتکاری به نامهای H1 و H2 به ترتیب برای مسائل با ابعاد بزرگ و معمولی برای حل مساله ارائه می شود. بعلت اینکه این مساله تا کنون در ادبیات موضوع مورد مطالعه قرار نگرفته است، معیار مناسبی برای ارزیابی الگوریتم های ارائه شده وجود ندارد. بنابراین به منظور ارزیابی الگوریتمهای ارائه شده، سه الگوریتم ابتکاری با نامهای H3، H4 و H5 و همچنین یک کران پایین برای آن ارائه می شود و نتایج الگوریتمهای H1 و H2 با آنها مقایسه شده است. نتایج محاسبات نشان می دهد که الگوریتم پیشنهادی H2برای مسائل با ابعاد کوچک، جوابهای بهتری را نسبت به الگوریتمهای دیگر ارائه می دهد. اما در مسائل با ابعاد بزرگ H1 به طور مجانبی کاراتر از H2 است. همچنین کارائی الگوریتم H3 پایین تر از سایر الگوریتمها است.