Abstract
This paper addresses the balancing problem for straight assembly lines where task times are not known exactly but given by intervals of their possible values. The objective is to assign the tasks to workstations minimizing the number of workstations while respecting precedence and cycle-time constraints. An adaptable robust optimization model is proposed to hedge against the worst-case scenario for task times. To find the optimal solution(s), a breadth-first search procedure is developed and evaluated on benchmark instances. The results obtained are analysed and some practical recommendations are given.
Similar content being viewed by others
References
Ağpak K and Gökçen H (2007). A chance-constrained approach to stochastic line balancing problem. European Journal of Operational Research 180 (3): 1098–1115.
Aissi H, Bazgan C and Vanderpooten D (2009). Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research 197 (2): 427–438.
Alem D and Morabito R (2011). Production planning in furniture settings via robust optimization. Computers & Operations Research 39 (2): 139–150.
Battini D, Faccio M, Ferrari E, Persona A and Sgarbossa F (2007). Design configuration for a mixed-model assembly system in case of low product demand. The International Journal of Advanced Manufacturing Technology 34 (1–2): 188–200.
Baybars I (1986). A survey of exact algorithms for the simple assembly line balancing problem. Management Science 32 (8): 909–932.
Baykasoğlu A and Özbakir L (2007). Stochastic U-line balancing using genetic algorithms. The International Journal of Advanced Manufacturing Technology 32 (1–2): 139–147.
Bertsimas D and Sim M (2003). Robust discrete optimization and network flows. Mathematical Programming 98 (1–3): 49–71.
Bertsimas D and Thiele A (2006). A robust optimization approach to inventory theory. Operations Research 54 (1): 150–168.
Chiang W-C and Urban T (2006). The stochastic U-line balancing problem: A heuristic procedure. European Journal of Operational Research 175 (3): 1767–1781.
Dolgui A and Kovalev S (2012). Min–max and min–max (relative) regret approaches to representatives selection problem. 4OR:A Quarterly Journal of Operations Research 10 (2): 181–192.
Dolgui A and Proth J-M (2010). Supply Chain Engineering: Useful Methods and Techniques. Springer-Verlag: London.
Erel E, Sabuncuoglu I and Sekerci H (2005). Stochastic assembly line balancing using beam search. International Journal of Production Research 43 (7): 1411–1426.
Gabrel V and Murat C (2010). Robustness and duality in linear programming. Journal of the Operational Research Society 61 (8): 1288–1296.
Gamberini R, Gebennini E, Grassi A and Regattieri A (2009). A multiple single-pass heuristic algorithm solving the stochastic assembly line rebalancing problem. International Journal of Production Research 47 (8): 2141–2164.
Gen M, Tsujimura Y and Li Y (1996). Fuzzy assembly line balancing using genetic algorithms. Computers & Industrial Engineering 31 (3–4): 631–634.
Hazır O and Dolgui A (2011). Simple assembly line balancing under uncertainty: A robust approach. In: Proceedings of the International Conference on Industrial Engineering and Systems Management (IESM ’2011), 25–27 May 2011; Metz, France, pp 87–92.
Hazır O, Erel E and Günalay Y (2011). Robust optimization models for the discrete time/cost trade-off problem. International Journal of Production Economics 130 (1): 87–95.
Hop N (2006). A heuristic solution for fuzzy mixed-model line balancing problem. European Journal of Operational Research 168 (3): 798–810.
Jackson J (1956). A computing procedure for a line balancing problem. Management Science 2 (3): 261–271.
Mausser HE and Laguna M (1999). Minimising the maximum relative regret for linear programmes with interval objective function coefficients. Journal of the Operational Research Society 50 (10): 1063–1070.
Moon Y and Yao T (2011). A robust mean absolute deviation model for portfolio optimization. Computers & Operations Research 38 (9): 1251–1258.
Özcan U (2010). Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm. European Journal of Operational Research 205 (1): 81–97.
Scholl A (1999). Balancing and Sequencing of Assembly Lines. 2nd edn. Physica-Verlag: Heidelberg.
Tsujimura Y, Gen M and Kubota E (1995). Solving fuzzy assembly-line balancing problem with genetic algorithms. Computers & Industrial Engineering 29 (1–4): 543–547.
Urban T and Chiang W-C (2006). An optimal piecewise-linear program for the U-line balancing problem with stochastic task times. European Journal of Operational Research 168 (3): 771–782.
Acknowledgements
We thank Chris Yukna for his help in editing the English language used in this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was financially supported by Saint-Étienne Metropole government and the European Project AMEPLM.
Without loss of generality, it is assumed that tasks’ order numbers in the graph of the precedence constraints are topologically sorted.
Rights and permissions
About this article
Cite this article
Gurevsky, E., Hazır, Ö., Battaïa, O. et al. Robust balancing of straight assembly lines with interval task times. J Oper Res Soc 64, 1607–1613 (2013). https://doi.org/10.1057/jors.2012.139
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2012.139