Computers & Industrial Engineering 66 (2013) 158–170

Contents lists available at SciVerse ScienceDirect

Computers & Industrial Engineering journal homepage: www.elsevier.com/locate/caie

Iterative approaches for solving a multi-objective 2-dimensional vector packing problem
Nadia Dahmani a, François Clautiaux b,⇑, Saoussen Krichen a, El-Ghazali Talbi b a b

Institut Supérieur de Gestion de Tunis, LARODEC, 41 Avenue de la Liberté, Cité Bouchoucha, 2000 Le Bardo, Tunisie Université de Lille 1, LIFL CNRS UMR 8022, INRIA Lille-Nord Europe, Bâtiment INRIA, Parc de la Haute Borne, 59655 Villeneuve d’Ascq, France

a r t i c l e

i n f o

a b s t r a c t
In this paper, we address a bi-objective 2-dimensional vector packing problem (Mo2-DBPP) that calls for packing a set of items, each having two sizes in two independent dimensions, say, a weight and a height, into the minimum number of bins. The weight corresponds to a ‘‘hard’’ constraint that cannot be violated while the height is a ‘‘soft’’ constraint. The objective is to find a trade-off between the number of bins and the maximum height of a bin. This problem has various real-world applications (computer science, production planning and logistics). Based on the special structure of its Pareto front, we propose two iterative resolution approaches for solving the Mo2-DBPP. In each approach, we use several lower bounds, heuristics and metaheuristics. Computational experiments are performed on benchmarks inspired from the literature to compare the effectiveness of the two approaches. Ó 2013 Elsevier Ltd. All rights reserved.

Article history: Received 21 May 2012 Received in revised form 2 March 2013 Accepted 26 May 2013 Available online 4 June 2013 Keywords: 2-Dimensional vector packing problem Multi-objective optimization Lower bounds Heuristics Metaheuristics

1. Introduction In this paper, we address a new bi-objective version of the 2dimensional vector packing problem (2-DVPP). A 2-DVPP instance consists of a set {1, . . . , N} of items i with two sizes ci and hi, and an unlimited number of bins with two sizes C and H. The objective is to pack the items into a minimum number of bins without violating the capacity constraint of each dimension. The problem is a generalization of the classical one-dimensional bin packing problem (BPP), and thus is NP-hard in the strong sense (see Garey & Johnson, 1979). Different greedy heuristics and exact methods have been proposed to solve d-DVPPs or more precisely the 2-DVPP (Alves, de Carvalho, Clautiaux, & Rietz, 2013; Caprara & Toth, 2001; Garey, Graham, Johnson, & Andrew, 1976; Spieksma, 1994). The d-DVPP arises in a large variety of real-world applications in computer science (assignment of jobs to processors, or virtual machine placement Lee et al., 2011), production planning and logistics (packing problems), or in steel industry (Chang, Hwang, & Park, 2005). The literature on 2-DVPP problems focuses on the minimization of wasted space. However, in real-world applications, there are often conflicting criteria to be satisfied. In the computer processor selection with job assignment context for example, a finite number
⇑ Corresponding author. Tel.: +33 359632224; fax: +33 359632221.
E-mail address: francois.clautiaux@univ-lille1.fr (F. Clautiaux). 0360-8352/$ - see front matter Ó 2013 Elsevier Ltd. All rights reserved. http://dx.doi.org/10.1016/j.cie.2013.05.016

of real-time computer jobs (items) have to be assigned to a group of processors (bins). Each job has its own resource demands for CPU time and memory. Each processor has its time processing and memory resource constraints. The jobs must all run simultaneously and, for a fast time response, all must be memory-resident at all times. A decision maker may be interested in solutions with a good trade-off between the number of processors and the completion time. In this paper, we consider a bi-objective version of the 2-dimensional vector packing problem, denoted as multi-objective two dimensional vector packing problem (Mo2-DBPP). We relax the height constraint, which becomes an objective to minimize. The objective is to find a trade-off between the number of used bins and the maximum height of a bin. Only few works, published in the last 10 years, were dedicated to multi-objective bin packing problems. In addition to the the minimization of the number of used bins, other objectives were addressed. For instance, Liu, Tan, Huang, Goh, and Ho (2008) pointed out the issue of the balance of the bins, and tried to minimize the average deviation of center of gravity from an ideal position. The authors addressed the multi-objective problem using an evolutionary particle swarm optimization approach. Geiger (2007) focused on minimizing the heterogeneousness of the elements in each bin. An extension of the Best-Fit approximation algorithm was presented to solve the problem. In Sathe, Schenk, and Burkhart (2009), a cost function designed for the special real case study in the automobile sheet metal forming processes has

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

159

to be minimized. The problem was solved by using a combination of a multi-objective evolutionary algorithm with a clustering algorithm. Khanafer, Clautiaux, Hanafi, and Talbi (2012), addressed a bi-objective version of the bin packing with conflicts where the second objective was the minimization of the number of violated conflicts when the number of bins is fixed. Several heuristics, and an exact method were proposed to solve the problem. The previous methods proposed to solve multi-objective packing problems are dedicated to a specific cost function. They cannot be applied directly to our two-dimensional problem, since the subproblems to solve have a totally different structure. In the Mo2-DBPP, the number of optimal points in the objective space is bounded by the number of items. This property led us to design two different resolution approaches that generate potentially efficient solutions by iteratively solving a mono-objective problem. The first method consists in iterating over the possible values of maximum height of a bin. This method gives rise to a pseudo-polynomial number of 2-DVPPs to solve iteratively. The second method consists in optimizing the maximum height of a bin while iteratively fixing the number of used bins. In this method, a fewer number of height minimization problems (MHPP) have to be solved. The purpose of this paper is to compare the efficiency and the effectiveness of these two iterative approaches. For each one, we present integer linear programming models, several lower bounds and heuristic algorithms based on adaptations of vector packing and scheduling algorithms. We also devised three different metaheuristics: one population based algorithm and two local search methods. To show the effectiveness of our algorithmic approaches, an experimental investigation is performed on various benchmarks inspired from the literature (Caprara & Toth, 2001). We compare the different algorithms dedicated to each approach, and then compare the two approaches in terms of computing time and solution quality. The remainder of the paper is organized as follows: Section 2 provides a mathematical formulation of Mo2-DBPP and a general description of the two resolution approaches. Sections 3 and 4 deal with the iterative vector-packing and min-height based approaches. For each approach, we introduce heuristics and lower bounds for the related problems. In Section 5, a description of different metaheuristic algorithms is presented. Finally, our computational experiments are reported in Section 6. 2. Problem formulation and resolution approaches In this section, we present the mathematical formulation of Mo2-DBPP. We then give a general description of our two iterative approaches. 2.1. Definition and model for the Mo2-DBPP The Mo2-DBPP can be described as follows. Let {1, . . . , N} be a set of items. Each item i has a weight ci and a height hi. Let also f1; . . . ; Mg be a set of bins, where M is an upper bound on the number of bins that can be used ðM 6 NÞ. Each bin j has a weight capacity C. The two conflicting objectives that have to be simultaneously minimized are the number of used bins and the maximum height of a bin. We now give a formal description of the problem, using binary variables xij that take the value of 1 if item i has been placed in bin j, 0 otherwise, and binary variables yj that take the value of 1 if bin j is used, 0 otherwise. Integer variable H expresses the maximum height loaded into one bin. A mathematical formulation of the Mo2-DBPP can be stated as follows:

min

* + M X yj ; H j¼1 M X xij ¼ 1; j¼1 N X ci xij 6 Cyj ; i¼1 N X hi xij À H 6 0; i¼1

ð1Þ

s:t:

i ¼ 1; . . . ; N j ¼ 1; . . . ; M j ¼ 1; . . . ; M j ¼ 1; . . . ; M

ð2Þ ð3Þ ð4Þ ð5Þ ð6Þ ð7Þ

xij 2 f0; 1g; yj 2 f0; 1g; H2N

i ¼ 1; . . . ; N; j ¼ 1; . . . ; M

The two objective functions minimize concurrently the number of used bins and the maximum height H of a bin. The partition constraints (2) ensure that each item i is assigned to exactly one bin j. Inequalities (3) express the maximum weight capacity for each bin. Inequalities (4) mean that each item size combination into a single bin j must not exceed the maximum height H. Since we are handling a multi-objective problem, not only one optimal solution s exists but a set S of efficient solutions that minimize both objective functions. For a given solution s, let f1(s) be the number of bins in this solution and f2(s) the maximum height of a bin. A solution s 2 S is evaluated with respect to a vector (f1(s), f2(s)), and a decision vector s dominates a vector s0 if fk(s) 6 fk(s0 ) "k 2 {1, 2} and $ljfl(s) < fl(s0 ) for l – k. Hence, solving the problem aims to identify all the efficient outcomes or the Pareto optimal set Z Ã . A maximal set of non-dominated solutions will be denoted as Pareto approximation set X Ã . 2.2. Iterative resolution approaches The number m of bins used is bounded by the number of items (trivially m 6 N). This means that the size of the Pareto front is at

Fig. 1. Illustration of the two resolution approaches for Example 1.

160

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

most linear in the size of the data. This justifies the application of an iterative approach. We used two different resolution approaches. The first one consists in iterating over the possible values of maximum height H. At each iteration, a 2-DVPP is solved. A second alternative is to optimize the maximum height H while iteratively fixing the number of used bins m. The problem to be solved is denoted as the Min-height packing problem (MHPP). These methods are similar to the classical Constraint method (Haimes, Lasdon, & Wismer, 1971), but we add an equality constraint on the first objective instead of an inequality. The main objective of this paper is to compare these two iterative approaches for generating the Pareto approximation set X Ã . Example 1. Consider the following instance with N = 8, C = 100. The vector sizes of each item i 2 {1, . . . , N}: (ci, hi) = {(20, 40); (60, 30); (20, 30); (40, 60); (10, 50); (30, 40); (10, 10); (10, 60)}. The corresponding Pareto front depicted in Fig. 1 has been obtained by applying the proposed resolution approaches. In this example, we found a non-dominated solution for each possible number of bins between the extrema, which is not the case in general.

3.2. Lower bounds In this section, we present various lower bounds for the 2-DVPP from the literature, based on combinatorial considerations or linear programming. The first lower bound was proposed by Spieksma (1994) and defined as the maximum between the continuous lower bound values of the two one-dimensional bin packing problems obtained by relaxing the first and the second dimension.

&$P LB1 ¼ max

i¼1;...;N

ci

C

% $P %' i¼1;...;N hi ; H

Caprara and Toth (2001) describe improved lower bounding procedures based on extensions of BPP lower bounds and an integer programming formulation whose linear programming relaxation can be solved by column generation. Recently, Alves et al. (2013) used the concept of dual-feasible functions (see Clautiaux, Alves, & Valério de Carvalho, 2010) to compute lower bounds for k-dimensional vector packing problems. 3.3. Heuristics

3. An iterative vector-packing based approach 3.1. Outline of the method The resolution approach starts by computing an upper bound U and a lower bound L for the height H, and then iterates over all possible values. The lower bound L is directly given by the item of maximum height. A naive upper bound would sum the heights of all items. This bound can be improved by considering the fact that not all items can fit together in the bin because of the weight constraint. Our upper bound U is thus obtained by solving a knapsack problem, where the size of the items is the weight and their profit is their height. Not all values of H are possible. Some do not correspond with the sum of heights of any subset of items. Therefore, to ensure that a value H is useful, we solve a Subset-Sum Problem: Given a set of N positive integers and a value C, the objective of this problem is to find the subset of integers whose sum is the closest to C without exceeding C. If this problem has no solution for value H, then this value is skipped. Instead of scanning linearly all possible values of H, we apply a divide-and-conquer strategy, which avoids the computation of many non-useful subproblems. At each iteration, a threshold value H ¼ bLþUc is considered. If 2-DVPP(H) = 2-DVPP(U) then set U = H 2 and iterate with the new values found. If instead 2-DVPP(H) – 2DVPP(U) the method is run in both intervals [L, H] and [H, U]. A process is stopped when L = U. The problem to solve at each step is a two-dimensional vectorpacking problem. It can be stated as follows, using the variables of model (1)–(7):

Many heuristics have been designed for solving the vector packing problem. The most popular and effective ones are First Fit Decreasing (FFD) based heuristics (see Caprara & Toth, 2001; Garey et al., 1976; Spieksma, 1994). Recently, Lee et al. (2011) presented new heuristics based on a generalization of FFD for solving a virtual machine consolidation problem. These heuristics take into account both item sizes and how well they fit the residual capacities of the opened bin. The authors showed that they outperform FFD-based heuristics in most cases. In the 2-DVPP, there is not an obvious choice of how to sort the resources (items or bins) according to their dimensions. Hence, different ways of assigning the weights to the two dimensional vectors are possible. Therefore a scaling vector w = {w1, w2} is used to normalize the sizes across dimensions and to weight the resources according to their importance. A natural choice of w is the average demand for each dimension.

8 N X > >w ¼ 1 > ci > 1 N < i¼1 N > X > >w ¼ 1 > 2 N hi : i¼1

ð14Þ

The DotProduct heuristic defines the largest item as the item that maximizes the dot product between the vector of remaining capacities r = {r1, r2} of the current opened bin j and the vector sizes of item i. It selects the item i that maximizes the quantity w1cir1 + w2hir2 without violating the capacity constraints. The best results were obtained with a weight assignment of exp(0.01  w), where w stands for the size of the bin in the current dimension. 4. An iterative min-height based approach 4.1. Outline of the method The exploration of the search space starts by computing lower ~  and upper bounds m and m on the number of bins. The used lower bound is LB1 (see above) (Eilon & Christofides, 1971). The upper bound is generated using the DotProduct heuristic. For each valid ~  number of bins m 2 ½m; . . . ; mŠ, a MHPP instance is optimized. By associating items to jobs and bins to machines, we note that the problem corresponds to a scheduling problem denoted by PkCmax with additional capacity constraints. In the latter problem, n jobs have to be assigned to m identical parallel machines. Each

min

M X j¼1 M X j¼1 N X i¼1 N X i¼1

yj

ð8Þ

s:t:

xij ¼ 1;

i ¼ 1; . . . ; N j ¼ 1; . . . ; M j ¼ 1; . . . ; M j ¼ 1; . . . ; M

ð9Þ ð10Þ ð11Þ ð12Þ ð13Þ

ci xij 6 Cyj ; hi xij 6 Hyj ;

xij 2 f0; 1g; yj 2 f0; 1g;

i ¼ 1 . . . ; N; j ¼ 1; . . . ; M

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

161

having a processing time pi (i = 1, . . . , n) and the main objective is to minimize the maximum completion time of jobs (makespan). Since PkCmax is known to be strongly NP-hard, the same holds for MHPP. Considering a cardinality constraint k on the maximum number of items that have to be packed into one bin leads to a special case of MHPP denoted as P#j6kjCmax. Using the variables of model (1)–(7), we now give the formal definition of MHPP.

constraint (17). Recalling that we are approximating a Pareto optimal set, the proposed heuristics have to be run for each valid number of bins. 4.3.1. The least loaded heuristic The least loaded heuristic (LL) attempts to balance the load between the bins. Given a list of empty bins k = (1, . . . , m) and an ordered list of items r, LL takes each item i following r and tries to pack i into one of the current m bins by choosing the currently least loaded one (i.e. the bin of largest residual capacity). If LL fails to pack a selected item into the current m bins, a new bin is opened. The process is stopped when there are no more items to pack. The heuristic can be seen as the well known approximating algorithm List Scheduling (Graham, 1966) for the PkCmax problem. One of the most effective sorting rules is the Longest Processing Time (LPT) that orders the jobs (items) in a non-increasing order of processing time (height/weight). In order to adapt LL to our two-dimensional problem, we examined various sorting rules: decreasing ci (favoring the construction of feasible solutions), decreasing hi (favoring good quality solutions) and decreasing max{ci, hi}. After some preliminary experiments, the most effective sorting rule is decreasing hi. This can be explained by the fact that for many instances, finding a feasible solution in term of ci is not hard. In the iterative process, we choose the valid bin with the minimum height among the m current bins. 4.3.2. The min-bin heuristic The min-bin (MB) heuristic was designed to be applied in our multi-objective framework. It starts from an initial solution with m + 1 bins and tries to build a new solution with m bins based on the latter one. The heuristic empties the bin j with the minimum total height and tries to repack its items into the remaining m bins. These items are sorted in a decreasing order of hi and iteratively assigned to the first feasible bins. If the heuristic succeeds to pack all the items then bin j is discarded from the list. The process is stopped when it is unable to repack an unpacked item. 4.3.3. The multi-fit heuristic The multi-fit (MF) heuristic has been proposed by Coffman, Garey, and Johnson (1978) for the PkCmax problem. The heuristic finds through a binary search the smallest value ~ for an associate BPP c instance that uses no more than m bins of capacity ~. In our case, c MF takes as input a list of items r = (1, . . . , N) sorted in a decreasing order of hi, and a number m of bins. The heuristic starts by computing lower and upper bounds L and U on the maximum height of a bin, according to Coffman et al. (1978). It then proceeds through a binary search to find the minimum height H that uses no more than m bins and that respects the weight constraints. At each iteration, we apply an adapted version of first fit decreasing that takes into account capacity constraints (17) and (18). 5. Improving both approaches using metaheuristics In this section, we introduce several metaheuristics developed for both resolution approaches. We use exactly the same models and encodings for both problems. Only the cost functions and the initial solutions are modified. One of the main issues when designing metaheuristics for solving combinatorial optimization is to find a trade-off between intensification and diversification (see for example Talbi, 2009). Whereas local search methods are known to be efficient as intensifying methods, evolutionary algorithms (EA) are powerful to explore the decision space thanks to their variation operators. These metaheuristics attested their efficiency for several challenging packing problems (see for example Falkenauer, 1996; Khanafer

min H m X xij ¼ 1; s:t: j¼1 N X i¼1 N X i¼1

ð15Þ i ¼ 1; . . . ; N j ¼ 1; . . . ; m j ¼ 1; . . . ; m j ¼ 1; . . . ; m ð16Þ ð17Þ ð18Þ ð19Þ ð20Þ

ci xij 6 C;

hi xij À H 6 0;

xij 2 f0; 1g; H2N
4.2. Lower bounds

i ¼ 1; . . . ; N;

In this section, we present different lower bounds adapted from PkCmax, P#j6kjCmax. The following bounds were proposed in Dell’Amico and Martello (2001, 1995), Dell’amico, Iori, and Martello (2004), Dell’Amico, Iori, Martello, and Monaci (2006). The first lower bound L1 is the maximum among the solution value of the continuous relaxation of the problem, the maximum height of an item and the minimum possible height needed to pack the m + 1 largest items.

& L1 ¼ max

’ ! n 1X hi ; maxfhi g; hm þ hmþ1 i m i¼1

For our specific problem, we can slightly improve the lower bound of Dell’amico et al. (2004). A new lower bound can be derived from L1 by eliminating the n À m À 1 smallest items and considering the weight capacity constraints. The optimal solution value of the relaxed problem is clearly no less than hmþ1 þ mini2f1;...;mg:ci þcmþ1 6C hi . Thus, an improved bound is

 e1 ¼ max L1 ; hmþ1 þ L

i2f1;...;mg:ci þcmþ1 6C

min

hi



L When n > m(k À 1), bound e2 was obtained by observing that at least one bin must contain k items among the first largest m(k À 1) + 1 ones. Thus, by considering the k smallest items, we have

0 L L2 ¼ max @e1 ;

mðkÀ1Þþ1 X

1 hi A

i¼ðmÀ1ÞðkÀ1Þþ1

In the special case arising when n = mk, the bound L2 can be improved by considering the total height of the bin that contain the largest item.

e2 ¼ max L2 ; h1 þ L

n X

! hi

i¼nÀkþ2

L L The overall lower bound is then LC ¼ maxðL1 ; e1 ; L2 ; e2 Þ. 4.3. Heuristics In this section, we describe several heuristic algorithms for solving MHPP. Most of them are adapted versions of heuristics proposed for the PkCmax so as to handle the weight capacity

162

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

et al., 2012; Khanafer, Clautiaux, & Talbi, 2012). We examine the performance of these metaheuristics on solving our problem with both of our iterative approaches. We first describe an iterated tabu search (ITS) algorithm. The reader is referred to Glover and Laguna (1999) for a detailed description of tabu search algorithms. Second, a basic EA is presented in this section. The choice of a solution representation is of considerable importance for the search operators and in the evaluation process. Several simple representations may be carried out for the same optimization problem such as permutation, float, discrete or binary vector representation. In this paper, we investigate two different solution encoding schemes, namely direct and indirect encoding schemes. In the sequel, we list the algorithms’ features related to fitness function, solution representation and evaluation.
Fig. 2. An example of the direct encoding scheme.

5.1. Fitness functions For the Mo2-DBPP, different fitness criteria are worth considering. For a given solution s, let m(s) be the number of bins used, and H(s) the maximum height of a bin. For the vector-packing problem where H is the height currently fixed, our metaheuristics use the following lexicographic fitness function: tion technique. The best solution in the neighborhood replaces the current solution even if it is not improving. 5.2.3. Perturbation method When the search has not found an improving solution after a given number of iterations, a perturbation method is used. It consists in swapping N times a pair of randomly chosen items. Each time the 4 perturbation method is called, only feasible moves are allowed (i.e. swap item i from bin j with item i0 from bin j0 while satisfying the capacity constraints of each bin). 5.2.4. Tabu list and aspiration criterion To prevent the search from revisiting previously visited solutions, a tabu list is used. In our implementation, the tabu list is a vector containing the attributes of tabu neighbors. Because of the loss of information concerning the search memory, the tabu list may prohibit attractive neighbors that have not yet been generated. Hence, it is necessary to use an aspiration criterion to accept some forbidden neighbors. Our aspiration criterion consists in choosing a tabu neighbor if it is the best solution found overall. 5.3. Metaheuristics with an indirect encoding 5.2. An iterated tabu search with a direct encoding A solution is encoded as a discrete vector of size N. Each vector’s position ai (i = 1, . . . , n) represents the index j = 1, . . . , m of the bin in which i is packed. Fig. 2 illustrates our solution encoding. 5.2.1. Initial solution In the vector-packing based approach, for each fixed maximum height H, the initial solution is generated by performing the DotProduct heuristic. In the min-height based approach, for each fixed number of bins m, the initial solution is generated as follows. If there is a previous generated solution with m + 1 bins, the min-bin heuristic (see Section 4.3.2) is performed in order to generate a new solution with m bins. If not, the LL heuristic (see Section 4.3.1) is applied. If the initial solution is not feasible, the objective function described above is used to drive the search toward feasible solutions. 5.2.2. Neighborhood exploration and evaluation Neighbors for a current solution can be obtained by swapping items between all possible pairs of bins. We only consider swaps that preserve the capacity constraints. The swapping process starts by comparing the items in the first bin with the items in the second bin, and so on, sequentially down to the last bin in the initial solution and is repeated for each possible pair of bins. Each time the move is applied, the neighbor is evaluated through a lazy evaluaThe major asset of the indirect encoding is to effectively avoid some symmetries and redundancy in the search space. This representation scheme is applied for both ITS and EA algorithms. A packing solution is represented as a permutation r = (1, . . . , N) of N items. A straightforward decoder considers the permutation r as a priority list and sequentially assigns the incoming items, in the vector-packing approach, using an adapted version of the First Fit algorithm. In the min-height approach, the LL heuristic is performed to assign the items to the m current bins. Fig. 3 presents the main steps of a solution encoding/decoding process for Example 1. 5.3.1. Initial population and variation operators for the EA The initial population of 100 individuals is generated by combining random solutions with a solution constructed using the DotProduct heuristic in the 2-DVPP approach and the LL heuristic in the min-height based approach. After the decoding process, a fitness value is assigned to every individual in the population (see Section 5.1). At each step of the algorithm, individuals are selected using the tournament selection method and reproduced using the variation operators (i.e. crossover and mutation). Finally, a generational replacement is applied to the initial population. We use the Two-points crossover operator (Ishibuchi & Murata, 1998): a pair of crossing points is randomly selected, and the generated offspring preserves the items outside the selected two

F v p ðsÞ ¼ hmaxfHðsÞ À H; 0g; mðsÞi
This function first aims at finding a feasible solution. Then a solution with the smallest number of bins is sought. In the min-height approach, many solutions may be equivalent in term of H(s). Therefore, we introduce another term h2(s), the sum of the square of the height of each bin. This latter criterion is used to refine H(s) and to favor solutions with few highly loaded bins. If the number of currently fixed bins is m, the lexicographic objective function is the following:

F mh ðsÞ ¼ hmaxfmðsÞ À m; 0g; HðsÞ; h ðsÞi
This function will always favor a feasible solution, then optimize the actual objective of height minimization. The third term is used to break the ties between solutions of same height.

2

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

163

points from the first parent chromosome. The remaining items are inserted from the second parents respecting the order of their appearance. We also adapt two mutation operators: shift mutation operator and swap mutation operator. In the shift mutation operator, a pair of randomly chosen components are shifted from the permutation part of the chromosome, whereas in the swap mutation operator, a pair of randomly chosen components are swapped from the permutation part of the chromosome. From preliminary experiments, we noted that a good performance is achieved through randomly using the above described mutation operators, which are invoked with probabilities 0.5 and 0.5 respectively. 5.3.2. Initial solution and neighborhood exploration of the iterated tabu search The algorithm starts by a solution constructed using the DotProduct heuristic in the vector-packing based approach and the LL heuristic in the min-height based approach. If LL fails to generate a solution with m bins, a random permutation is generated. The neighborhood exploration is based on pairwise exchanging operations (i.e. Two-exchange neighborhood). It consists in selecting randomly two items and swapping their position in the packing solution. The perturbation method consists in swapping N times a 4 pair of randomly chosen items. The tabu list and acceptance criteria are the same as those designed for the direct encoding case. 5.4. An hybrid metaheuristic for the min-height problem We here describe a new hybrid metaheuristic hybMeta for solving the MHPP. It combines heuristics and exact methods for both MHPP and 2-DVPP problems. Let m be the current fixed number of bins. We first compute lower and upper bounds L and U for the possible bin height using LC and MF heuristic respectively. A binary search is then performed to find the smaller value of H between U and L that will lead to a solution with at most m bins. This scheme leads to the resolution of several 2-DVPP problems. We first use the DotProduct heuristic to find an initial solution. Then a perturbation method is iteratively applied until an improved packing solution is found or the maximum computing time is reached. The perturbation works as follows. We first choose a subset of bins to discard, and try to repack their contents into the remaining bins and new created bins. The selection of the bin subset consists in choosing a given number q of bins with total height equal to H and a random subset of ‘‘Least loaded’’ bins. We determine the least loaded bins with the rule described in Eq. (14). For repacking the items, we first use DotProduct. If it fails to reduce the number of bins, we use a branch-and-price based on Caprara and Toth (2001). 6. Experiments We empirically investigate the performances of the vectorpacking and min-height approaches in order to determine which approach is more relevant to solve Mo2-DBPP. 6.1. Benchmarks We used the benchmarks of Caprara and Toth (2001) for 2DVPP. Table 1 summarizes the main features of each class in the data set (u.d. stands for uniform distribution). In the first six classes, the value N, and each value of ci and hi are random independent values generated from a uniform distribution in [a, b]. Classes 1–3 were proposed in Spieksma, 1994. In these classes, each bin contains on average about 4, 2 and 2 items respectively. In order to consider instances where more items per bin are

Fig. 3. The encoding/decoding process using the indirect encoding for Example 1.

Table 1 Benchmark description. Class 1 2 3 4 5 6 7 8 9 10 C 1000 1000 1000 1000 1000 150 150 150 $P % c i¼1;...;N i L

ci u.d.[100, 400] u.d.[100, 1000] u.d.[200, 800] u.d.[50, 200] u.d.[25, 100] u.d.[20, 100] u.d.[20, 100] u.d.[20, 100] u.d.[100, 400] See text

hi u.d.[100, 400] u.d.[100, 1000] u.d.[200, 800] u.d.[50, 200] u.d.[25, 100] u.d.[20, 100] u.d.[cj À 10, cj + 10] u.d.[110 À cj, 130 À cj] u.d.[100, 400] See text

100

packed, Caprara and Toth suggested two new classes 4 and 5 where each bin contains on average about 8 and 16 items respectively. By analogy to the most difficult instances of BPP mentioned in the literature (see Falkenauer, 1996), the authors proposed class 6, where bin capacities are equal to 150, and weights are uniformly distributed in [20, 100]. In Class 7, the height and the weight are correlated for each item, whereas these two value are anti-correlated in Class 8. Instances in Classes 9 and 10 are artificially designed to be hard to solve. In Class 9, item sizes are generated as in Class &$P % $P %' c h i¼1;...;N i i¼1;...;N i 1. The value of L is computed as max ; and 1000 1000 $P % ci i¼1;...;N . Instances in the bin weight capacities are defined as C ¼ L Class 10 are generated as the triplets (Falkenauer, 1996) for BPP. For our experimentation, about 40 instances are used by considering the problem sizes related to the values N 2 {25, 50, 100, 200} (for Class 10, N 2 {24, 51, 99, 201}) and solving one instance for each value of N.

6.2. Computational results The overall presented algorithms are implemented in C++. The CPLEX solver 12.0 is used to solve the (integer) linear models. Computational runs were performed under Linux operating system on an Intel Core 2 Duo 6600 (2.40 GHz) machine, with 2 GB RAM. All the metaheuristics presented in this paper have been implemented using the ParadisEO framework.1 The stopping criterion of all meta-heuristics is the CPU time. The time limit t is fixed depending on the problem size: for each
1

ParadisEO is available at: http://paradiseo.gforge.inria.fr.

164 Table 2 Comparison of lower bounding procedures. Class n Lcont %gap 1 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 24 51 99 201 4.8 4.06 4.63 5.56 4.76 23.13 30.03 13.68 19.54 21.6 11.1 17.59 13.92 12.98 13.9 3.87 2.94 3.51 3.83 3.54 3.62 2.62 3.34 3.36 3.24 6.82 7.52 6.6 6.06 6.75 5.59 8.56 4.25 3.36 5.44 15.36 18.55 17.94 22.54 18.6 5.21 4.14 6.2 7.65 5.8 9.93 7.94 10.89 12.21 10.24 9.39

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

Lint ropt 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.08 0.04 0.02 0 0.04 0 t 0.02 0.01 0.05 0.21 0.07 0.02 0.02 0.07 0.38 0.12 0.02 0.02 0.07 0.42 0.13 0.01 0.01 0.05 0.19 0.07 0.01 0.01 0.04 0.17 0.06 0.02 0.02 0.05 0.3 0.1 0.02 0.02 0.05 0.33 0.11 0.02 0.08 0.19 0.98 0.32 0.02 0.06 0.17 0.63 0.22 0.02 0.08 0.18 0.77 0.26 0.15 %gap 0.93 2.92 3.6 4.96 3.1 0 0 8.92 7.4 4.08 3.58 6.75 9.62 11.11 7.77 0.99 1.93 2.68 3.38 2.25 0.88 1.7 2.46 2.56 1.9 1.63 3.77 4.25 4.91 3.64 1.46 4.21 2.59 2.71 2.74 0 5.2 2.41 2.75 2.59 0.98 2.96 5.31 5.67 3.73 1.16 6.89 6.51 8.83 5.85 3.77 ropt 0.27 0.05 0.05 0 0.09 1 1 0 0 0.5 0.2 0.2 0.06 0 0.12 0.21 0.04 0.04 0 0.07 0.5 0.07 0.02 0 0.15 0.29 0.27 0.08 0 0.16 0.5 0.33 0.1 0 0.23 1 0.3 2.26 0.34 0.98 0.36 0.06 0.02 0.06 0.13 0.73 0.04 0.3 0.02 0.27 0.27 t 59.1 110.34 170.63 357.12 174.3 0.27 3.42 176.59 359.8 135.02 57.59 112.94 178.5 379.3 118.05 56.28 119.12 177.42 378.09 182.73 35.26 118.53 179.4 356.3 172.37 56.71 119.04 169.59 378.16 180.88 59.61 118.66 173.34 356.98 177.15 51.63 116.02 169.38 349.21 171.56 45.61 118.38 149.51 339.26 163.19 24.69 115.74 139.92 359.01 159.84 163.51

LC %gap 2.71 3.2 2.73 3.91 3.14 8.69 0 5.24 12.21 6.54 6.04 6.75 7.54 7.84 7.04 2.23 2.37 2.15 2.64 2.35 2.26 2.26 2.21 1.37 2.03 3.78 4.39 4.22 4.23 4.16 2.98 2.07 2.67 3.2 2.73 11.66 5.73 13.89 17.23 12.13 2.92 3.22 4.3 6 4.11 2.23 3.51 2.38 2.08 2.55 4.68 ropt 0.2 0.5 0.05 0.01 0.19 0.33 1 0 0 0.33 0.2 0.2 0.05 0 0.11 0.13 0.04 0.04 0 0.05 0.13 0.04 0.02 0.08 0.07 0.14 0.27 0.07 0 0.12 0.2 0.27 0.09 0.03 0.15 0.11 0.3 0.32 0.26 0.25 0.18 0.06 0.02 0 0.07 0.38 0.22 0.29 0.33 0.31 0.17 t 0.11 0.14 0.38 0.86 0.37 0.07 0.08 0.09 0.1 0.09 0.04 0.06 0.24 0.28 0.16 0.14 0.18 0.45 1 0.44 0.11 0.37 0.67 1.42 0.64 0.08 0.16 0.24 0.49 0.24 0.05 0.1 0.14 0.35 0.16 0.08 0.1 0.29 0.53 0.25 0.1 0.16 0.28 0.8 0.34 0.09 0.19 0.5 0.75 0.38 0.31

LCG %gap 0.06 0.3 0.91 1.48 0.69 0 0 0.03 0 0.01 0 0 0.02 0.13 0.04 0.07 0.23 0.57 0.93 0.45 0.22 0.3 0.36 0.69 0.39 0.12 0.54 0.12 0.6 0.35 0 0 0 0 0 0 0 0.86 0.1 0.24 0.01 0.45 0.95 2.16 0.89 0 0.09 0.49 0.49 0.27 0.33 ropt 0.73 0.68 0.47 0.53 0.6 1 1 0.78 1 0.95 1 1 0.84 0.75 0.9 0.79 0.44 0.35 0.38 0.49 0.67 0.5 0.45 0.3 0.48 0.83 0.45 0.83 0.55 0.67 1 1 1 1 1 1 1 0.6 0.96 0.89 0.82 0.61 0.63 0.41 0.62 1 0.96 0.84 0.84 0.91 0.75 t 0.11 0.29 0.68 2 0.77 0.04 0 0.43 2.1 0.64 0.08 0.14 0.41 0.91 0.39 0.12 0.35 0.56 4.95 1.5 0.11 0.32 0.58 13.41 3.61 0.09 0.25 0.67 3.34 1.09 0.08 0.19 0.7 3.15 1.03 0.06 0.12 0.55 2.42 0.79 0.1 0.32 0.67 3 1.02 0.09 0.36 0.54 1.41 0. 6 1.14

Average 2

Average 3

Average 4

Average 5

Average 6

Average 7

Average 8

Average 9

Average 10

Average Overall average

value N 2 {25, 50, 100, 200}, t is equal to {60, 120, 180, 360} seconds respectively. The tables below provide the following informations: let vL be the value produced by a lower bounding procedure L, and vH the solution value generated by a heuristic algorithm A. Let v à and L v à denote the best lower bound and heuristic solution value obH tained, respectively. For each test instance and for each algorithm, the tables report the following information.  %gap = the average percentage gap for all points in the Pareto À Á approximated set. The %gap is determined by 100 v H À v à =v à L L À à Á à for the upper bounds and 100 v H À v L =v L for the lower bounds  ropt = the ratio between the number of proved optimal solutions and the number the generated approximated solutions.

 t = the average computing time needed to obtain the best solution. We denote by (–) the instances where no solutions were found by the algorithm.

6.3. Lower bounds In Table 2, we present the behavior of four lower bounding procedures. Columns Lcont and Lint respectively deal with the results of the continuous relaxation and the integer linear model (15)–(20) using the same CPU time as the metaheuristics. In columns LC, we report the results for the bounds presented in Section 4.2.

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170 Table 3 Overall performance of metaheuristics based on the vector-packing approach. Class n EA_BinPack %gap avg 1 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 24 51 99 201 5.89 5.1 3.23 2.3 4.13 15.19 – 4.57 11.73 10.5 3.6 4.88 1.54 2.49 3.13 6.69 4.64 3.23 2.26 4.21 7.44 3.99 3.1 2.17 4.18 14.03 3.91 1.98 2.69 5.65 5.02 1.66 1.45 2.5 2.66 6.86 6.77 2.68 2.27 4.65 4.89 4.15 3.27 3.03 3.84 3.4 2.07 2.32 2.48 2.57 4.47 min 5.15 5.1 2.67 1.76 3.67 15.19 – 0.76 1.2 5.72 3.6 4.88 0.49 1.92 2.72 6.2 4.37 2.9 2.04 3.88 6.84 3.82 2.96 2.02 3.91 13.72 2.42 1.02 1.82 4.75 4.51 1.31 0.91 2.3 2.26 6.86 6.77 2.6 2.01 4.56 3.83 3.59 2.48 2.47 3.09 3.4 1.58 1.78 2.09 2.21 3.66 max 6.07 5.89 3.88 2.87 4.68 15.19 – 16.21 26.38 19.26 3.6 4.88 2.28 3.11 3.47 6.81 4.77 3.49 2.42 4.37 8.34 4.23 3.23 2.31 4.53 14.66 5.11 3.23 3.86 6.72 5.78 2.47 1.86 2.8 3.23 6.86 6.77 2.91 2.64 4.8 5.52 4.34 3.91 3.58 4.34 3.4 2.33 2.66 2.8 2.8 5.6 0 0.05 0.12 0.19 0.09 0 – 0.33 0.3 0.21 0.2 0 0.22 0.13 0.14 0.14 0 0.11 0.24 0.12 0.07 0.07 0.25 0.04 0.11 0 0.11 0.45 0.51 0.27 0.17 0.33 0.52 0.19 0.3 0.27 0.25 0.63 0.56 0.43 0 0.06 0.07 0.19 0.08 0.17 0.58 0.56 0.5 0.45 0.22 ropt ITS_BinPack %gap avg 5.85 3.67 2.26 2.21 3.5 15.19 – 5.04 21.3 13.84 3.6 4.88 1.4 3.74 3.41 6.81 4.12 2.36 1.58 3.72 6.22 3.42 2.21 1.61 3.37 3.35 3.54 6.78 7.92 5.4 5.05 1.51 1.07 0.77 2.1 6.86 6.49 3.99 4.17 5.38 4.92 3.44 2.42 3.19 3.49 3.51 1.52 2.19 3 2.56 4.53 min 4.95 2.8 1.94 1.94 2.91 15.19 – 2.11 11.58 9.63 3.6 4.88 0.63 2.53 2.91 6.81 3.68 2.09 1.42 3.5 6.07 3.42 1.93 1.49 3.23 2.87 3.18 4.81 6.18 4.26 5.05 1.51 1.07 0.77 2.1 6.86 5.39 3.03 2.69 4.49 3.38 2.16 2.09 2.62 2.56 3.2 1.34 2.03 2.62 2.3 3.7 max 6.07 4.3 2.47 2.48 3.83 15.19 – 16.21 38.67 23.36 3.6 4.88 2.41 5.5 4.1 6.81 4.23 2.59 1.71 3.84 6.84 3.42 2.45 1.73 3.61 3.91 3.99 7.94 9.27 6.28 5.05 1.51 1.07 0.77 2.1 6.86 6.77 6.06 5.69 6.35 5.52 3.88 2.87 3.62 3.97 3.82 1.77 2.24 3.22 2.76 5.73 0 0 0.02 0.15 0.04 0 – 0 0 0 0.2 0 0.47 0 0.17 0.07 0 0.16 0.28 0.13 0.06 0.14 0.02 0.25 0.12 0 0.11 0.43 0.24 0.2 0.14 0.33 0.52 0.44 0.36 0.27 0.25 0.47 0.48 0.37 0 0 0.02 0.15 0.04 0.15 0.58 0.67 0.5 0.48 0.19 ropt ITS %gap avg 5.76 8.13 5.37 3.91 5.79 9.83 – 22.28 6.56 12.89 4.19 5.07 0.73 1.77 2.94 6.93 7.42 5.47 4.48 6.08 10.97 6.95 8.81 4.8 7.88 7.78 5.69 8.51 10.21 8.05 5.78 1.51 1.62 1.11 2.51 9.98 11.17 11.2 13.91 11.57 5.09 7.79 5.65 3.31 5.46 4.37 4.11 2.63 1.48 3.15 6.57 min 5.76 8.13 5.37 3.91 5.79 9.83 – 22.28 6.56 12.89 4.19 5.07 0.48 1.77 2.88 6.93 7.42 5.47 4.48 6.08 10.97 6.95 8.81 4.8 7.88 7.78 5.66 8.51 10.21 8.04 5.78 1.51 1.62 1.11 2.51 9.98 11.17 11.2 13.91 11.57 5.09 7.79 5.65 3.31 5.46 4.37 4.11 2.63 1.48 3.15 6.57 max 5.76 8.13 5.37 3.91 5.79 9.83 – 22.28 6.56 12.89 4.19 5.07 0.88 1.77 2.98 6.93 7.42 5.47 4.48 6.08 10.97 6.95 8.81 4.8 7.88 7.78 5.7 8.51 10.21 8.05 5.78 1.51 1.62 1.11 2.51 9.98 11.17 11.2 13.91 11.57 5.09 7.79 5.65 3.31 5.46 4.37 4.11 2.63 1.48 3.15 6.58 0 0 0 0 0 0 – 0 0 0 ropt

165

Average 2

Average 3

Average 4

0 0 0.18 0 0.05 0 0 0 0 0 0 0 0.02 0.01 0.01 0.14 0.11 0.04 0.03 0.08 0 0.33 0.23 0.3 0.22 0 0 0.05 0.03 0.02 0 0 0 0 0 0.17 0.48 0.56 0.4 0.4 0.07

Average 5

Average 6

Average 7

Average 8

Average 9

Average 10

Average Overall average

The LCG columns contain the results related to the vector packing based lower bound (Caprara & Toth, 2001). The model (15)–(20) leads to weak results. It can be explained by the bad quality of its linear relaxation (9.39% gap in average, up to 30.03% for Class 2 with n = 50) and its large number of variables. The integer model is able to solve to optimality 27% of the instances, but fails to solve a large number of instances of size 25. The maximal remaining average gap for Lint reaches 11.11% for Class 3 with n = 200. The fast lower bound LC is slightly worse than Lint in term of overall average gap but is able to find better average gaps for subsets of all classes, except for class 8, where the gap of LC is the worst (up to 17.23% with n = 200). This bound is always

better than the linear relaxation Lcont for comparable computing times. The time required for LC was at most one second in all cases, which is far less than the time given to the integer model. The column generation LCG provides the best lower bound (0.33% gap in average). It solved to optimality all instances in Class 7 and produced near optimal results for instances in Class 2 (0.01% of average gap and 95% of proved optimal solutions). The average gap for LCG is never larger than 2.16% (Class 9, n = 200). The computing time of this bound remains reasonable (1, 14 s in average) with larger computing times for Classes 4 and 5 (up to 13, 41 s), where many items can be packed into a bin (and thus the pricing subproblems are more time-consuming).

166

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

CL_01_50_1
1150 LCG EA_BINPACK 1100 ITS_BINPACK ITS 1050 hybMeta 1000 950 900 850 800 750 700 650 600 550 500 450 400 350 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

940 920 900

CL_03_50_1
LCG EA_BINPACK ITS_BINPACK ITS hybMeta

Maximal height

Maximal height

880 860 840 820 800 780 30 31 32 33 34

Number of bins

Number of bins

CL_05_100_1
900 850 800 750 700 650 600 550 500 450 400 350 300 250 200 150 100 50
LCG EA_BINPACK ITS_BINPACK ITS hybMeta

160 150

CL_07_100_1
LCG EA_BINPACK ITS_BINPACK ITS hybMeta

Maximal height

Maximal height

140 130 120 110 100 40

5

10 15 20 25 30 35 40 45 50 55 60 65 70

45

50

55

60

65

Number of bins

Number of bins

CL_08_200_1
320 300 280 260 240 220 200 180 160 140 120 100 80
LCG EA_BINPACK ITS_BINPACK ITS hybMeta

80

85

90

95

100 105 110 115 120 125 130

1250 1200 1150 1100 1050 1000 950 900 850 800 750 700 650 600 550 500 450 400 350

CL_09_200_1
LCG EA_BINPACK ITS_BINPACK ITS hybMeta

Maximal height

Maximal height

50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140

Number of bins

Number of bins

Fig. 4. Pareto approximation sets comparison for a randomly chosen instances with n 2 {50, 100, 200}.

It transpires from our experiments that the best combination of bounds is to use LC, which is always fast, before using LCG. 6.4. Upper bounds In this section, we compare the average overall performance of the proposed algorithms for both 2VPP and MHPP based approaches. For all the presented metaheuristics, we performed five independent runs. For each instance and each algorithm,

we report the average, minimum and maximum percentage gap (%gap) in columns avg, min and max. Concerning the parameter settings, for the ITS algorithms, each time the construction phase is called, a tabu search algorithm is performed and stopped when the best solution cannot be improved n within a given number of iterations equal to 2. For the GA, the initial population size is fixed to 100 individuals and the crossover and mutation probabilities are set to 0.8 and 0.5 respectively.

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170 Table 4 Overall performance of metaheuristics based on the min-height approach. Class n EA_BinPack %gap avg 1 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 24 51 99 201 0.74 2.68 3.06 5.19 2.92 0 0 6.13 24.26 7.6 0 0.08 4.49 4.68 2.31 0.41 0.74 1.18 1.78 1.03 0.32 0.67 0.82 1.58 0.85 0.25 2.06 2.06 6.24 2.65 0.03 0.44 0.6 3.14 1.05 0.02 0.36 1.04 3.97 1.35 0.48 0.74 2.75 7.59 2.89 0.09 1.06 2.17 4.97 2.07 2.47 min 0.4 2.26 2.2 3.81 2.17 0 0 2.79 16.87 4.92 0 0 2.49 3.06 1.39 0.21 0.44 0.82 1.35 0.71 0.2 0.43 0.37 1.17 0.54 0.1 1.09 1.07 4.64 1.73 0 0.43 0.29 2.58 0.83 0 0.19 0.63 2.95 0.94 0.25 0.38 2.27 6.34 2.31 0 0.68 1.52 3.92 1.53 1.71 max 1.27 3.18 3.87 6.69 3.75 0 0 10.59 32.84 10.86 0 0.36 6.95 6.95 3.57 0.71 1.11 1.65 2.24 1.43 0.57 0.99 1.47 2.05 1.27 0.81 3.4 3.33 7.83 3.84 0.13 0.48 0.96 3.84 1.35 0.06 0.66 1.62 5 1.84 0.92 1.14 3.34 8.99 3.6 0.53 1.57 3 6.24 2.84 3.43 0.58 0.42 0.16 0.01 0.29 1 1 0 0 0.5 1 1 0.11 0.05 0.54 0.53 0.4 0.29 0.04 0.32 0.69 0.39 0.56 0.09 0.43 0.86 0.45 0.56 0.06 0.48 1 0.8 0.67 0.03 0.63 1 0.79 0.68 0.26 0.68 0.64 0.56 0.33 0 0.38 0.83 0.73 0.35 0.05 0.49 0.47 ropt ITS_BinPack %gap avg 6.98 2.59 1.72 18.17 7.37 9.98 19.23 12.29 33.19 18.67 8.02 2.16 5.17 11.18 6.63 6.34 1.99 1.64 14.45 6.11 5.71 1.86 3.04 12.39 5.75 9.2 2.92 4.59 24.7 10.35 6.41 1.96 1.6 13.21 5.8 6.64 4.56 14.68 16.16 10.51 5.7 5.72 17.27 17.95 11.57 8.97 5.58 12.47 13.6 10.17 9.3 min 2.12 0.67 1.72 18.17 5.67 0.94 7.39 12.29 33.19 13.45 2.36 0.54 5.17 11.18 4.81 1.55 0.55 1.64 14.45 4.55 1.26 0.85 2.08 12.39 4.15 2.2 1.31 4.59 24.7 8.2 1.17 1.13 1.6 13.21 4.28 2.07 1.51 13.52 16.16 8.32 1.18 2.85 15.19 17.95 9.2 1.89 3.04 10.51 13.6 7.28 7 max 15.66 6.17 1.72 18.17 10.43 23.1 35.02 12.29 33.19 25.9 15.03 4.69 5.17 11.18 9.02 13.46 4.18 1.64 14.45 8.43 12.48 3.86 4.6 12.39 8.33 17.2 5.12 4.59 24.7 12.9 14.51 4.34 1.6 13.21 8.42 13.67 9.66 15.14 16.16 13.66 11.52 10.89 19.46 17.95 14.87 17.36 10.34 13.87 13.6 13.81 12.58 0 0.05 0.02 0 0.02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.13 0.04 0 0 0.04 0.14 0.09 0 0 0.06 0.33 0 0 0 0.08 0.22 0 0 0 0.06 0.18 0 0 0 0.05 0.17 0.04 0 0 0.05 0.04 ropt ITS %gap avg 1.12 5.79 14.35 7.1 7.09 0 0 – – 0 1.49 0 3.62 8.6 3.43 0.98 5.26 10.78 6.44 5.87 1.13 4.92 11.4 5.91 5.84 0.97 4.18 5.13 2.87 3.29 0.17 1.16 2.14 5.41 2.22 0 0.35 4.23 3.8 2.1 1.18 5.59 14.01 16.22 9.25 0 3.01 8.65 10.48 5.54 4.7 min 0.96 4.81 13.73 7.07 6.64 0 0 – – 0 1.49 0 3.07 5.92 2.62 0.84 4.43 6.94 6.41 4.66 1.03 4.13 10.93 5.91 5.5 0.97 3.18 4.96 2.79 2.98 0.17 0.69 1.86 5.11 1.96 0 0 4.23 3.8 2.01 1.01 4.8 13.32 16.22 8.84 0 2.17 8.14 10.37 5.17 4.25 max 1.35 6.6 14.62 7.12 7.42 0 0 – – 0 1.49 0 3.99 10.88 4.09 1.11 6.08 12.87 6.47 6.63 1.27 5.63 11.68 5.92 6.13 0.97 5.08 5.28 2.91 3.56 0.17 1.72 2.31 5.59 2.45 0 0.61 4.23 3.8 2.16 1.34 6.38 14.3 16.22 9.56 0 3.82 9.04 10.57 5.86 5.04 0.09 0 0.03 0.07 0.05 1 1 – – 1 0.5 1 0 0 0.38 0.33 0 0.16 0.07 0.14 0.38 0.07 0.11 0.22 0.2 0.33 0.18 0.11 0.13 0.19 0.83 0.53 0.6 0.29 0.56 1 1 0.63 0.63 0.82 0.18 0 0.03 0 0.05 1 0.26 0.04 0.04 0.34 0.34 ropt hybMeta %gap avg 0.85 2.71 2.74 3 2.33 0.14 0.28 9.31 9.53 4.82 1.25 0.59 2.39 2.07 1.58 0.48 1.51 4.74 3.6 2.58 0.71 1.1 5.71 1.34 2.22 2.61 7.57 2.56 2.77 3.88 1.6 0.45 0.43 1.78 1.07 1.77 3.43 8.76 9.79 5.94 0.97 2.64 2.82 2.27 2.18 0.37 1.65 2.63 2.15 1.7 2.83 min 0.77 2.68 2.69 2.34 2.12 0 0 8.76 7.31 4.02 1.08 0.32 1.73 1.3 1.11 0.4 1.51 4.71 3.6 2.56 0.69 1.1 5.71 1.34 2.21 2.19 6.38 2.55 2.77 3.47 1.3 0.44 0.43 1.78 0.99 0.92 2.74 6.88 9.13 4.92 0.89 2.56 2.73 2.25 2.11 0.11 1.54 2.52 2.15 1.58 2.51 max 0.96 2.75 2.79 2.7 2.3 0.31 0.81 10.23 13.35 6.18 1.54 0.75 3.23 3.07 2.15 0.65 1.51 4.76 3.6 2.63 0.8 1.1 5.71 1.34 2.24 3.28 8.58 2.59 2.77 4.31 1.91 0.48 0.43 1.78 1.15 3.22 4.54 9.66 10.55 6.99 1.07 2.7 2.9 2.29 2.24 0.55 1.8 2.98 2.15 1.87 3.2 ropt

167

Average 2

0.27 0.21 0.4 0.35 0.31 1 1 0 0 0.5 0.6 0.2 0.26 0.05 0.28 0.58 0.16 0.02 0.01 0.19 0.42 0.25 0.05 0.15 0.22 0.63 0.2 0.05 0.06 0.24 0.71 0.8 0.64 0.42 0.64 0.78 0.17 0.14 0.1 0.3 0.45 0.22 0.4 0.34 0.35 0.92 0.72 0.48 0.43 0.64 0.37

Average 3

Average 4

Average 5

Average 6

Average 7

Average 8

Average 9

Average 10

Average Overall average

6.4.1. Results for the vector-packing based approach In Table 3, we report the results obtained by a population based and a single solution based metaheuristics using an indirect encoding (EA_BinPack and ITS_BinPack) and an iterated tabu search using a direct encoding ITS. The two methods using the indirect encoding are better than the ITS with direct encoding (respectively 4.47% and 4.53% gap against 6.57% gap for ITS). This difference is reduced when one considers the worst run, but becomes larger when one considers the best run. This hints that the indirect encoding is more adapted in average for this vector-packing based approach. However, note that for Class 2 with n = 200, ITS is clearly better than the two other methods. Furthermore, we observed that the ITS

is also better for small size instances of Class 1 and 3. The weakness of our direct encoding ITS is that it tends to converge toward the same local optimum at each run. Between the two indirect encoding based methods, the evolutionary algorithm is slightly better than the iterated tabu search for both average gap and number of optimal solutions. However this difference is small. The ITS_BinPack algorithm can outperform the EA_BinPack for some instances and vice versa. 6.4.2. Results for the min-height based approach The results obtained by the MHPP based approaches are comparable with those obtained by the 2DVPP approaches, with some notable differences.

168

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170

Table 5 Comparison of min-height and vector-packing based heuristics. Class n MB %gap 1 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 25 50 100 200 24 51 99 201 28.99 36.76 40.06 40.31 36.53 15.43 69.03 – – 21.12 28.51 24.54 26.02 32.32 28.46 24.72 26.13 31.64 34.35 29.21 22.96 26.53 29.82 33.03 28.09 36.23 40.45 50.73 53.08 45.12 19.1 13.19 7.32 6.54 11.54 27.86 33.56 40.23 43.16 36.2 29.44 41.36 39.58 40.24 37.66 9.18 27.75 27.97 31.74 24.16 30.44 opt 0 0 0.03 0 0.01 0.33 0 – – 0.08 0 0 0 0 0 0.07 0 0.02 0 0.02 0.13 0 0.02 0 0.04 0.14 0.11 0.05 0 0.08 0.17 0.47 0.55 0.29 0.37 0.13 0.1 0 0.03 0.07 0.09 0 0.02 0 0.03 0.09 0.04 0.02 0.01 0.04 0.08 t 0.23 0.44 1.2 3.2 1.27 0.09 0.16 0.1 0.3 0.16 0.11 0.26 0.53 1.32 0.3 0.25 0.69 1.66 3.93 0.47 0.26 0.68 1.75 4.48 0.47 0.13 0.29 0.69 1.76 0.37 0.12 0.37 0.54 1.13 0.34 0.14 0.39 0.78 2.13 0.44 0.23 0.47 1.23 3.03 0.35 0.04 0.11 0.23 0.62 0.25 0.46 LL %gap 5.54 6.5 5.83 6.17 6.01 0.47 – – – 0.12 8.13 8.63 7.8 15.3 9.97 4.87 5.87 5.32 5.56 5.41 4.41 5.19 4.85 5.77 5.06 3.1 5.88 2.46 5.17 4.15 1.64 1.29 4.06 6.22 3.3 0 0 0 0.55 0.14 5.02 6.47 5.83 6.18 5.88 1.16 2.79 3.75 3.85 2.89 4.45 opt 0.08 0 0.22 0.07 0.09 0.5 – – – 0.13 0 0 0 0 0 0.07 0 0 0.07 0.04 0.06 0 0.02 0 0.02 0.17 0.22 0.18 0 0.14 0.33 0.79 0.63 0.29 0.51 1 1 1 0.71 0.93 0.09 0 0.23 0.07 0.1 0.82 0.83 0.54 0.4 0.65 0.22 t 0.03 0.036 0.12 0.04 0.06 0.01 0.02 0.02 0.04 0.02 0.01 0.02 0.07 0.17 0.07 0.02 0.048 0.18 0.36 0.15 0.03 0.06 0.12 0.47 0.17 0.01 0.03 0.09 0.2 0.08 0.02 0.04 0.06 0.09 0.05 0.008 0.03 0.1 0.23 0.09 0.03 0.04 0.14 0.64 0.21 0.03 0.07 0.13 0.24 0.12 0.1 DotProduct %gap 3.01 4.3 4.12 3.45 3.72 0 – 0.72 8.78 2.38 0.98 0.55 2.37 2.65 1.64 2.8 4.14 4.11 3.77 3.71 3.52 3.84 4.11 4.61 4.02 2.01 3.26 6.65 2.89 3.7 0.26 0.54 0.64 1.02 0.62 4.08 9.28 4.21 27.71 11.32 2.43 4.78 4.08 3.68 4.18 1.73 1.98 2.03 2.62 2.09 3.92 opt 0.08 0 0.02 0 0.03 1 – 0 0 0.25 0.8 0.2 0.17 0.03 0.3 0.07 0 0.02 0 0.02 0.06 0 0.02 0 0.02 0.29 0.11 0.04 0 0.11 0.67 0.73 0.36 0.3 0.52 0.18 0.09 0.05 0.03 0.09 0.09 0 0.02 0 0.03 0.5 0.61 0.67 0.39 0.54 0.15 t 0.04 0.16 0.99 4.23 1.36 0.02 0.02 0.34 2.39 0.69 0.02 0.07 0.6 2.58 0.82 0.05 0.16 0.92 4.82 1.49 0.04 0.16 0.83 4.54 1.39 0.01 0.04 0.18 0.88 0.28 0.01 0.04 0.14 0.54 0.18 0.02 0.1 0.5 2.29 0.73 0.04 0.15 0.92 5.2 1.58 0.03 0.1 0.32 1.77 0.56 0.95

Average 2

Average 3

Average 4

Average 5

Average 6

Average 7

Average 8

Average 9

Average 10

Average Overall average

Once again, the best method in average is EA_BinPack. However, it transpires that the ITS_BinPack is the worst in average, with poor performances for all classes. The difference between EA_BinPack and ITS is smaller in this case. This means that applying the direct encoding scheme can be a good strategy in some cases, although EA_BinPack remains better in average for all classes, with a greater difference for large size instances. Class 2 remains difficult, even with the min-height approach. The maximal average gap achieved for both EA_BinPack and ITS_BinPack (32.84% and 33.19% respectively) are obtained for Class 2 with n = 200. In this case, hybMeta performs better (13.35% avg. gap).

The minimum average gap of hybMeta was low for almost all instances especially for small value of n. This is because of the combination of heuristic and exact methods in the hybMeta algorithm. When the value of n is small, the exact method can solve an instance constructed with a large subset of the items. This method is stable: the worst gap is never far from the best.

6.5. Pareto approximation sets comparison We plot in Fig. 4 the Pareto approximation sets generated from the different metaheuristics (EA_BinPack, ITS_BinPack, ITS and hybMeta) for a randomly chosen instances with n 2 {50, 100, 200}. We

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170 Table 6 Studying the impact of the variation of the resources sizes on the computational time needed for min-height and vector-packing based heuristics. Class n min-bin 10 1 50 100 200 50 100 200 50 100 200 50 100 200 0.04 0.12 0.196 0.016 0.044 0.152 0.06 0.116 0.264 0.02 0.028 0.068 100 0.056 0.1 0.196 0.032 0.032 0.108 0.064 0.116 0.24 0.012 0.06 0.068 1000 0.056 0.12 0.164 0.048 0.064 0.124 0.072 0.176 0.22 0.036 0.064 0.092 LL 10 0.048 0.1 0.22 0.012 0.072 0.084 0.06 0.164 0.28 0.024 0.04 0.072 100 0.032 0.108 0.188 0.028 0.048 0.104 0.072 0.152 0.28 0.048 0.06 0.076 1000 0.036 0.108 0.268 0.024 0.044 0.088 0.072 0.12 0.26 0.048 0.056 0.068 DotProduct 10 0.79 5.34 30.778 0.928 5.80 44.235 0.82 5.484 24.802 0.268 0.86 4.22 100 1.92 13.40 71.38 1.484 10.885 132.868 1.916 12.329 52.107 0.44 1.52 8.737 1000

169

10.04 43.01 211.189 9.549 30.218 170.855 8.157 30.478 146.433 1.172 3.104 11.941

3

5

7

compare these approximated Pareto fronts against the column generation lower bound LCG, which is our best lower bound. The selected test instances are not equally difficult to solve, which affects the number of the generated potentially efficient solutions of each algorithm. This number varies from 5 to 19 (for instances of 50 items), 42 to 62 (for instances of 100 items) and 75 to 81 (for instances of 200 items). The examples in Fig. 4 illustrate the numerical results. The algorithms with indirect encoding (EA_BinPack and ITS_BinPack) were generally equivalent by producing near optimal solutions and outperform the ITS in most cases. However, applying the algorithm with direct encoding (ITS) can be helpful in some cases especially when the number of bins is small. The hybrid metaheuristic hybMeta also performs well for hard instances where the exact method generates a solution with a large subset of the items.

7. Conclusion Throughout this paper, we studied a bi-objective version of the 2-DVPP. To tackle the problem, we presented two resolution approaches that iteratively solve mono-objective problems. Our computational experiments show that the min-height packing approach is more relevant to solve the bi-objective problem when the size of the bin becomes large, since the computational effort needed by the vector-packing approach becomes too large in this case. However, for medium sizes of bin, this latter approach leads to good results. References
Alves, C., de Carvalho, J. V., Clautiaux, F., & Rietz, J. (2013). Multidimensional dualfeasible functions and fast lower bounds for the vector packing problem. European Journal of Operational Research (submitted for publication). Caprara, A., & Toth, P. (2001). Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Applied Mathematics, 111(3), 231–262. Chang, S. Y., Hwang, H.-C., & Park, S. (2005). A two-dimensional vector packing model for the efficient use of coil cassettes. Computers and Operations Research, 32, 2051–2058. Clautiaux, F., Alves, C., & Valério de Carvalho, J. (2010). A survey of dual-feasible and superadditive functions. Annals of Operations Research, 179, 317–342. Coffman, J. E. G., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. INFORMS Journal on Computing, 7(1), 1–17. Dell’amico, M., Iori, M., & Martello, S. (2004). Heuristic algorithms and scatter search for the cardinality constrained pkCmax problem. Journal of Heuristics, 10, 169–204. Dell’Amico, M., Iori, M., Martello, S., & Monaci, M. (2006). Lower bounds and heuristic algorithms for the ki-partitioning problem. European Journal of Operational Research, 171(3), 725–742. Dell’Amico, M., & Martello, S. (1995). Optimal scheduling of tasks on identical parallel processors. INFORMS Journal on Computing, 7(2), 191–200. Dell’Amico, M., & Martello, S. (2001). Bounds for the cardinality constrained pkCmax problem. Journal of Scheduling, 4, 123–138. Eilon, S., & Christofides, N. (1971). The loading problem. Management Science, 17, 259–267. Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5–30. Garey, M. R., Graham, R. L., Johnson, D. S., & Andrew (1976). Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, 21, 257–298. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness (Series of books in the mathematical sciences). W.H. Freeman. Geiger, M. J. (2007). Bin packing under multiple objectives – A heuristic approximation approach. In The fourth international conference on evolutionary multi-criterion optimization: Late breaking papers, Matsushima, Japan (pp. 53–56). Glover, F., & Laguna, M. (1999). TABU search. Kluwer. Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45, 1563–1581. Haimes, Y., Lasdon, L., & Wismer, D. (1971). On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Transactions on Systems, Man, and Cybernetics, 1(3), 296–297. Ishibuchi, H., & Murata, T. (1998). Multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man and Cybernetics, 28(3), 392–403.

6.6. Comparison of the two iterative approaches From Tables 3 and 4, it transpires that the best average gap are obtained by the min-height approaches. Since the number and the structure of the subproblems to solve is not the same, we now provide a comparison between the two approaches, using heuristics only. In Table 5, we compare two MHPP heuristics (MB and LL), and the 2VPP heuristic (DotProduct) in terms of solutions and computing time. Heuristic MB performs uniformly bad for all instances (with the notable exception of class 2, n = 50 where it finds a feasible solution whereas LL does not). Since its computing time is larger than the computing time of LL, we will focus on this latter heuristic for the following comparisons. The DotProduct heuristic outperforms LL on average %gap. However, LL is better than DotProduct for the average number of proved optimal solutions ropt. Moreover, DotProduct is often slower than the min-height based heuristics because of the large number of problems to solve. Since the vector packing approach needs to be run a pseudopolynomial number of times, we study in Table 6 the variation of the average computational time when the size of the bin grows. For each instance, we successively multiply the resources sizes by 10, 100 and 1000. The results generated by the DotProduct algorithm show that solving the problem using the vector-packing based approach consumes much more time than heuristics from the min-height based approach (MB and LL). This is due to the pseudo-polynomial number of 2-DVPPs to be solved. Therefore, for large sizes of bin, this approach should not be used.

170

N. Dahmani et al. / Computers & Industrial Engineering 66 (2013) 158–170 Sathe, M., Schenk, O., & Burkhart, H. (2009). Solving bi-objective many-constraint bin packing problems in automobile sheet metal forming processes. In EMO ’09: Proceedings of the 5th international conference on evolutionary multi-criterion optimization (pp. 246–260). Spieksma, F. C. R. (1994). A branch-and-bound algorithm for the twodimensional vector packing problem. Computers and Operations Research, 21(1), 19–25. Talbi, E.-G. (2009). Metaheuristics: From design to implementation. John Wiley & Sons.

Khanafer, A., Clautiaux, F., Hanafi, S., & Talbi, E.-G. (2012). The min-conflict packing problem. Computers and Operations Research, 39(9), 2122–2132. Khanafer, A., Clautiaux, F., & Talbi, E.-G. (2012). Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Computers and Operations Research, 39(1), 54–63. Lee, S., Panigrahy, R., Prabhakaran, V., Ramasubramanian, V., Talwar, K., Uyeda, L., et al. (2011). Validating heuristics for virtual machines consolidation. TechReport MSR-TR-2011-9, Microsoft Research. Liu, D., Tan, K., Huang, S., Goh, C., & Ho, W. (2008). On solving multiobjective bin packing problems using evolutionary particle swarm optimization. European Journal of Operational Research, 190(2), 357–382.