Intuitively, the two objective functions are of conflicting nature. While a large number of bins allows the packing of bins which are each fully homogeneous, leading to a z2 = 1, a solution being minimal for z1 will require the packing of items **i, j** of different ai and aj into the same bin. It can therefore be suspected that not a single solution x exists in the set of feasible solutions X that equally minimizes both objective functions z1 and z2. In brief, this leads to a vector optimization problem in which a solution x ∈ X is evaluated with respect to a vector Z(x) = (z1(x), z2(x)). The resolution of the problem has consequently to be seen in the identification of all efficient outcomes or the Pareto set P, introduced in the following Definitions 2.1 and 2.2.

Definition 2.1 (Dominance): A vector Z(x) is said to dominate Z(x
′
) iff zk(x) ≤ zk(x
′
)∀k = 1**, . . . , K** ∧ ∃k | zk(x) <
zk(x
′
). We denote the dominance of Z(x) over Z(x
′
) with Z(x)  Z(x
′
).

Definition 2.2 (Efficiency, Pareto-optimality): The vector Z(x), x ∈ X is said to be efficient iff ¬∃Z(x
′
), x′ ∈ X | Z(x
′
)  Z(x). The corresponding alternative x is called *Pareto-optimal*, the set of all Paretooptimal alternatives *Pareto-set* P.

Numerous practical applications of the formal model exist.

In many cases, a minimum number of bins should be used when packing a given set of items, however assuring a maximum possible homogeneousness of the items being packed together into a single bin. Applications include the storage of goods, the storage of music/video data on optical discs, etc.

## Iii. A Heuristic Approximation Approach

As already mentioned in Section I, numerous algorithms have been proposed to solve the single-objective variant of the bin packing problem. One important heuristic is the *Best-Fit* algorithm, important for both for its' time complexity as well as for its' worst-case complexity [6]. Best-Fit subsequently assigns items to the feasible bin having the smallest residual capacity. If no such bin exists, the item is assigned to a previously unused (new) bin.

Unfortunately however, Best-Fit only takes into consideration the weights wj of the items and the residual capacities of the bins when selecting the 'best-fitting'-bin. In order to address the problem described in Section II, a method of controlling the heterogeneousness of the bins needs to be included in the algorithm. Algorithm 1 describes such an attempt, allowing the successive computation of alternatives with different heterogeneousness levels and therefore providing an idea of how to compute an approximation to the vector optimization problem given in Section II.

The modified Best-Fit algorithm is based in principle on the conventional method. However, in order to control the heterogeneousness of the bins, an additional control parameter umax is used as described in step 8 of Algorithm 1. Starting with an initial value of umax = u = 1, only Best-Fit-bins are allowed which are fully homogeneous. This means that an item may only be assigned to a bin containing other elements of identical attributes aj . In this stage of the algorithm, solutions are computed that lead to the lowest possible value of z2 = 1 as all bins contain homogeneous items.

## Algorithm 1 Multi-Objective Best-Fit Algorithm

Require: s, m 1: Compute the maximum possible heterogeneousness of a bin u 2: Set u = 1 3: P
approx = ∅
4: **repeat**
5: for m = 1 to m do 6: Construct a new solution x: 7: **for all** n items do 8: Compute the maximally allowed heterogeneousness umax of the Best-Fit-bin:
umax = ⌊u⌋ with probability 1 − (u − ⌊u⌋) and umax = ⌈u⌉ with probability u − ⌊u⌋
9: Compute the Best-Fit-bin with respect to the randomly determined umax 10: Assign i to the Best-Fit-bin 11: **end for**
12: Update P
approx with x:
Remove all elements in P
approx which are dominated by Z(x);
Add x to P
approx if Z(x) is not dominated by any element in P
approx 13: **end for**
14: Set u = u + s 15: until u > u 16: Return P
approx With increasing value of u, incremented by s in step 14 of the algorithm, Best-Fit-bins become possible that have a higher heterogeneousness. This concept is randomized throughout the generation of the solutions, allowing a gradual transition from umax = u = 1 to the maximum possible heterogeneousness umax = u. Due to the randomness in the algorithm, different runs lead to different outcomes. We therefore propose to compute a number of solutions with each setting of u, given as control parameter m.

Throughout the algorithm, an archive P
approx of the best solutions is kept which is returned after the algorithm terminates. This archive represents an approximation to the true Pareto-set P.

## Iv. Experimental Investigation A. Generation Of Test Instances And Experimental Setup

In order to test the effectiveness of the multi-objective extension of the Best-Fit approximation algorithm, four multiobjective test instances have been computed with values of n = 100, n = 200, n = 500, and n = 1000. The data has been derived taking n 5 bins, each of capacity c = 1000, and randomly splitting the capacity into five items **j, . . . , j**+4 such that the weights wj of the items add up to c:Pj+4 j wj = c.

This means that the so constructed instances have a solution for which the minimum number of bins is n 5 and therefore equal to the trivial lower bound lPn j=1 wj c m.

The items of each instance have been randomly assigned nominal attributes from a set of five different attributes. Each