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

Abstract

در این مقاله مساله زمانبندی تولید کارگاهی در نظر گرفته شده که در عین کاربردی بودن آن به عنوان یکی از مسائل پیچیده در مبحث بهینه‌سازی ترکیبیاتی مطرح بوده و این امر باعث توجه روز افزون محققین به این مساله شده است. در این مساله با فرض وجود تعدادی کارگاه، تعداد کار بایستی با مسیر تولیدی که از قبل معلوم است در این کارگاهها پردازش ‌شوند. به منظور حل این مساله، در این مقاله، ابتدا مساله زمانبندی تولید کارگاهی بصورت برنامه‌ریزی عددصحیح مختلط مدل گردیده است. سپس با توجه به محدودیت حل مسئله بصورت دقیق با استفاده از این مدل، روش برش سطحی به منظور ایجاد نامعادلاتی که برای مساله معتبرند در قالب الگوریتم شاخه و برش پیشنهاد گردیده است. هدف از اضافه کردن این مجموعه‌ از نامعادلات، ایجاد کران پایینی است که در عین حال که جواب‌های شدنی توسط آنها حذف نمی‌شود، باعث تسریع حل در قالب الگوریتم شاخه و برش می‌شود. برای حل مساله به صورت بهینه، نتایج نشان می‌دهد که حدود پایین ایجاد شده توسط مدل مجددا فرموله شده، قوی تر از حدود پایین ایجاد شده توسط مدل اصلی آزاد شده می‌باشد.