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

Abstract

Assembly line balancing problems (ALBP) are of capital im-\nportance for the industry since the first assembly line for the\nFord T by Henry Ford. Their objective is to optimize the\ndesign of production lines while satisfying the various con-\nstraints. Precedence constraints among the tasks are always\npresent in ALBP. The objective is then to place the tasks\namong various workstations such that the production rate is\nmaximized. This problem can be modeled as a bin pack-\ning problem with precedence constraints (BPPC) where the\nbins are the workstations and the items are the tasks. Paul\nShaw 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\nprecedences and the bin-packing, allowing to solve instances which are otherwise intractable in constraint programming.\nWe 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\nheuristics, 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.