Skip to main content

Advertisement

Springer Nature Link
Log in

Robust counterpart mathematical models for balancing, sequencing, and assignment of robotic U-shaped assembly lines with considering failures and setup times

  • Application Article
  • Published:
OPSEARCH Aims and scope Submit manuscript

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).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

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

  1. 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)

    Article  Google Scholar 

  2. 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)

    Article  Google Scholar 

  3. 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)

    Article  Google Scholar 

  4. 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)

    Article  Google Scholar 

  5. 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)

    Article  Google Scholar 

  6. 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)

    Article  Google Scholar 

  7. Chutima, P., Olanviwatchai, P.: Mixed-model U-shaped assembly line balancing problems with coincidence memetic algorithm. J. Softw. Eng. Appl. 3, 347–363 (2010)

    Article  Google Scholar 

  8. Ç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)

    Article  Google Scholar 

  9. 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)

    Article  Google Scholar 

  10. 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)

  11. Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76, 60–68 (2001)

    Article  Google Scholar 

  12. Geem, Z.W.: Harmony Search Algorithms for Structural Design Optimization, 2010th edn. Studies in Computational Intelligence. Springer, Berlin (2010)

  13. 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)

    Article  Google Scholar 

  14. Hazir, O., Dolgui, A.: Assembly line balancing under uncertainty: robust optimization models and exact solution method. Comput. Ind. Eng. 65, 261–267 (2013)

    Article  Google Scholar 

  15. 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)

    Article  Google Scholar 

  16. 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

    Article  Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. 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)

    Article  Google Scholar 

  19. 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)

    Article  Google Scholar 

  20. 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

    Article  Google Scholar 

  21. Liu, X., Yang, X., Lei, M.: Optimization of mixed-model assembly line balancing problem under uncertain demand. J. Manuf. Syst. 59, 214–227 (2021)

    Article  Google Scholar 

  22. 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)

    Article  Google Scholar 

  23. 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)

    Article  Google Scholar 

  24. Nilakantan, J.M., Ponnambalam, S.G., Jawahar, N.: Design of energy efficient RAL system using evolutionary algorithms. Eng. Comput. 33(2), 580–602 (2016)

    Article  Google Scholar 

  25. 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)

    Article  Google Scholar 

  26. Nilakantan, J.M., Ponnambalam, S.G.: Robotic U-shaped assembly line balancing using particle swarm optimization. Eng. Optim. 48, 231–252 (2016)

    Article  Google Scholar 

  27. 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)

    Article  Google Scholar 

  28. 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)

    Article  Google Scholar 

  29. Özcan, U.: Balancing and scheduling tasks in parallel assembly lines with sequence-dependent setup times. Int. J. Prod. Econ. 213, 81–96 (2019)

    Article  Google Scholar 

  30. Ö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)

    Article  Google Scholar 

  31. Özcan, U., Toklu, B.: Balancing two-sided assembly lines with sequence-dependent setup times. Int. J. Prod. Res. 48(18), 5363–5383 (2010)

    Article  Google Scholar 

  32. 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)

    Article  Google Scholar 

  33. Pereira, J.: the Robust (min-max regret) assembly line worker assignment and balancing problem. Comput. Oper. Res. 93, 27–40 (2018)

    Article  Google Scholar 

  34. Pereira, J., Miranda, E.A.: An exact approach for the robust assembly line balancing problem. Omega 78, 85–98 (2017)

    Article  Google Scholar 

  35. 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)

    Article  Google Scholar 

  36. 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)

    Google Scholar 

  37. Ricart, J., Huttemann, G., Lima, J., Baran, B.: Multi-objective harmony search algorithm proposals. Electron. Notes Theor. Comput. Sci. 281, 51–67 (2011)

    Article  Google Scholar 

  38. Rubinovitz, J., Bukchin, J.: Design and balancing of robotic assembly lines. In: Proceedings of the Fourth World Conference on Robotics Research, Pittsburgh, PA (1991)

  39. 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)

    Article  Google Scholar 

  40. Sarin, S., Erel, E., Dar-El, E.: A methodology for solving single-model, stochastic assembly line balancing problem. Omega 27(5), 525–535 (1999)

    Article  Google Scholar 

  41. Scholl, A., Boysen, N., Fliedner, M.: The sequence-dependent assembly line balancing problem. OR Spect. 30(3), 579–609 (2008)

    Article  Google Scholar 

  42. 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)

    Article  Google Scholar 

  43. 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)

    Article  Google Scholar 

  44. 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)

    Article  Google Scholar 

  45. 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)

    Google Scholar 

  46. Thomopoulos, N.T.: Assembly Line Planning and Control. Springer (2014)

    Book  Google Scholar 

  47. 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)

    Chapter  Google Scholar 

  48. 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

    Article  Google Scholar 

  49. 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)

    Article  Google Scholar 

  50. 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)

    Article  Google Scholar 

  51. 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)

    Article  Google Scholar 

  52. Zhou, B., Wu, Q.: Decomposition-based bi-objective optimization for sustainable robotic assembly line balancing problems. J. Manuf. Syst. 55, 30–43 (2020)

    Article  Google Scholar 

Download references

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

  1. Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

    Parvaneh Samouei & Mahsa Sobhishoja

Authors
  1. Parvaneh Samouei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mahsa Sobhishoja
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Correspondence to Parvaneh Samouei.

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:

$$ \left\| {\xi_{ij} } \right\|_{\infty } = \left| {\xi_{ij} } \right| \ll \psi \forall i = 0, 1, 2, \ldots ,m; \xi_{ij} \in \left[ { - 1,1} \right] $$
(53)

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:

$$ \begin{gathered} \min z \hfill \\ s.t. \hfill \\ z \ge \mathop \sum \limits_{j} a_{0j} x_{j} + b_{0} + \psi_{0} \left( {\mathop \sum \limits_{j} \hat{a}_{0j} \left| {x_{j} } \right| + \hat{b}_{0} } \right) \hfill \\ \mathop \sum \limits_{j} a_{ij} x_{j} + \psi_{i} \mathop \sum \limits_{j} \hat{a}_{ij} \left| {x_{j} } \right| \le b_{i} - \psi_{i} \hat{b}_{i} \forall i = 1, \ldots ,m \hfill \\ \end{gathered} $$
(54)

It is linearized as follows:

$$ \begin{gathered} \min z \hfill \\ s.t. \hfill \\ z \ge \mathop \sum \limits_{j} a_{0j} x_{j} + b_{0} + \psi_{0} \left( {\mathop \sum \limits_{j} \hat{a}_{0j} u_{j} + \hat{b}_{0} } \right) \hfill \\ \mathop \sum \limits_{j} a_{ij} x_{j} + \psi_{i} \mathop \sum \limits_{j} \hat{a}_{ij} u_{j} \le b_{i} - \psi_{i} \hat{b}_{i} \forall i = 1, \ldots ,m \hfill \\ - u_{j} \le x_{j} \le u_{j} \hfill \\ u_{j} \ge 0 \hfill \\ \end{gathered} $$
(55)

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:

$$ \left\| {\xi _{{ij}} } \right\|_{2} = \sqrt {\sum\limits_{j} {\xi _{{ij}}^{2} } } \le \Omega \forall i = 0,1,2, \ldots ,m;\;\xi _{{ij}} \in \left[ { - 1,1} \right] $$
(56)

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:

$$ \begin{gathered} {\text{min }}z \hfill \\ s.t. \hfill \\ z \ge \mathop \sum \limits_{j} a_{0j} x_{j} + b_{0} + {\Omega }_{0} \left( {\sqrt {\mathop \sum \limits_{j} \left( {\hat{a}_{0j} x_{j} } \right)^{2} + \hat{b}_{0}^{2} } } \right) \hfill \\ \mathop \sum \limits_{j} a_{ij} x_{j} + {\Omega }_{i} \mathop \sum \limits_{j} \left( {\hat{a}_{ij} x_{j} } \right)^{2} \le b_{i} - {\Omega }_{i} \hat{b}_{i}^{2} \forall i = 1, \ldots ,m \hfill \\ \end{gathered} $$
(57)

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:

$$ \left\| {\xi_{ij} } \right\|_{1} = \mathop \sum \limits_{j}^{n} \left| {\xi_{ij} } \right| \le {\Gamma }_{i} \forall i = 0, 1, 2, \ldots ,m; \xi_{ij} \in \left[ { - 1, 1} \right] $$
(58)
$$ \begin{gathered} \min z \hfill \\ s.t. \hfill \\ z \ge \mathop \sum \limits_{j} a_{0j} x_{j} + b_{0} + \Gamma_{0} t_{0} \hfill \\ t_{0} \ge \hat{a}_{0j} \left| {x_{j} } \right| \;and\; t_{0} \ge \hat{b}_{0} \hfill \\ \mathop \sum \limits_{j} a_{ij} x_{j} + \Gamma_{i} t_{i} \le b_{i} \hfill \\ t_{i} \ge \mathop \sum \limits_{j}^{n} \hat{a}_{ij} \left| {x_{j} } \right|\;and\;t_{i} \ge \hat{b}_{i} \forall i = 1, \ldots ,m \hfill \\ \end{gathered} $$
(59)

The geometric relationship between box, ellipsoidal and polyhedral uncertainty sets is shown in Fig. 

Fig. 12
figure 12

Illustration of box, ellipsoidal and polyhedral uncertainty set

Full size image

12.

Appendix 2

See Tables

Table 12 Comparison of two algorithms for the first objective function (cycle time) for different conditions
Full size table

12 and

Table 13 Comparison of two algorithms for the second objective function (cost) for different conditions
Full size table

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12597-022-00609-w

Keywords

Search

Navigation