Abstract
In recent years, robots have been widely used in assembly systems called robotic assembly lines, where a set of tasks have to be assigned to stations, and each station needs to select one of the different robots to process the assigned tasks. Our focus is on U-shaped layouts because they are widely employed in many industries due to their efficiency and flexibility compared to straight assembly lines. These lines offer more choices to group operations. A worker can be assigned to multiple stations at the entrance and the exit sides. Moreover, it has been shown experimentally that labor productivity can increase significantly in U-shaped lines. However, in many realistic situations, robots may be unavailable during the scheduling horizon for different reasons, such as breakdowns. This research deals with line balancing under uncertainty. It presents robust optimization models for balancing, sequencing, and robot assignment of U-shaped assembly lines with considering sequencing-dependent setup times, failure robots, and preventive maintenance. The nature of this problem is NP-hard with two objective functions; a multi-objective harmony search is suggested to solve it. The parameters of the proposed algorithm were analyzed using the Taguchi method, and their results were compared with the non-dominated sorting genetic algorithm-II (NSGA-II).
Similar content being viewed by others
Data availability
The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
References
Aghajani, M., Ghodsi, R., Javadi, B.: Balancing of robotic mixed-model two-sided assembly line with robot setup times. Int. J. Adv. Manuf. Technol. 74, 1005–1016 (2014)
Akpinar, S., Bayhan, G.M., Baykasoglu, A.: Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence-dependent setup times between tasks. Appl. Soft Comput. 13(1), 574–589 (2013)
Akpinar, S., Baykasoglu, A.: Modeling and solving mixed-model assembly line balancing problem with setups. Part I: a mixed-integer linear programming model. J. Manuf. Syst. 33(1), 177–187 (2014)
Akpinar, S., Baykasoglu, A.: Modeling and solving mixed-model assembly line balancing problem with setups. Part II: a multiple colony hybrid bees’ algorithm. J. Manuf. Syst. 33(4), 445–461 (2014)
Andres, C., Miralles, C., Pastor, R.: Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur. J. Oper. Res. 187(3), 1212–1223 (2008)
Cakir, B., Altiparmak, F., Dengiz, B.: Multi-objective optimization of a stochastic assembly line balancing: a hybrid simulated annealing algorithm. Comput. Ind. Eng. 60(3), 376–384 (2011)
Chutima, P., Olanviwatchai, P.: Mixed-model U-shaped assembly line balancing problems with coincidence memetic algorithm. J. Softw. Eng. Appl. 3, 347–363 (2010)
Çil, Z.A., Mete, S., Ağpak, K.: Analysis of the type II robotic mixed-model assembly line balancing problem. Eng. Optim. 49(6), 990–1009 (2017)
Gamberini, R., Gebennini, E., Grassi, A., Regattieri, A.: A multiple single-pass heuristic algorithm solving the stochastic assembly line rebalancing problem. Int. J. Prod. Res. 47(8), 2141–2164 (2009)
Geem, Z., Hwangbo, H.: Application of harmony search to multi-objective optimization for satellite heat pipe design. In: Proceedings of US-Korea Conference on Science, Technology and Entrepreneurship, Citeseer, Teaneck, NJ, USA, pp. 1–3 (2006)
Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76, 60–68 (2001)
Geem, Z.W.: Harmony Search Algorithms for Structural Design Optimization, 2010th edn. Studies in Computational Intelligence. Springer, Berlin (2010)
Hamta, N., Ghomi, S.F., Jolai, F., Shirazi, M.A.: A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect. Int. J. Prod. Econ. 141(1), 99–111 (2013)
Hazir, O., Dolgui, A.: Assembly line balancing under uncertainty: robust optimization models and exact solution method. Comput. Ind. Eng. 65, 261–267 (2013)
Hazir, O., Dolgui, A.: A decomposition-based solution algorithm for U-type assembly line balancing with interval data. Comput. Oper. Res. 59, 126–131 (2015)
Jin, W., He, Z., Wu, Q.: Robust optimization of resource-constrained assembly line balancing problems with uncertain operation times. Eng. Comput. (2021). https://doi.org/10.1108/EC-01-2021-0061
Lee, K.S., Geem, Z.W., Lee, S.H., Bae, K.W.: The harmony search heuristic algorithm for discrete structural optimization. Eng. Optim. 37(7), 663–684 (2005)
Li, Z., Ding, R., Floudas, C.A.: A comparative theoretical and computational study on robust counterpart optimization: I. Robust linear optimization and robust mixed-integer linear optimization. Ind. Eng. Chem. Res. 50, 10567–10603 (2011)
Li, Z., Janardhanan, M.N., Tang, Q., Ponnambalam, S.G.: Model and metaheuristics for robotic two-sided assembly line balancing problems with setup times. Swarm Evol. Comput. 50, 100567 (2019)
Lin, M.H., Carlsson, J.G., Ge, D., Shi, J., Tsai, J.F.: A review of piecewise linearization methods. Math. Probl. Eng. (2013). https://doi.org/10.1155/2013/101376
Liu, X., Yang, X., Lei, M.: Optimization of mixed-model assembly line balancing problem under uncertain demand. J. Manuf. Syst. 59, 214–227 (2021)
Lu, Z., Cui, W., Han, X.: production and preventive maintenance scheduling for a single machine with failure uncertainty. Comput. Ind. Eng. 80, 236–244 (2015)
Martino, L., Pastor, P.: Heuristic procedures for solving the general assembly line balancing problem with setups. Int. J. Prod. Res. 48(6), 1787–1804 (2010)
Nilakantan, J.M., Ponnambalam, S.G., Jawahar, N.: Design of energy efficient RAL system using evolutionary algorithms. Eng. Comput. 33(2), 580–602 (2016)
Nilakantan, J., Nielsen, I., Ponnambalam, S.G., Venkataramanaiah, S.: Differential evolution algorithm for solving RALB problem using cost- and time-based models. Int. J. Adv. Manuf. Technol. 89, 311–332 (2016)
Nilakantan, J.M., Ponnambalam, S.G.: Robotic U-shaped assembly line balancing using particle swarm optimization. Eng. Optim. 48, 231–252 (2016)
Nilakantan, M.N., Li, Z., Bocewicz, G., Banaszak, Z., Nielsen, P.: Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times. Appl. Math. Model. 65, 256–270 (2019)
Oksuz, M.K., Buyukozkan, K., Satoglu, S.I.: U-shaped assembly line worker assignment and balancing problem: a mathematical model and two meta-heuristics. Comput. Ind. Eng. 112, 246–263 (2017)
Özcan, U.: Balancing and scheduling tasks in parallel assembly lines with sequence-dependent setup times. Int. J. Prod. Econ. 213, 81–96 (2019)
Özcan, U., Toklu, B.: Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming model. Comput. Oper. Res. 36(3), 1955–1965 (2009)
Özcan, U., Toklu, B.: Balancing two-sided assembly lines with sequence-dependent setup times. Int. J. Prod. Res. 48(18), 5363–5383 (2010)
Pastor, R., Andrés, C., Miralles, C.: Corrigendum to ‘‘Balancing and scheduling tasks in assembly lines with sequence-dependent setup” [European Journal of Operational Research 187 (2008) 1212–1223]. Eur. J. Oper. Res. 201, 336 (2010)
Pereira, J.: the Robust (min-max regret) assembly line worker assignment and balancing problem. Comput. Oper. Res. 93, 27–40 (2018)
Pereira, J., Miranda, E.A.: An exact approach for the robust assembly line balancing problem. Omega 78, 85–98 (2017)
Rabbani, M., Moghaddam, M., Manavizadeh, N.: Balancing of mixed-model two-sided assembly lines with multiple U-shaped layout. Int. J. Adv. Manuf. Technol. 59(9–12), 1191–1210 (2012)
Rabbani, M., Mousavi, Z., Farrokhi-Asl, H.: Multi-objective metaheuristics for solving a type II robotic mixed-model assembly line balancing problem. J. Ind. Prod. Eng. 33(7), 472–484 (2016)
Ricart, J., Huttemann, G., Lima, J., Baran, B.: Multi-objective harmony search algorithm proposals. Electron. Notes Theor. Comput. Sci. 281, 51–67 (2011)
Rubinovitz, J., Bukchin, J.: Design and balancing of robotic assembly lines. In: Proceedings of the Fourth World Conference on Robotics Research, Pittsburgh, PA (1991)
Samouei, P., Ashayeri, J.: Developing optimization & robust models for a mixed-model assembly line balancing problem with semi-automated operations. Appl. Math. Model. 72, 259–275 (2019)
Sarin, S., Erel, E., Dar-El, E.: A methodology for solving single-model, stochastic assembly line balancing problem. Omega 27(5), 525–535 (1999)
Scholl, A., Boysen, N., Fliedner, M.: The sequence-dependent assembly line balancing problem. OR Spect. 30(3), 579–609 (2008)
Scholl, A., Boysen, N., Fliedner, M.: The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics. OR Spectr. 35(1), 291–320 (2013)
Seyed-Alagheband, S., Ghomi, S.F., Zandieh, M.: A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks. Int. J. Prod. Res. 49(3), 805–825 (2011)
Sivasubramani, S., Swarup, K.S.: Multi-objective harmony search algorithm for optimal power flow problem. Int. J. Electr. Power Energy Syst. 33(3), 745–752 (2011)
Sobaszek, Ł, Gola, A., Świć, A.: The algorithms for robust scheduling of production jobs under machine failure and variable technological operation times. In: Machado, J., Soares, F., Trojanowska, J., Ivanov, V. (eds.) Innovations in Industrial Engineering. icieng 2021. Lecture Notes in Mechanical Engineering. Springer, Cham (2022)
Thomopoulos, N.T.: Assembly Line Planning and Control. Springer (2014)
Yang, X.S.: Harmony search as a metaheuristic algorithm. In: Geem, Z.W. (ed.) Music-Inspired Harmony Search Algorithm, Studies in Computational Intelligence, vol. 191, pp. 1–14. Springer (2009)
Yılmaz, Ö.F.: Robust optimization for U-shaped assembly line worker assignment and balancing problem with uncertain task times. Croat. Oper. Res. Rev. (2020). https://doi.org/10.17535/crorr.2020.0018
Yolmeh, A., Kianfar, F.: An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times. Comput. Ind. Eng. 62(4), 936–945 (2012)
Zhang, Z., Tang, Q., Chica, M.: A robust MILP and gene expression programming based on heuristic rules for mixed-model multi-manned assembly line balancing. Appl. Soft Comput. 109, 107513 (2021)
Zhang, Z., Tang, Q., Zhang, L.: Mathematical model and grey wolf optimization for low-carbon and low-noise U-shaped robotic assembly line balancing problem. J. Clean. Prod. 215, 744–756 (2019)
Zhou, B., Wu, Q.: Decomposition-based bi-objective optimization for sustainable robotic assembly line balancing problems. J. Manuf. Syst. 55, 30–43 (2020)
Acknowledgements
The authors like to thank anonymous reviewers for their constructive and valuable comments for improving the manuscript.
Funding
The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.
Author information
Authors and Affiliations
Contributions
The authors confirm contribution to the paper as follows: Study conception and design: PS and MS. Data collection: MS. Analysis and interpretation of results MS. Draft manuscript preparation: PS and MS. All authors reviewed the results and approved the final version of the manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Consent for publication
We, the undersigned, give our consent for the publication of identifiable details, which can include photograph(s) and/or videos and/or case history and/or details within the text to be published in the above journal and article. We confirm that we have seen and been given the opportunity to read both the material and the article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix 1
1.1 Robust counterpart based on box uncertainty set
Li et al. [18] provided a comprehensive study on the robust counterpart reformulation for linear and mixed-integer linear programming using different uncertainty sets. The proposed uncertainty sets are formulated based on different norms of the perturbation variables. The box uncertainty set is formulated based on the Chebyshev norm of the perturbation variables. It is presented as follows:
where \(\psi \) is the adjustable parameter that controls the uncertainty set size, hence controlling the conservativeness of the solution. If \(\psi \) = 1, the resulting uncertainty set is equivalent to the interval uncertainty set. The robust counterpart based on the box uncertainty set is given as follows:
It is linearized as follows:
1.2 Robust counterpart based on ellipsoidal uncertainty set
Li et al. [18] studied the robust counterpart formulation under the ellipsoidal uncertainty set. The ellipsoidal uncertainty set is formulated based on the Euclidean norm of the perturbation variables and is defined as follows:
where is the radius of the uncertainty set; it also represents the degree of the conservativeness of the solution. The robust counterpart reformulation based on the ellipsoidal uncertainty set is given as follows:
1.3 Robust counterpart based on polyhedral uncertainty set
Li et al. [18] also discussed the robust counterpart formulation under the pure polyhedral uncertainty set. The polyhedral uncertainty set is formulated based on the rectilinear norm of the perturbation variables. It is defined as:
The geometric relationship between box, ellipsoidal and polyhedral uncertainty sets is shown in Fig.
12.
Appendix 2
See Tables
12 and
13.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Samouei, P., Sobhishoja, M. Robust counterpart mathematical models for balancing, sequencing, and assignment of robotic U-shaped assembly lines with considering failures and setup times. OPSEARCH 60, 87–124 (2023). https://doi.org/10.1007/s12597-022-00609-w
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12597-022-00609-w