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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری مهندسی صنایع، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه بوعلی‌سینا، همدان، ایران

2 گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه الزهرا (س)، تهران، ایران

3 استادیار گروه مهندسی صنایع، دانشکده صنایع و مدیریت، دانشگاه صنعتی شاهرود، شاهرود، ایران

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسندگان [English]

  • Fatemeh Daneshamooz 1
  • Parviz Fattahi 2
  • Seyed Mohammad Hassan Hosseini 3
1 PhD Student in Industrial Engineering, Department of Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
3 . Assistant Professor, Department of Industrial Engineering and Management, Faculty of Industry and Management, Shahrood University of Technology, Shahrood, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Scheduling
  • Flexible flow shop
  • Sssembly
  • Branch and bound algorithm

مراجع

[1] Urlings, T. (2010). Heuristics and metaheuristics for heavily constrained hybrid flowshop problems. PhD thesis, Universidad Politecnica de valencia, France.
[2] Lee, C.Y., Cheng, T.C.E., Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flow shop scheduling problem, Management Science, 39 (5), 616-625.
[3] Park, M.W., Kim, Y.D. (2000). A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints, European Journal of Operational Research, 123: 504-518.
[4] Tozkapan, A. K., Chung, C.S. (2003). A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly-scheduling problem, Computers & Operations Research, 30: 309-320.
[5] Yokoyama, M. (2004). Scheduling for two-stage production system with setup and assembly operations, Computers & Operations Research, 31: 2063–2078.
[6] Yokoyama, M., Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times, European Journal of Operational Research, 161: 754-770.
[7] Allahverdi, A., Al-Anzi, F.S. (2006). A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times, European Journal of Operational Research, 169: 767-780.
[8] Yokoyama, M. (2008). Flow-shop scheduling with setup and assembly operations, European Journal of Operational Research, 187: 1184–1195.
[9] Sung, C.S., Kim, H.A. (2008). A two-stage multiple-machine assembly-scheduling problem for minimizing sum of completion times, International Journal of Production Economics, 113: 1038-1048.
[10] Fattahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-moghadam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling, 38: 119–134.
[11] Yao, L., Sarin, C.S. (2014). Multiple-Lot Lot Streaming in a Two-stage Assembly System, Essays in Production, Project Planning and Scheduling, 357-388.
[12] Lee, J.Y., Bang, J.Y. (2016). A Two-Stage Assembly-Type Flowshop Scheduling Problem for Minimizing Total Tardiness, Mathematical Problems in Engineering, 6409321.
[13] Lin, W.C. (2018). Minimizing the Makespan for a Two-Stage Three-Machine Assembly Flow Shop Problem with the Sum-of-Processing-Time Based Learning Effect, Discrete Dynamics in Nature and Society, 1-15.
[14] Hosseini, S.M.H., Hassani, A.A. (2017). Proposed a branch and bound algorithm for Assembly flow shop scheduling problem, Journal of Modeling in Engineering, 15: 85-98.
[15] Luo, J.C., Liu, Z.Q., Xing, K.Y. (2019). Hybrid branch and bound algorithms for the two-stage assembly-scheduling problem with separated setup times, International Journal of Production Research, 57: 1398-1412.
[16] Hosseini, S.M.H. (2019). Modelling and solving the job shop scheduling Problem followed by an assembly stage considering maintenance operations and access restrictions to machines. Journal of Optimization in Industrial Engineering, 12(1), 63-78. DOI: 10.22094/joie.2018.760.1484.
 [17] Fattahi, P., Rad, N. B., Daneshamooz, F., & Ahmadi, S. (2020). A new hybrid particle swarm optimization and parallel variable neighborhood search algorithm for flexible job shop scheduling with assembly process. Assembly Automation.
[18] Zhang, S., & Wang, S. (2018). Flexible assembly job-shop scheduling with sequence-dependent setup times and part sharing in a dynamic environment: Constraint programming model, mixed-integer programming model, and dispatching rules. IEEE Transactions on Engineering Management, 65(3), 487-504.
[19] Defersha, F. M., & Movahed, S. B. (2018). Linear programming assisted (not embedded) genetic algorithm for flexible job shop scheduling with lot streaming. Computers & Industrial Engineering, 117, 319-335.
[20] Shi, F., Zhao, S., Meng, Y. (2020). Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem. International Journal of Production Research, 58: 2604-2625.
[21] Wang, H., Sarker, B.R., Li, J., Li, J. (2020). Adaptive scheduling for assembly job shop with uncertain assembly times based on dual Q-learning. International Journal of Production Research, 1-18.
[22] Land, A.H., Doig, A.G. (1960).  An automatic method of solving discrete programming problems. Econometrica, 28: 497-520.
[23] Ghanbari, R. Heydari, A. (2015). A two-phase variable neighborhood search for solving nonlinear optimal control problems. Iranian Journal of Numerical Analysis and Optimization, 5:13-36.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 8، شماره 17
اسفند 1399
صفحه 347-359

فایل ها

هم رسانی

ارجاع به این مقاله

آمار