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

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

A branch and bound algorithm for flexible job shop scheduling problem followed by an assembly stage

Concurrently scheduling for twostage production systems consist of a processing stage and an assembly stage causes to achieve the ideal result for these systems. This paper aims to propose a branch and bound (B B) algorithm for the scheduling problem in a flexible job shop followed by an assembly stage. The objective function is the total completion time of products (makespan). Due to time consuming the classic B B algorithms in solving optimization problems, two efficient lower bounds are developed to reduce the run time. Moreover, two search strategies the socalled the Best First Search (BFS) and the DepthFirst Search (DFS) are introduced to enhance performance of the proposed algorithm. The variable neighborhood search (VNS) is applied to determine proper upper bound for solution of the problem. To more clarification, the problem is modeled as a mixedinteger linear programming (MIP) model with definition need parameters and decision variables. Since the problem is well known as NPhard strongly, performance of the proposed algorithm is investigated in comparison to the exact solutions provided by the mathematical model for the smallsized instances. The evaluation results showed that the depth search strategy has performed better than the other one. This search strategy has could to enhance efficiency of the proposed algorithm, and has significantly reduced the solution time.