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

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

زمان‌بندي هم‌زمان براي سيستم‌هاي توليد دومرحله‌اي شامل يك مرحله‌ي پردازش قطعات و يك مرحله‌ي مونتاژ، موجب تحقق اهداف ايده‌آل براي اين سيستم‌ها مي‌شود. در اين مقاله براي اولين‌بار يك الگوريتم شاخه و كران جهت حل مسأله زمان‌بندي در سيستم توليدكارگاهي انعطاف‌پذير همراه با يك مرحله‌ي مونتاژ با هدف حداقل كردن زمان تكميل محصولات ارائه شده است. باتوجه به زمان‌بر بودن روش‌هاي حل شاخه و كران، جهت افزايش كارايي الگوريتم پيشنهادي و كاهش زمان اجراي آن، دو كران پايين ارائه و دو استراتژي جست‌وجوي تحت عنوان جست‌وجوي اولين بهترين و جست‌وجوي عمق مورد بررسي قرار گرفت. هم‌چنين به‌منظور تعيين حد بالا براي هر شاخه، از الگوريتم جست‌وجوي همسايگي متغير (VNS) استفاده شده است. به‌منظور درك بهتر مسأله، يك مدل برنامه‌ريزي عدد صحيح مختلط (MIP) همراه با پارامترها و متغيرهاي تصميم مورد نياز تشريح شده است. ازآن‌جايي‌كه مسأله مورد مطالعه از نوع مسائل رده‌ي سخت محسوب مي‌شود، عملكرد الگوريتم‌هاي پيشنهادي در حل مسأله با ابعاد كوچك مورد ارزيابي و مقايسه قرار گرفته است. نتايج ارزيابي نشان داد كه استراتژي جست‌وجوي عمق عملكرد بهتري داشته و موجب افزايش كارايي الگوريتم شاخه و كران پيشنهادي و كاهش زمان حل مي‌شود.

Concurrently scheduling for two-stage 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 so-called the Best First Search (BFS) and the Depth-First 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 mixed-integer linear programming (MIP) model with definition need parameters and decision variables. Since the problem is well known as NP-hard strongly, performance of the proposed algorithm is investigated in comparison to the exact solutions provided by the mathematical model for the small-sized 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.