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

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

Branch & cut algorithm for solving the job shop scheduling problem using valid inequalities

In this paper, the problem of scheduling the job shop production is considered, which, while being applicable as one of the complex issues in the field of combinatorial optimization, has been raised and this has caused the researchers to pay more attention to this problem. In this problem, given the existence of a number of workshops, the number of jobs should be processed in the workshop with a known production path that is already known. In order to solve this problem, in this paper, the problem of production scheduling is firstly modeled as a mixed integer programming. Then, due to the limitations of the exact solving using this model, the surface cutting method is proposed to create inequalities this is valid for the problem in the framework of branching and cutting algorithm. The aim of adding this set of inequalities is to create a lower bound, which, while the feasible solutions are not eliminated by them, accelerates the solution in the framework of branch & cut algorithm. To solve the problem optimally, the results show that the lower bound created by the reformulated model is stronger than the lower bound created by the original relaxed model.