Abstract
We investigate the problem of mixed model assembly line balancing with sequence dependent setup times. The problem requires that a set of operations be executed at workstations, in a cyclic fashion, and operations may have precedences between them. The aim is to minimise the maximum cycle time incurred across all workstations. The simple assembly line balancing problem (with precedence constraints) is proven to be NP-hard and is consequently computationally challenging. In addition, we consider setup times and mixed model product types, thereby further complicating the problem. In this study, we propose a novel ant colony optimisation (ACO) based heuristic, which unlike previous approaches for the problem, focuses on learning permutations of operations. These permutations are then mapped to workstations using an efficient assignment heuristic, thereby creating feasible allocations. Moreover, we develop a mixed integer programming formulation, which provides a basis for comparing the quality of solutions found by ACO. Our numerical results demonstrate the efficacy of ACO across a number of problems. We find that ACO often finds optimal solutions for small problems, and high quality solutions for medium-large problem instances where mixed integer programming is unable to find any solutions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note, SALBPS is a special case of MMALBPS.
- 2.
We use workstations and stations synonymously in the remainder of this paper.
- 3.
Backward setups are assumed to be done within the initial setups for all workstations, at the beginning of a cycle.
- 4.
- 5.
In the industry, workstations are limited in the number of operations they can handle.
- 6.
The MIP is given larger run-time as it struggles to find solutions for large problems.
References
S. Akpinar and A. Baykasoğlu. Modeling and solving mixed-model assembly line balancing problem with setups. part i: A mixed integer linear programming model. Journal of manufacturing systems, 33(1):177–187, 2014
Akpinar, S., Elmi, A., Bektaş, T.: Combinatorial benders cuts for assembly line balancing problems with setups. European Journal of Operational Research 259(2), 527–537 (2017)
Battaïa, O., Dolgui, A.: A taxonomy of line balancing problems and their solution approaches. International Journal of Production Economics 142(2), 259–277 (2013)
Blum, Christian, Thiruvady, Dhananjay, Ernst, Andreas T., Horn, Matthias, Raidl, Günther R.: A Biased Random Key Genetic Algorithm with Rollout Evaluations for the Resource Constraint Job Scheduling Problem. In: Liu, Jixue, Bailey, James (eds.) AI 2019. LNCS (LNAI), vol. 11919, pp. 549–560. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35288-2_44
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge, Massachusetts, USA (2004)
M. L. Fisher. The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management science, 50(12\_supplement):1861–1871, 2004
Gutjahr, A., Nemhauser, G.: An algorithm for the line balancing problem. Management science 11(2), 308–315 (1964)
S. K. M. Hossain. Solving Assembly Line Balancing Type II Problem Using Progressive Modeling. In Proceedings of the International Annual Conference of the American Society for Engineering Management., pages 1–10, 2017
Kilincci, O.: A petri net-based heuristic for simple assembly line balancing problem of type 2. The International Journal of Advanced Manufacturing Technology 46(1–4), 329–338 (2010)
Kucukkoc, I., Zhang, D.Z.: Mixed-model parallel two-sided assembly line balancing problem: A flexible agent-based ant colony optimization approach. Computers & Industrial Engineering 97, 58–72 (2016)
Scholl, A.: Balancing and Sequencing of Assembly Lines. Physica-Verlag HD, Contributions to Management Science (1999)
Scholl, A., Becker, C.: State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research 168(3), 666–693 (2006)
Seyed-Alagheband, S.A., Ghomi, S.M.T.F., Zandieh, M.: A simulated annealing algorithm for balancing the assembly line type ii problem with sequence-dependent setup times between tasks. International Journal of Production Research 49(3), 805–825 (2011)
Simaria, A.S., Vilarinho, P.M.: A genetic algorithm based approach to the mixed-model assembly line balancing problem of type ii. Computers & Industrial Engineering 47(4), 391–407 (2004)
Sivasankaran, P., Shahabudeen, P.: Literature review of assembly line balancing problems. The International Journal of Advanced Manufacturing Technology 1665–1694 (2014). https://doi.org/10.1007/s00170-014-5944-y
Thiruvady, D., Morgan, K., Amir, A., Ernst, A.T.: Large Neighbourhood Search based on Mixed Integer Programming and Ant Colony Optimisation for Car Sequencing. International Journal of Production Research 58(9), 1–16 (2019)
D. Thiruvady, A. Nazari, and A. Elmi. An Ant Colony Optimisation Based Heuristic for Mixed-model Assembly Line Balancing with Setups. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1–8, 2020
Thiruvady, D., Wallace, M., Gu, H., Schutt, A.: A Lagrangian Relaxation and ACO Hybrid for Resource Constrained Project Scheduling with Discounted Cash Flows. Journal of Heuristics 20(6), 643–676 (2014)
Vilarinho, P.M., Simaria, A.S.: Antbal: an ant colony optimization algorithm for balancing mixed-model assembly lines with parallel workstations. International journal of production research 44(2), 291–303 (2006)
Zheng, Q., Li, M., Li, Y., Tang, Q.: Station ant colony optimization for the type 2 assembly line balancing problem. The International Journal of Advanced Manufacturing Technology 66(9–12), 1859–1870 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Thiruvady, D., Elmi, A., Nazari, A., Schneider, JG. (2020). Minimising Cycle Time in Assembly Lines: A Novel Ant Colony Optimisation Approach. In: Gallagher, M., Moustafa, N., Lakshika, E. (eds) AI 2020: Advances in Artificial Intelligence. AI 2020. Lecture Notes in Computer Science(), vol 12576. Springer, Cham. https://doi.org/10.1007/978-3-030-64984-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-64984-5_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64983-8
Online ISBN: 978-3-030-64984-5
eBook Packages: Computer ScienceComputer Science (R0)