Discrete Optimization
Procedures for the bin packing problem with precedence constraints

https://doi.org/10.1016/j.ejor.2015.10.048Get rights and content

Highlights

  • The bin packing problem with precedence constraints is investigated.

  • Its relationship with the assembly line balancing problem is considered.

  • New dominance rules and lower bounds are developed.

  • A dynamic programming based heuristic and a branch-and-bound method are proposed.

  • The results show that the methods outperforms all previous approaches.

Abstract

The bin packing problem with precedence constraints (BPP-P) is a recently proposed variation of the classical bin packing problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later bins than their predecessors.

In this paper we propose a dynamic programming based heuristic, and a modified exact enumeration procedure to solve the problem. These methods make use of several new lower bounds and dominance rules tailored for the problem in hand. The results of a computational experiment show the effectiveness of the proposed methods, which are able to close all of the previous open instances from the benchmark instance set within very reduced running times.

Introduction

The bin packing problem with precedence constraints (BPP-P) can be described as follows: a set of items, each with a non-negative weight, has to be packed into consecutively numbered bins, each with an identical capacity that limits the total weight of the items packed into the bin. Each item also presents a set of precedence relations: that is, items that need to be packed into a lower numbered bin than the item in question. The objective of the problem is to find the lowest number of bins accepting a packing of items such that all capacity constraints and precedence relations are satisfied.

The BPP-P is a closely related problem to two classical problems: (1) it can be seen as an extension of the bin packing problem in which strict precedence constraints have been incorporated; and (2) it corresponds to the simple assembly line balancing problem (SALBP-1) with a different definition of the precedence relations.

The SALBP-1 is a basic formulation of the assembly line balancing problem (ALBP). ALBPs try to find an optimal assignment of tasks (the items) among the workstations (the bins) so as to maximize the efficiency of the line. In the SALBP-1, tasks have an operation time (their weight); the workstations have a maximum allotted time to perform the tasks equal to the cycle time (the capacity of the bin); the precedence constraints represent technological constraints that require some tasks to be performed after other tasks have been finished; and the efficiency of the line is measured by minimizing the number of workstations required (the number of bins). The main difference between the SALBP-1 and the BPP-P is the rendition of the precedence constraints: that is, while the precedence relations in the SALBP-1 correspond to inequality constraints (≤), the precedence constraint in BPP-P correspond to strict inequality constraints (<).

While bin packing and line balancing problems have been widely studied in the literature, see Coffman, Galambos, Martello, and Vigo (1999), Valério De Carvalho (2002) and Clautiaux, Alves, and Valério de Carvalho (2010) for reviews on different aspects of the BPP, Dolgui and Battaïa (2013) for a review on the ALBP, and Scholl and Becker (2006) for a survey specifically geared towards the SALBP-1, the BPP-P has received much less attention, even when the BPP-P is, or is a part of, the basic formulation of several theoretical and practical problems.

A similar problem was introduced in the mid 70’s, see Garey, Graham, and Johnson (1976), in order to model single resource constrained multiprocessor scheduling problems. This work studies a generalization of the BPP-P and its relationship with the BPP, and it also provides a heuristic with a 2.7 asymptotic performance guarantee. A similar line of work was followed by Augustine, Banerjee, and Irani (2009) in which the BPP-P is identified as the model of an FPGA dynamic reconfiguration problem, and in which an adaptation of the BPP next fit heuristic is shown to have an absolute performance guarantee of 3.

The literature also covers some recent attempts to solve the problem using exact and metaheuristic methods. In Dell’Amico, Díaz, and Iori (2012), the authors put forward an variable neighbourhood search (VNS) metaheuristic, along with a branch-and-bound method to solve the problem. The branch-and-bound relies on several new bounds which combine classical BPP bounds with the additional considerations derived from the precedence relations. The results show that the proposed metaheuristic and lower bounds are able to close 245 of the 269 instances derived from the classical SALBP benchmark set, see Scholl and Becker (2006). Furthermore, the branch-and-bound reaches optimality for another 21 instances within a two-hours per instance time limit.

Other authors have considered problems which include the BPP-P as a subproblem. Specifically, the ALBP literature covers several cases in which the strict inequality precedence constraints from the BPP-P portray real characteristics of the assembly work. According to Dell’Amico et al. (2012) and Tirpak (2008) reports the design and application of an automated assembly line balancing tool in which some of the tasks feature strict precedence constraints. Another classical ALBP problem in which strict precedence relations appear is the transfer assembly line balancing problem. Transfer assembly lines correspond to a special type of assembly lines in which the tasks are performed by robots with multiple tools. A frequent situation, see for example Borisovsky, Dolgui, and Kovalev (2012); Delorme, Dolgui, and Kovalyov (2012), corresponds to the assignment of a single robot in each workstation that performs all of its assigned tasks in parallel, thus forcing strict inequality precedence constraints.

While BPP and SALBP-1 solution procedures are not directly applicable to the BPP-P, their tight relationship suggests that some of the successful techniques used for these problems could be successfully applied to the BPP-P. Therefore, we proceed to discuss some references from these two problems which are relevant for the present study.

Enumeration based procedures constitute the state-of-the-art for the SALBP-1. The branch, bound and remember procedure, see Morrison, Sewell, and Jacobson (2014); Sewell and Jacobson (2012), is the current best performing exact method for the problem, and the bounded dynamic programming, see Bautista and Pereira (2009), together with a recent modification of a truncated branch-and-bound known as the multi-Hoffmann heuristic, see Sternatz (2014), are the best performing heuristic methods.

All of these methods, to different extent, make use of lower bounds and dominance rules to avoid, or to prioritize, the enumeration of parts of the search tree; to detect equivalent partial solutions, and to certify the optimality of the solutions found. We refer the reader to Pereira (2015) for a comprehensive comparison of different lower bounding procedures for the SALBP-1, and to Scholl and Becker (2006); Sewell and Jacobson (2012); Vilà and Pereira (2013); 2014) for different dominance rules used to detect symmetries and other relations among partial solutions.

The best performing methods to solve the classical BPP correspond to column generation approaches, see Valério De Carvalho (2002), but there is a broad literature on fast lower bounds which can be used on enumeration based procedures, see for example Fekete and Schepers (2001). Other packing problems feature similar characteristics to the BPP-P. Among them, we highlight the bin packing problem with conflicts (BBPC). In this problem the classical BPP formulation is extended to consider that some items cannot share a bin. The relationship between the BPPC and the BPP-P was used in Dell’Amico et al. (2012) to obtain a maximum flow based lower bound for the BPP-P which will be discussed in Section 3.1.

In this paper we address the BPP-P and offer several novel preprocessing rules, dominance rules, lower bounds and upper bounds to those found in the literature. First, we propose a preprocessing rule to reduce the number of items of the instance. Second, we propose two different lower bounds: one based on the one-machine lower bound for the SALBP, and another one based on the Dantzig–Wolfe reformulation of the problem. Third, we put forward a constructive based method built upon a dynamic programming (DP) formulation of the BPP-P. Fourth, we introduce several dominance rules in the procedure proposed in Dell’Amico et al. (2012) as well as a different exploration method based on the successful branch, bound and remember, see Sewell and Jacobson (2012). Among the proposed dominance rules, a generalization of the Jackson dominance rule, Scholl and Becker (2006), which is applicable to the SALBP and other ALBPs, is considered. Fifth, the branch-and-bound makes use of the states explored by the DP-based heuristic, and avoids work repetition between the heuristic and the exact phase of the proposed method.

This work also describes an extensive computational experiment with the proposed procedures. A first experiment using the classical SALBP instances, see Scholl and Becker (2006), allows us to compare the proposed algorithms to the results found in Dell’Amico et al. (2012). The results show that the proposed algorithms provide better lower and upper bounds in much shorter computational times than the previously available methods, allowing us to close all open instances from this set. A second experiment using a new instance set proposed in Otto, Otto, and Scholl (2013) allows us to study the effect of different characteristics of the instances into the quality of the proposed solutions. The results of this experiment show that the method provides very good solutions on a broad set of instances with different characteristics.

The remainder of the paper is structured as follows. Section 2 is devoted to the description of the problem, its different mathematical formulations of the problem and the notation used throughout the paper. Section 3 studies different lower bounds, while Section 4 describes both the upper bounds and dominance rules derived from the DP formulation of the problem. Section 5 gives a description of the branch-and-bound algorithm and its main differences with previous proposed methods. In Section 6 we document the computational experiment. Finally, Section 7 gives some conclusions.

Section snippets

Problem formulation

A BPP-P instance is defined by n items, each with an associated non-negative weight wi, iV=[1:n]. Note that throughout the paper for any pair of integers i, j: ij, we denote set {i,i+1,,j} as [i: j].

Some items also present precedence relations among them. The set of immediate predecessors, and the set of immediate successors of item i are denoted as Pi, Fi; while the set of all predecessor and successor relations of item i (which can be obtained by transitivity) are denoted as Pi* and Fi*.

Lower bounds

In this section we introduce some of the lower bounds available in the literature for the BPP-P as well as two novel approaches which can be seen as adaptations of existing lower bounds for the SALBP-1. Note that other bounding methods are possible, as the BPP and the SALBP-P are valid lower bounds for the BPP-P, and thus any bounding method for these two problems could be used to obtain bounds.

Description of the algorithm

The main drawback of dynamic programming (DP) approaches lies on the large state space needed to enumerate, a phenomenon coined by Bellman as the “curse of dimensionality”. Several techniques exist to partially palliate the problem, like state space relaxation, Christofides, Mingozzi, and Toth (1981), dynasearch, Congram, Potts, and van de Velde (2002), restricted dynamic programming Gromicho, van Hoorn, Kok, and Schutten (2012), or bounded dynamic programming, Bautista and Pereira (2009).

Branch-and-bound algorithm

When the previous methods (upper and lower bounds) fail to verify the optimality of the incumbent solution, we rely on an enumeration based approach to verify optimality. The proposed method corresponds to a branch-and-bound approach known as branch, bound and remember, see Morrison et al. (2014); Sewell and Jacobson (2012). The main characteristic of the branch, bound and remember approach is the use of a memory structure that stores already explored partial solutions. Although this feature is

Computational experiment

In order to assess the quality of the final method, the proposed algorithms were coded in C++, compiled using GCC 4.7 and run on an Intel Xeon machine with an 8-core 2.66 gigahertz CPU and 32-gigabytes RAM, running the Linux operating system. Note that the code does not make use of any form of parallelism, and thus only one core is effectively used. Furthermore, the limit on the number of states in memory leads to a lower memory use than the total available memory (maximum reported usage was

Conclusions

In this work we have investigated the bin packing problem with precedence constraints, a recently proposed generalization of the bin packing problem, (Dell’Amico et al., 2012), which models some characteristics of several scheduling and assembly line balancing problems. In order to provide a solution procedure for the problem, two lower bounds derived from the simple assembly line balancing problem as well as a dynamic programming based heuristic and an branch, bound and remember enumeration

Aknowledgements

This research has been partially funded by the research grant “Heterogeneous assembly line balancing problems with process selection features” number 1150306, from the Fondo Nacional de Desarrollo Científico y Tecnológico of the Ministry of Education of Chile.

References (35)

Cited by (0)

View full text