Constraint programming for solving various assembly line balancing problems

Yossi Bukchin and Tal Raviv

Omega, 2018, vol. 78, issue C, 57-68

Abstract: In this paper, the constraint programming (CP) approach is applied for the simple assembly line balancing problem (SALBP) as well as some of its generalizations. CP is a rich modeling language that enables the formulation of general combinatorial problems and is coupled with a strong set of solution methods that are available through general purpose solvers. The proposed formulations are conversions of well-known mixed integer programming (MILP) formulations to CP, along with a new set of constraints that helps the CP solver to converge faster. As a generic solution method, we compare its performance with the best known generic MILP formulations and show that it consistently outperforms MILP for medium to large problem instances. A comparison with SALOME, a well-known custom-made algorithm for solving the SALBP-1, shows that both approaches are capable of efficiently solving problems with up to 100 tasks. When 1000-task problems are concerned, SALOME provides better performance; however, CP can provide relatively good close to optimal solutions for multiple combinations of problem parameters. Finally, the generality of the CP approach is demonstrated by some adaptations of the proposed formulation to other variants of the assembly line balancing problem including the U-shaped assembly line balancing problem and the task assignment and equipment selection problem.

Keywords: Constraint programming (CP); Assembly line balancing; Mixed-integer linear programming (MILP); Branch & bound (B&B) (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048316306363
Full text for ScienceDirect subscribers only

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:eee:jomega:v:78:y:2018:i:c:p:57-68

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.06.008

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().