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

Document Type : Research Paper

Authors

1 PhD Student in Industrial Engineering, Department of Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

2 . Assistant Professor, Department of Industrial Engineering and Management, Faculty of Industry and Management, Shahrood University of Technology, Shahrood, Iran

Abstract

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.

Keywords

References

[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.
Journal of Industrial Engineering Research in Production Systems
Volume 8, Issue 17
March 2021
Pages 347-359

Files

Share

How to cite

Statistics