Meta-Heuristic Algorithms for Two-Stage Assembly Flow Shop Scheduling Problem with Considering Setup Times of Machines

Yazdani, Mehdi

doi:10.22054/jims.2020.47551.2394

Document Type : Research Paper

Author

Mehdi Yazdani

Assistant Professor, Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Islamic Azad University, Qazvin Branch

https://doi.org/10.22054/jims.2020.47551.2394

Abstract

This paper deals with the problem of two-stage assembly flow shop scheduling with considering sequence-independent setup times .The objective is to minimize total
completion times of all orders. In this problem, there are several orders for one type of product. Each ordered product is formed of several different parts. At first, the parts are manufactured in a flow shop stage with some different machines and then they are assembled into a final product on a single machine. This paper presents three meta-heuristic algorithms, namely Parallel Variable Neighborhood Search (PVN) Artificial Immune Algorithm (AIA) and Simulated Annealing (SA), for solving under studied problem. The Taguchi experimental design method as an optimization technique is employed to tune different parameters and operators of presented algorithms. Also, Numerical experiments are used to evaluate the performance of the proposed algorithms. The results show that the PVNS algorithm performs better than the other algorithms

Keywords

20.1001.1.22518029.1399.18.58.10.4

References

[1] Y. Demir, S. Kursat Isleyen (2013). Evaluation of mathematical models for flexible job-shop scheduling problems, Applied Mathematical Modelling, 37, 977–988.

[2] C.Y. Lee, T.C.E. Cheng, B.M.T. Lin (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39(5), 616–625.

[3] C.N. Potts, S.V. Sevast’janov, V.A. Strusevich, L.N.V. Wassenhove, C.M. Zwaneveld (1995). The two-stage assembly scheduling problem, Complexity and approximation, Operations Research, 43(2), 346–355.

[4] A. Allahverdi, F.S. Al-Anzi (2006). A PSO and a tabu search heuristics for assembly scheduling problem of the two stage distributed database application, Computers and Operations Research, 33(4), 1056–80.

[5] M. Yokoyama, D.L. Santos (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.

[6] P. Fattahi, S.M. Hosseini, F. Jolai, R. Tavakkoli-Moghaddam (2013). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling 38, 119–134.

[7] M. Yokoyama (2008). Flow-shop scheduling with setup and assembly operations, European Journal of Operational Research, 187, 1184–1195.

[8] A.M.A. Hariri, C.N. Potts (1997). A branch and bound algorithm for the two-stage assembly scheduling problem, European Journal of Operational Research, 103, 547–556.

[9] T.C.E. Cheng, G. Wang (1999). Scheduling the fabrication and assembly of components in a two-machine flow shop, IIE Transactions, 31, 135–143.

[10] M. Yokoyama (2001). Hybrid flow-shop scheduling with assembly operations, International Journal of Production Economics, 73(2), 103–116.

[11] C. Koulamas, G.J. Kyparisis (2001). The three-stage assembly flow shop scheduling problem, Computers and Operations Research, 28(7), 689–704.

[12] A. Allahverdi, F.S. Al-Anzi (2006). Evolutionary heuristics and an algorithm for the two- stage assembly scheduling problem to minimize makespan with setup times, International Journal of Production, 44(22), 4713–35.

[13] F.S. Al-Anzi, A. Allahverdi (2007). A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times, European Journal of Operational Research, 182(1), 80–94.

[14] A. Mozdgir, S.M.T. Fatemi Ghomi, F. Jolai, J. Navaei (2013). Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times, International Journal of Production Research, 51(12), 3625–42.

[15] A. Tozkapan, O. Kirca, C.S. Chung (2003). A branch and bound algorithm to minimize the total weighted flow time for the two-stage assembly scheduling problem, Computers and Operations Research, 30(2), 309–20.

]16[ غلامی، حبیب رضا، مهدی زاده، اسماعیل، نادری، بهمن (1397) مدل‌سازی ریاضی و الگوریتم رقبات استعماری برای مسئله خط مونتاژ جریان کارگاهی، چشم انداز مدیریت صنعتی، شماره 29، 84-102.

[17] R.W. Eglese (1990). Simulated annealing: a tool for operational research, European journal of operational research, 46(3), 271–81.

[18] R. Storn, K. Price. Differential evolution – a simple and efficient heuristic for global optimization over continuous space, Journal of global optimization 11(4) (1997) 341–59.

[19] N. Mladenovic, P.V. Hansen (1997). A variable neighborhood search, Computers & Operations Research, 24(11), 1097–100.

[20] F. Glover (1986), Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13(5), 533–49.

[21] M. Dorigo, L.M. Gambardella (1997). Ant colony system: a cooperative learning approach to the traveling sales man problem, IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

[22] A. Bagheri, M. Zandieh, I. Mahdavi, M. Yazdani (2010). An artificial immune algorithm for the flexible job-shop scheduling problem, Future Generation Computer Systems, 26(4), 533–541.

[23] E. Atashpaz-Gargari, C. Lucas (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, in: CEC IEEE Congress on Evolutionary Computation.

[24] M. Sevkli, M.E. Aydin )2007(. Parallel variable neighbourhood search algorithms for job shop scheduling problems, IMA Journal of Management Mathematics, 18(2), 117–133.

[25] M. Zandieh, S.M.T. Fatemi Ghomi, S.M. Moattar Husseini (2006). An immune algorithm approach to hybrid flow shops scheduling with sequencedependent setup times, Applied Mathematics and Computation, 180(1), 111-127.

[26] D. Dasgupta (2002) Special issue on artificial immune system, IEEE Transactions on Evolutionary Computation 6, 225-256.

[27] L.N.D. Castro, J. Timmis (2002). An artificial immune network for multimodal function optimization, Evolutionary computation, CEC'02, in: Proceedings of the Congress, pp. 699-704.

[28] R. Shang, W. Zhanga, F. Li, L. Jiao, R. Stolkin (2019). Multi-objective artificial immune algorithm for fuzzy clustering based on multiple kernels, Swarm and Evolutionary Computation, In Press.

[29] G.C. Luh, C.H. Chueh (2009). A multi-modal immune algorithm for the job-shop scheduling problem, Information Sciences, 179(10), 1516-1532.

]30[ یزدانی، مهدی، زندیه، مصطفی، توکلی مقدم، رضا (1393) یک الگوریتم فراابتکاری ترکیبی برای مسئله زمان بندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین، مطالعات مدیریت صنعتی، شماره 33، 43-74.

Industrial Management Studies

Meta-Heuristic Algorithms for Two-Stage Assembly Flow Shop Scheduling Problem with Considering Setup Times of Machines

References

References

Volume 18, Issue 58
October 2020
Pages 307-335

Meta-Heuristic Algorithms for Two-Stage Assembly Flow Shop Scheduling Problem with Considering Setup Times of Machines

References

References

Volume 18, Issue 58October 2020Pages 307-335

Volume 18, Issue 58
October 2020
Pages 307-335