Multi-objective Assembly Line Balancing Using
Fuzzy Inertia-adaptive Particle Swarm Algorithm
Fundamental Sciences and Humanities Department,
Constanta Maritime University,
104, Mircea cel Batran Street, Constanta, code 900663, Romania
Abstract: The Assembly Line Balancing problem is an industrial optimization problem of considerable importance in lean systems. It has been extensively studied in literature through classical optimization methods. However, conventional computing paradigms have not proved practical utility for complex problems. Metaheuristic solutions such as “Tabu Search”, “Simulated Annealing”, “Genetic Algorithms”, “Evolutionary Programming”, “Ant Colony”, “Particle Swarm Optimization” were a preoccupation mainly for the last two decades. This paper presents a model of a multi-objective Assembly Line Balancing problem and a solution approach based on Particle Swarm Optimization (PSO) with a fuzzy controller for tuning inertia weight. This prevents the premature convergence and, in addition, the algorithm demonstrates improved search features. For the considered test instance, the algorithm obtains a better result compared to the results reported in the literature, regarding the number of stations actually used, the line efficiency, the total unused time, the variation in charging stations and the uniformity index of the line.
Keywords: Particle Swarm Optimization (PSO), Assembly Line Balancing (ALB) problem, fuzzy controller, multi-objective optimization.
CITE THIS PAPER AS:
Simona DINU, Multi-objective Assembly Line Balancing UsingFuzzy Inertia-adaptive Particle Swarm Algorithm, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (3), pp. 283-292, 2015.
As part of an industrial manufacturing system, installing an assembly line is a costly decision and requires a considerable time for execution and therefore it is important to be well designed and properly balanced to guarantee maximum efficiency in operation.
An important assembly design problem is the assembly line balancing (ALB) problem. This decisional problem is a classic Operations Research (OR) optimization problem that aims to determine the allocation of the tasks to an ordered sequence of workstations such that every task is assigned at just one station, the precedence relations are not violated and certain objectives are fulfilled.
Since the bin-packing problem, which is an ALB problem without precedence constraints , is NP-hard, even the simple case of the ALB problem is NP-hard by nature. Indeed, m tasks and r preference constraints generate m!/2r feasible solutions of the problem , as there are m!/2r possible task sequences. As one can observe, the problem size grows very rapidly with the number of tasks and/or workstations. Because of the high computational complexity, conventional optimization methods do not seem appropriate for this simple or multi-objective practical optimization problem.
Due to the complexity of the ALB problem and its practical importance for industrial applications, many approaches based on metaheuristics such as Tabu Search, Simulated Annealing, Evolutionary Algorithms, Agent-based approaches (Ant Colony Optimization and Particle Swarm Optimization) or hybrid Artificial Intelligence methods have been applied recently in attempts to solve this manufacturing optimization problem. A survey study of soft computing applications in ALB problems is presented in . Other comprehensive reviews of assembly systems and different balancing problems are presented in .
This study proposes a model and a solution approach to a multi-objective ALB problem considering three evaluation criteria. This multi-objective problem is solved by a discrete PSO algorithm whose efficiency is enhanced due to the development of a fuzzy controller for tuning inertia weight.
- AMEN, M., Heuristic Methods for Cost– oriented Assembly Line Balancing: A Comparison on Solution Quality and Computing Time, Int. J. of Production Economics, Vol. 69, 2001, pp. 255-264.
- BAYBARS, I., A survey of exact algorithms for SALBP, Management Science, Vol. 32, 1986, pp. 11-17.
- BETANCOURT, L. C., ASALBP: the Alternative Subgraphs ALBP, Formalization and Resolution Procedures, Doctoral thesis, Technical University of Catalonia, 2007.
- BOUKEF, H., BENREJEB, M., BORNE, P.: Flexible Jobshop Scheduling Problems Resolution Inspired From PSO, Studies In Informatics And Control, Vol. 17(3), 2008, pp.241-252.
- BOUTEVIN, C., GOURGAND, M. and NORRE, S., Bin Packing Extensions for Solving an Industrial Line Balancing Problem, Proceedings of the 5th IEEE International Symposium on Assembly and Task Planning, France, 10-11, 2003.
- DELICE, Y., AYDOGAN, E.K., ÖZCAN, U., ILKAY, M.S., A modified PSO algorithm to mixed-model two sided assembly line balancing, Journal of Intelligent Manufacturing, 2014, pp. 1-22.
- DELORME, X., BATTAÏA, O., DOLGUI, A., Multi-objective Approaches for Design of Assembly Lines, Multi-criteria and Game Theory Applications in Manufacturing and Logistics, Springer, 2014, pp. 31-56.
- DINU, S. and POMAZAN, C.C., A New Hybrid Fuzzy G.A. Optimization Method For Dynamic Economic Dispatch With Valve-Point Loading Effects, MEQAPS ’13, 2013, pp. 217-222.
- DURAN, O. and PEREZ, L., Solution of the spare parts joint replenishment problem with quantity discounts using a discrete particle swarm optimization technique, Studies in Informatics and Control, Vol. 22(4), 2013, pp. 319–328.
- GEN, M., CHENG, R. and LIN, L.: Network Models and Optimization: Multiobjective Genetic Algorithm Approach, Springer, Heidelberg, 2008.
- GUILLERMO CABRERA, G., SILVANA RONCAGLIOLO, D., RIQUELME, J.P., CUBILLOS, C. and SOTO, R., A hybrid PSO simulated annealing algorithm for the probabilistic travelling salesman problem, Studies in Informatics and Control, vol. 21(1), 2012, pp. 49–58.
- KENNEDY, J. and EBERHART, R.C., Particle Swarm Optimization, Proc. of the IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.
- LEVITIN, G., RUBINOVITZ, J. and SHNITS, B., A genetic algorithm for robotic assembly line balancing, European Journal of Operational Research, Vol. 168(3), 2006, pp. 811–825.
- LIM, K.S., BUYAMIN, S., AHMAD, A., NAWAWI, S.W., IBRAHIM, Z., NAIM, F., GHAZALI, K.H. and MOKHTAR, N., An improved VEPSO algorithm for multiobjective optimization problems, Malaysia Japan Academic Scholar Conference (MJASC201), Springer, 2013.
- MATONDANG, M. and JAMBAK, M.I., Soft computing in optimizing assembly lines balancing, Journal of Computer Science, Vol. 6, 2010, pp.141-162.
- PARSOPOULOS, K.E. and VRAHATIS, M.N., Particle swarm optimization method in multi-objective problems, Proceedings of the 2002 ACM symposium on applied computing, 2002, pp.603–607.
- RATNAWEERA, A., HALGAMUGE, S.K. and WATSON, H.C., Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients, IEEE Transactions on Evolutionary Computation, Vol. 8(3), 2004, pp. 240-255.
- SCHOLL, A., Balancing and Sequencing of Assembly Lines, Physica, Heidelberg, 1999.
- SCHOLL, A., Data of assembly line balancing problems, http://alb.mansci.de, Accessed: March 2015.
- SHI, Y.H. and EBERHART, R.C., Empirical study of particle swarm optimization, Proceedings of the IEEE International Conference on Evolutionary Computation, Washington, DC, USA, 1999, pp. 1945–1950.
- SHI, Y. H. and EBERHART, R.C., A modified particle swarm optimizer, Proceedings of the IEEE International Conferences on Evolutionary Computation, Anchorage, Alaska, USA, 1998, pp. 69–73.
- SUWANNARONGSRI, S. and PUANGDOWNREONG, D., Optimal Assembly Line Balancing Using Tabu Search with Partial Random Permutation Technique, Int. Journal of Management Science and Engineering Management, Vol. 3(1), 2008, pp. 3-18.
- YAZDANPARAST, V. and HAJIHOSSEINI, H., Multi-manned production Lines with labour Concentration, Australian Journal of Basic and Applied Sciences, Vol. 5(6), 2011, pp. 839-846.
- ZHANG, Y., WANG, S., and JI, G., A Comprehensive Survey on PSO Algorithm and Its Applications, Mathematical Problems in Eng., Article ID 931256, in press, 2015.