A Global Constraint for Bin-Packing with Precedences: Application to the Assembly Line Balancing Problem

Schaus, Pierre;Deville, Yves
(2008) AAAI-08, Twenty-Third AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence — Location: Chicago, USA (13.July.2008)

Files

aaai2008_binpacking.pdf
  • Open Access
  • Adobe PDF
  • 247.04 KB
Download

Details

Authors
Abstract
Assembly line balancing problems (ALBP) are of capital im- portance for the industry since the first assembly line for the Ford T by Henry Ford. Their objective is to optimize the design of production lines while satisfying the various con- straints. Precedence constraints among the tasks are always present in ALBP. The objective is then to place the tasks among various workstations such that the production rate is maximized. This problem can be modeled as a bin pack- ing problem with precedence constraints (BPPC) where the bins are the workstations and the items are the tasks. Paul Shaw introduced a global constraint for bin-packing (without precedence). Unfortunately this constraint does not capture the precedence constraints of BPPC. In this paper, we first introduce redundant constraints for BPPC combining the precedences and the bin-packing, allowing to solve instances which are otherwise intractable in constraint programming. We also design a global constraint for BPPC, introducing even more pruning in the search tree. We finally used our CP model for BPPC to solve ALBP. We propose two search heuristics, and show the efficiency of our approach on standard ALBP benchmarks. Compared to standard non CP approaches, our method is more flexible as it can handle new constraints that might appear in real applications.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Schaus, P., & Deville, Y. (2008). A Global Constraint for Bin-Packing with Precedences: Application to the Assembly Line Balancing Problem. AAAI-08, Twenty-Third AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, Chicago, USA. https://hdl.handle.net/2078.5/254075