Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups

Jiachen Zhang () and J. Christopher Beck ()
Additional contact information
Jiachen Zhang: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
J. Christopher Beck: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 977-997

Abstract: We propose domain-independent dynamic programming (DIDP) and constraint programming (CP) models to exactly solve type 1 and type 2 assembly line balancing problem with sequence-dependent setup times (SUALBPs). The goal is to assign tasks to assembly stations and to sequence these tasks within each station while satisfying precedence relations specified between a subset of task pairs. Each task has a given processing time and a setup time dependent on the previous task on the station to which the task is assigned. The sum of the processing and setup times of tasks assigned to each station constitute the station time and the maximum station time is called the cycle time. For the type 1 SUALBP (SUALBP-1), the objective is to minimize the number of stations, given a maximum cycle time. For the type 2 SUALBP (SUALBP-2), the objective is to minimize the cycle time, given the number of stations. On a set of diverse SUALBP instances, experimental results show that our approaches significantly outperform the state-of-the-art mixed integer programming models for SUALBP-1. For SUALBP-2, the DIDP model outperforms the state-of-the-art exact approach based on logic-based Benders decomposition. By closing 76 open instances for SUALBP-2, our results demonstrate the promise of DIDP for solving complex planning and scheduling problems.

Keywords: domain-independent dynamic programming; constraint programming; assembly line balancing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0603 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:977-997

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().