IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v309y2023i1p387-398.html
   My bibliography  Save this article

Exact and heuristic methods for a workload allocation problem with chain precedence constraints

Author

Listed:
  • Pereira, Jordi
  • Ritt, Marcus

Abstract

Industrial manufacturing is often organized in assembly lines where a product is assembled on a sequence of stations, each of which executes some of the assembly tasks. A line is balanced if the maximum total execution time of any station is minimal. Commonly, the task execution order is constrained by precedences, and task execution times are independent of the station performing the task. Here, we consider a recent variation, called the “(Calzedonia) Workload Allocation Problem” (WAP), where the precedences form a chain, and the execution time of a task depends on the worker executing it. This problem was recently proposed by Battarra et al. (2020) and it is a special case of the Assembly Line Worker Assignment and Balancing Problem Miralles et al. (2007) where precedence relations are arbitrary. In this paper we consider the computational complexity of the problem and prove its NP-hardness. To solve the problem, we provide different lower bounds and exact and heuristic procedures. The performance of the proposed methods is tested on previously proposed instances and on new, larger instances with the same characteristics. The results show that the proposed methods can solve instances with up to about 4000 tasks and 29 workers, doubling the size of the instances that previously could be solved to optimality.

Suggested Citation

  • Pereira, Jordi & Ritt, Marcus, 2023. "Exact and heuristic methods for a workload allocation problem with chain precedence constraints," European Journal of Operational Research, Elsevier, vol. 309(1), pages 387-398.
    • Handle: RePEc:eee:ejores:v:309:y:2023:i:1:p:387-398
    DOI: 10.1016/j.ejor.2022.12.035
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722010037
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.12.035?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Borba, Leonardo & Ritt, Marcus & Miralles, Cristóbal, 2018. "Exact and heuristic methods for solving the Robotic Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 146-156.
    2. E. C. Sewell & S. H. Jacobson, 2012. "A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 433-442, August.
    3. Scholl, Armin & Becker, Christian, 2006. "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 666-693, February.
    4. Battaïa, Olga & Dolgui, Alexandre, 2013. "A taxonomy of line balancing problems and their solutionapproaches," International Journal of Production Economics, Elsevier, vol. 142(2), pages 259-277.
    5. Edward P. C. Kao & Maurice Queyranne, 1982. "On Dynamic Programming Methods for Assembly Line Balancing," Operations Research, INFORMS, vol. 30(2), pages 375-390, April.
    6. Miralles, Cristobal & Garcia-Sabater, Jose Pedro & Andres, Carlos & Cardos, Manuel, 2007. "Advantages of assembly lines in Sheltered Work Centres for Disabled. A case study," International Journal of Production Economics, Elsevier, vol. 110(1-2), pages 187-197, October.
    7. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    8. Clautiaux, F. & Detienne, B. & Guillot, G., 2021. "An iterative dynamic programming approach for the temporal knapsack problem," European Journal of Operational Research, Elsevier, vol. 293(2), pages 442-456.
    9. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    10. Becker, Christian & Scholl, Armin, 2006. "A survey on problems and methods in generalized assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 694-715, February.
    11. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    12. James R. Jackson, 1956. "A Computing Procedure for a Line Balancing Problem," Management Science, INFORMS, vol. 2(3), pages 261-271, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Boysen, Nils & Schulze, Philipp & Scholl, Armin, 2022. "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, Elsevier, vol. 301(3), pages 797-814.
    2. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    3. Borba, Leonardo & Ritt, Marcus & Miralles, Cristóbal, 2018. "Exact and heuristic methods for solving the Robotic Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 146-156.
    4. Walter, Rico & Schulze, Philipp & Scholl, Armin, 2021. "SALSA: Combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 295(3), pages 857-873.
    5. Bukchin, Yossi & Raviv, Tal, 2018. "Constraint programming for solving various assembly line balancing problems," Omega, Elsevier, vol. 78(C), pages 57-68.
    6. Eduardo Álvarez-Miranda & Jordi Pereira & Harold Torrez-Meruvia & Mariona Vilà, 2021. "A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations," Mathematics, MDPI, vol. 9(17), pages 1-19, September.
    7. Koltai, Tamás & Dimény, Imre & Gallina, Viola & Gaal, Alexander & Sepe, Chiara, 2021. "An analysis of task assignment and cycle times when robots are added to human-operated assembly lines, using mathematical programming models," International Journal of Production Economics, Elsevier, vol. 242(C).
    8. Battaïa, Olga & Dolgui, Alexandre, 2013. "A taxonomy of line balancing problems and their solutionapproaches," International Journal of Production Economics, Elsevier, vol. 142(2), pages 259-277.
    9. Li, Zixiang & Kucukkoc, Ibrahim & Zhang, Zikai, 2020. "Branch, bound and remember algorithm for two-sided assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 896-905.
    10. Michels, Adalberto Sato & Lopes, Thiago Cantos & Magatão, Leandro, 2020. "An exact method with decomposition techniques and combinatorial Benders’ cuts for the type-2 multi-manned assembly line balancing problem," Operations Research Perspectives, Elsevier, vol. 7(C).
    11. Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    12. Battaïa, Olga & Dolgui, Alexandre, 2022. "Hybridizations in line balancing problems: A comprehensive review on new trends and formulations," International Journal of Production Economics, Elsevier, vol. 250(C).
    13. Raphael Kramer & Mauro Dell’Amico & Manuel Iori, 2017. "A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6288-6304, November.
    14. Parames Chutima, 2022. "A comprehensive review of robotic assembly line balancing problem," Journal of Intelligent Manufacturing, Springer, vol. 33(1), pages 1-34, January.
    15. Pereira, Jordi, 2016. "Procedures for the bin packing problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 250(3), pages 794-806.
    16. Otto, Alena & Li, Xiyu, 2020. "Product sequencing in multiple-piece-flow assembly lines," Omega, Elsevier, vol. 91(C).
    17. Daniel Leitold & Agnes Vathy-Fogarassy & Janos Abonyi, 2019. "Empirical working time distribution-based line balancing with integrated simulated annealing and dynamic programming," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 455-473, June.
    18. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    19. Bautista, Joaquín & Pereira, Jordi, 2011. "Procedures for the Time and Space constrained Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 212(3), pages 473-481, August.
    20. Urban, Timothy L. & Chiang, Wen-Chyuan, 2016. "Designing energy-efficient serial production lines: The unpaced synchronous line-balancing problem," European Journal of Operational Research, Elsevier, vol. 248(3), pages 789-801.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:309:y:2023:i:1:p:387-398. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.