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

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