Variants Of Bin Packing Problem Information Technology Essay

It has been the subject of numerous studies in community operational research. The development of industrial applications has led a growing number of researchers to study them.

Bin packing problem consider sets of objects and containers called bin and the aim is to group objects in such away that they all fit into the minimum number of bins. Usually , the critical aim is to make efficient use of space or time. A bin can not only be a container, but could represent a space in time or a surface area. So in the real world the packing must be without overlaps between goods and other goods or the container walls.

The study of the Packing problems goes back to the origins of operations research .

since the fifties cutting and Packing problems have been addressed in the literature, mainly on problems in one dimension. Today, the literature is very rich on this subject and many articles in two dimensions and three dimensions have been proposed.

This problem was addressed by many researchers. We cite here some theoreticians in this field: Gilmore and Gomory, Berkey and Wang , Lodi , El Hayek , Martello and Vigo…

this problem invaded several domains: The industrial sector is frequently confronted with problems of cutting material. In an effort to reduce costs, the objective is to minimize the amount of material (fabric, paper, wood, glass, metal …) lost in the fall. Also in the transport sector, development of logistics activities is very important. We can consider the storage of 3D objects, but also the filling of containers by taking into account the weight of items; also in the computer sector, we can find applications to bin packing problems when trying to store files on computer supports, or when trying to assign tasks to processors.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

thus, these problems are optimization problems with many practical applications related to real life as stock cutting, scheduling tasks, layouts on computer chips, packing goods into crates, assigning commercials to station breaks on television, loading trucks with a given size or weight limit and storage problems. The list is endless and extremely diverse.

There are several variants of the problems: according to dimensionality ,kind of assignment , the kind of the containers (one container, several containers …) or with the kind of items (item identical, different item,..) . This classification was proposed by Dyckhoff.

the most relevant generalization of Bin Packing is its 2-Dim version, and The most commonly studied case is the so called orthogonal packing, where the items must be packed parallel to the sides of the bin. In some versions,the items are allowed to be rotated. starting from the 1980s a slow but continuous progress was made, mainly concerning the 2-dimensional case.

Optimization problems with multiple objectives arise in most real-word applications. Usually the aim in multi-objective optimization is to identify a set of optimal solutions between the different conflicting objectives .

The classic bin packing problems take into account only the objective of minimizing the number of bins used but the problems that we encounter in the real world are always a lot difficult; there are always many constraints that complicate getting even an optimal solution. In fact, When we add this constraints we speak about the multi-objective bin packing

bin-packing problems and other unsolvable problems are placed by some theorists in a class of mathematical problems known as NP-hard and NP-complete because it is impossible to develop a rapid method to solve this problem optimally .In fact, in all cases, even when only a single bin, the problem remains very difficult and the enumeration of all feasible solutions to find the best one is impossible even for a medium size problem.

But real-world industry continues on using it for everything: scheduling television programming to transport sector and stacking cargo…

Therefore, theorists and scientists developed algorithms to bin packing problems. they have focused on approximated algorithms for this problem. It looks a good solution, without certainty that it is the best solution. However, there is also work to solve it exactly. The interest is to find better solutions. The disadvantage of these methods is that they can not be applied to the difficult problems . We can say that finding the perfect algorithm which derives the optimal solution is not easy .

1.2 Statement of the problem :

The BBP is well known NP-hard combinatorial optimization problems. It raises the following question: What is the minimum number k of identical bins, each with capacity C needed to store a finite collection of n weights w1, w2, w3, … , wn, such that the sum of the weights of the items in each bin does not exceed C?

so the basic idea is to find the best way to pack objects into bins and to combine the items in such a way that as few bins as possible are needed.

The problem is stated as:

min sum_{j=1}^n y_j

sum_{i=1}^{n} c_i x_{ij} leq C y_j, j=1,ldots,n

sum_{j=1}^{n} x_{ij} = 1, i=1,ldots,n

x_{i,j} in {0,1}, i=1,ldots,n, j=1,ldots,n

y_j in {0,1}, j=1,ldots,n

The first inequality means that one can not exceed the size of a box for storage. the right side of inequality requires yj to take the value 1 when an item is placed in the box j. The second inequality requires the object to be stored in only one box .The variable xij will be 1 if item i is stored in the box j, and 0 otherwise and the binary variable yj is equal to 1 if box j is used, 0 otherwise.

This modeling was proposed by Leonid Kantorovich in 1960.

1.3Classification and variants of Bin packing problem

1.3.1 Static Bin packing

These problems have been the subject of numerous studies in the literature and have generated a large amount of publications. The reasons for this are many. Firstly, there are many variations of these problems, which can generate models and methods of different resolution. Then, the objectives and constraints may vary.

this problem belong to the large group of cutting and packing problems.

1.3.1.1Classifications

Dyckhoff Classification

Dyckhoff [1] was the first who proposed a classification of these problems and gives a structure to organize this group of problems. This classification is based on four criteria:the first is the dimensionality :it’s used to identify the size of the problem :one,two,three dimensional problems. the second criterion provides information on the type of assignment :whether you want to place all the items into a number of bins or you have a fixed number of bins and you have to make an optimal selection from the small items(like in the knapsack problem).

the third criterion is the assortment of objects(bins): is there only one object,or are there several of the same size and shape or are there different. The last criterion is the assortment of small items:are they different or identical..?

Dimensionality

One-Dimensional Bin Packing Problem

In the one dimensional bin-packing problem, there is a finite collection of objects which is packed into one or more bins without exceeding the capacity. Each object in one dimensional bin-packing had fixed width and variable height or variable width and fixed height.

This problem may be thought as either a decision problem or an optimization problem.

The decision problem: do all of the objects fit into the bins? there is enough free space to hold the objects or not?

The optimization problem: minimizing the number of bins wasted or the amount of wasted bin capacity.

1.bmp

Fig1.1 one dimensional bin packing

Examples:

Supplying a material such as piping or cable in different quantities. The demands for pieces of the material are for varying lengths that do not exceed the standard length of the material. We must use the least number of standard lengths of the material in producing a given set of required pieces. Hence minimizing the wastage.

Assigning Advertisements with arbitrary lengths to commercial break time slots on television. Each break must last no longer than three minutes.

scheduling a set of tasks with known arbitrary execution times to be executed on some identical processors: It is a scheduling problem; the processors represents the bins and the common bin capacity is the deadline , and the individual execution times of the tasks are the objects .

The Two-Dimensional Bin Packing Problem

In this category of bin packing problem the aim is packing different sized objects (most commonly rectangles) into fixed sized, two-dimensional bins, using as few of the bins as possible. In the two dimensional version, both sides vary. This problem may be thought of as placing rectangles on a flat surface. The classic video game Tetris relates to the problem of rectangle bin-packing.

M3.bmp

Fig1.2 Two dimensional bin packing

Examples:

Stock cutting examples where the quantities of material (metal, glass), are produced in standard sized, rectangular sheets and the demands for pieces are often for rectangles with arbitrary sizes.

A variation on the two-dimensional bin packing problem is the strip packing problem .

Bin-Packing in Three Dimensions

In the Three dimensional bin-packing problems the objects and bins represent

Triplets containing three values: width, length, and height.

Fig1.3 Tree dimensional bin packing

Examples:

we find this type of problem in many industrial situations. Architecture, engineering, and design

The Strip Packing Problem

In this problem we have n rectangles which must be packed into an open-ended bin of fixed width C and infinite height. Our objective is to minimize the overall height of the bin. The difference between this problem and the two-dimensional bin packing problem is that there is only one bin, so instead of trying to minimize the number of bins used, the aim is to minimize the height of the single bin.

M2.bmp

Fig1.4 Strip bin packing

Examples:

the memory resource problem in a multi programmed computer system: The set of tasks represents the objects, their heights corresponds to the amount of processing time they require and their widths the amount of contiguous memory they need. all the tasks must be processed. The objective is to schedule all the set of tasks in the least possible time, so the computers’ memory is used in the most efficient way.

stock cutting: This type of bin packing problems can be found in many industrial settings, where the material such ( paper, sheet metal) comes in rolls of different width. a set of pieces of the materials must be cut from These rolls in arbitrary widths and heights. The goal is then to cut out all the required pieces from the shortest length of roll possible, so minimizing the wastage. In this example, the roll of material corresponds to the bin.

Kind of assignment:

According to the kind of assignment there is two basic situations:

all objects and a selection of items:

in this case there is a set of small items and a set of large objects(bins) but this object is not sufficient to accommodate all the items, therefore there is a selection of the small items with the maximal value to be assigned.

a selection of objects and all items:

Unlike before, in this case the set of objects is sufficient to accommodate all items. So there is a selection of objects with the minimal value.

Examples:

the value of objects/items can be represented by costs , revenues .

Assortment of small items

Identical small items

In this case all items are of the same shape and size.

Weakly heterogeneous assortment

In this problem category the items can be grouped into few classes.

If they are identical in the shape and the size and if they requires the same orientation so they are treated as identical kinds of items

Strongly heterogeneous assortment

The items which have the same shape and size are very few; consequently when they occurs they are treated as individual elements.

Assortment of large objects

One object

In this case there is only one object as the problem of the strip bin packing.

Several identical objects

All objects are of the same shape and consist of homogenous material

Several different objects

In this problem category objects are non-homogeneous (rectangular and circular ).this type of problem is present when the stock material is including defects

Lodi’s Classification :

Lodi et al [2] proposed the following typology for categorizing different bin packing problems. This typology is based on taking into account orthogonal rotations of components as well as the cut type. The rotation of 90 rectangles can increase the size of the search space, and the probability of finding the best solution. Finally in the cutting problems, a guillotine constraint can be imposed: the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. Guillotine cuts only allow a cut from one side of the stock sheet to the other

The typology of Lodi et al can be summarized as follows:

2BP|O|G: the item are oriented (O) they cannot be rotated and guillotine cutting (G) is required.

2BP|R|G: the items may be rotated by 90 deg (R) and guillotine cutting is required.

2BP|O|F: the items are oriented and cutting is free (F).

2BP|R|F: the items may be rotated by 90 deg and cutting is free.

Many publications was found in the bin packing and stock cutting literature: 2BP|O|G was firstly described by Schneider(1988) .Vasko ,wolf and Stott discussed the 2BP|R|G problems(1989) ; also 2BP|O|F was studied by Lagus,karanta and Yld Jddski(1996) and several applications of 2BP|R|F are mentioned by Bengtsson(1982).

1.3.1.2 Variants:

Several variants of Bin-Packing are known in the literature:

knapsack problem:

Given a number of items, we are required to select a subset to carry it in a fixed capacity of a bin (knapsack).items differ by their value. The aim is to load items which maximize the overall reward without exceeding the capacity.

subset-sum :

The subset-sum problem is not strictly speaking, a Bin-Packing problem but it seems sometimes as a special case of the knapsack problem.

Given a sequence of integers a1… an and a parameter k,decide whether there is a subset of the integers whose sum is exactly k.

1.3.2 Dynamic Bin packing

Another well-studied version of the bin packing problem is the dynamic problem known as on-line bin packing problem , here items arrive at arbitrary times one by one. this sequence of items must be packed into unit-size bins, such that the maximum number of bins used over all time is minimized.

In this variant of bin packing problem, each item must be assigned to a bin, without the knowledge of subsequent items. also, the migration of items from one bin to another is not allowed, items cannot be moved .

sequential bin packing :

In this variant of the on-line bin packing problems the sequence of items are received one by one. the decision maker must decide if the next item is packed in the currently open bin or the bin is closed and a new bin is opened before the revelation of the size of the next item . The aim is to minimize the loss accumulated over n periods. When a new item does not fit in the bin, it is lost. Also the free space in the closed bin accounts for a loss.

k-item bin-packing problem :

The k-item bin-packing problem imposes the constraint that at most k items are packed together into one bin.

Online bin packing with arbitrary release times

this online model items arrive one by one .in each item ai is associated with a size and a release time ri . In this variant, each bin has a time axis [0, 1] from the bottom to top, so every items must be placed at least ri above the bottom of a bin.

The goal is to pack all items into unit-size bins and minimize the number of bins used.

Variable sized online bin packing

in this version of the problem the bins do not all have the same capacity .There are an infinite number of bins of each capacity; and each piece must be assigned in turn, without knowledge of the next pieces.

The objective is to minimize the sum of the capacities of the bins used.

there is an other version of this problem where all information of the items are known.

but we cannot preview the types of the bins before packing. also in each bin the size is not less than the size of the largest item.

Variants

Researchers

Articles

sequential bin packing :

Andr´as Gy¨orgy

G´abor Lugosi

Gy¨orgy Ottucs´ak

On-Line Sequential Bin Packing(Journal of Machine Learning Research 11 (2010))

k-item bin-packing problem :

Luitpold Babel

Bo Che

Hans Kellerer

Vladimir Kotov

Algorithms for on-line bin-packing problems with

cardinality constraints(2003)

Online bin packing with arbitrary release times

Yongqiang Shi

Deshi Ye

Online bin packing with arbitrary release times(2007)

Variable sized online bin packing

Guochuan Zhang

A new version of on-line variable-sized bin packing(1997)

1.4 Heuristics for solving the BBP:

As in all combinatorial problems, many heuristics have been proposed for the Bin Packing problem in order to find good solutions in a reasonable time.

These strategies were used at the first time for the 1BP and then they had inspired several approaches for the resolution of BBP of higher dimension .hence many researchers had solved bin packing problems with fast heuristic algorithms:

first fit decreasing (FFD):in this algorithm the items are first placed in orderof decreasing weight. Then for each item to be processed. The algorithm iterates through the list of existing bins and places into the first bin that it will fit. if no bin is left the item can fit in, a new bin is started. This heuristic is described in algo 1.1 .

Another often used fast heuristic is

Best Fit Decreasing (BFD): This heuristic is described in algo 1. 2. The only difference with FFD,is that the items are not placed in the first bin that can hold them but the item is placed into the bin which will leave the least space after the item is placed in the bin.

the worst case performance for this two algorithms is 11/9opt+4 ;which opt is the number of bins in the optimal solution of the problem.

Next Fit Decreasing (NFD) : this heuristic sort objects in descending order of heights and apply the strategy : In this strategy we consider only one bin opened at once. The objects are arranged successively in the open bin as long as there is place for the current object .otherwise the bin is being closed and a new bin is opened.

1.Sort the items in order of decreasing weight

2.Remove the first item, and place it in the first bin that has enough space left to hold it .if no bin is empty enough ,start a new bin

3.Repeat step 2 until all items are placed in a bin

Algo1.1: FFD

1.Sort the items in order of decreasing weight

2.Remove the first item, and place it in the best filled bin that has enough space left to hold it .if no bin is empty enough ,start a new bin

3.Repeat step 2 until all items are placed in a bin

Algo1.2: BFD

Several heuristics have been proposed for the 2BP. these heuristics can be divided

into two different families Lodi et al. [3]:algorithms in one phase and the algorithms in two phases.

Algorithms in one phase consist in storing the objects directly in bins, while the algorithms with two phases is beginning first by storing objects in a bin of infinite height to search a solution for strip-packing problem. In the second phase, an algorithm for solving the problem consist in using the solution of Strip Packing problem obtained in order to arrange the objects in the bins to be used.

One phase Algorithms:

These algorithms consist in arranging items iteratively

in bins. we study the order of objects and their position in the bin. Among the algorithms that proceed in one phase, we find some who place the objects by levels as the algorithm Finite First Fit (FF).these objects are sorted in descending order. the current object is placed in the lowest level of the first bin that can contain it otherwise a new level is created or a new bin is considered.

Other algorithms does not fall items by level, these strategies are known as the Bottom-left (BL): always the current object is placed in position over the bottom and left-most possible.

Two phases Algorithms:

Start by packing the items into a single bin with a width and infinite height. First we sort objects according to their decreasing heights and then put them in the bin, thus forming levels defined by the height of the tallest object layer in the second phase, the strip solution is used to construct a packing into bins.

A two-phase algorithm for the finite bin packing problem, called Hybrid First-Fit (HFF), was proposed by Chung, Garey and Johnson [4]. In the first phase, a strip packing is obtained through the FFDH strategy. Let H1;H2… be the heights of the resulting shelves, and observe that H1 ¸ H2 … A finite bin packing solution is then obtained by heuristically solving a one-dimensional bin packing problem (with item sizes Hi and bin capacity H) through the First-Fit Decreasing algorithm: initialize bin 1 to pack shelf 1, and, for increasing i = 2;…, pack the current shelf i into the lowest indexed bin where it fits, if any; if no bin can accommodate i, initialize a new bin. An example is shown in Figure 1.5.

img.bmp

Fig 1.5 First and second phase of algorithm HFF

Berkey and Wang [5] proposed and experimentally evaluated a two-phase algorithm,

called Finite Best-Strip (FBS), which is a variation of HFF. Also Lodi et al. [6,7] presented an approach (Floor-Ceiling, FC) which extends the way items are packed on the levels.

Multi-objective optimization:

In the real world it is extremely rare to find a problem with a single value or objective. Hence multiple objectives have to be optimized.

2.1 Statement of the problem

The multi-objective optimization , or multi-criteria optimization, refers to finding values of decision variables to realize the optimum solution of more than one objective. contrary to the single-multi-objective optimization which gives a unique solution, there will be many optimal solutions for a multi-objective problem.

Hence there is no single solution to such problems and there is a large family of alternative solutions and different balances of the various objectives. This diversity of solutions precludes ‘right’ or ‘wrong’ decisions.

generally, this type of problem can have two or more objectives involving many decision variables and constraints. MOO problem can be written as:

min f (x) = (f1 (x) , f2 (x) , . . . , fp (x))

s.q.

gj (x) <= j{1, . . . ,G}

hk (x) = 0 k{1, . . . ,H}

xil <= xi <= xiu {1, . . . , n}

where fi is the i-th objective function and f (x) = (f1 (x) , f2 (x) , . . . , fp (x)) represents the different objectives of the problem, x = (x1, x2, . . . , xn) means the optimization variables. Each variable xi is between two bounds xil and xiu

g and h are the inequality and equality constraints respectively.

In the context of multi-objective problems, there is no single optimal solution but a set of optimal solutions. The resolution of such problems is to find all of these solutions. In this set no one is better than another.

2.2 Methods for solving multi-objective optimization problems:

Many methods for considering more than one objective are available for solving MOO problems.these methods can be categorized into two families: non Pareto approaches and Pareto approaches

Non-Pareto approaches involve converting the MOO problem into one or a series of SOO problems. Each of these problems implies the optimization of a ‘scalarizing’ function, by the use of a method for SOO. Many MOO methods exist due to the variety of way of defining a scalarizing function. A well-known combination method is the weighted linear sum of the objectives.

Although other methods are bringing the problem to a single-objective optimizations problem have been presented in the literature. The best known methods E- constraints, the Min-Max method…

Pareto approaches that do not transform the objectives of the problem are presented through evolutionary algorithms (EA).

Evolutionary Algorithms:

EAs began their existence during the late 1960 and early 1970. In these period many different scientists began the research of putting Nature and biological word at work in algorithmic, to solve problems. Three different EA models were appeared due to the existence of these different sources .

Therefore these algorithms take their inspiration and aspects from natural selection or survival of the fittest.

An evolutionary algorithm maintains a population of structures (usually randomly generated initially), that evolves according to rules of selection, recombination, mutation and survival :given a population the environmental pressure causes natural selection(survival of the fittest).Based on the fitness of population some candidate are chosen to be presented in the next generation and to apply recombination and mutation to them. Recombination is an operator which is applied to the selected candidate (parents) and the result is one or more new candidates (children).Mutation is applied to one candidate and the result is a new candidate.

a set of new candidates(offspring) based on their fitness is obtained after executing recombination and they can be placed in the next generation .the process is iterated until founding sufficient solution or a previously set computation limit is reached.

Hence ;this process make the population adapts to the environment better and better.

EA have been used in different problems from many domains: machine learning, optimization, automatic programming, operations research, bioinformatics and social systems.

alg1.bmp

Algo 1.3: The general scheme for EA in pseudo-code

In the history there are many variant of EA.The common underlying idea behind all these techniques is the same and they differ only in technical details. These classical variants are:

Evolutionary Programming (EP):

this EA family was used in the work of Fogel et al.It was appeared in the US in 1960. EP focuses in the adaption of individuals rather than in the evolution of their genetic information. Mutation is the main variation operator is mutation. This behavior is modeled by using a finite automata or graphs.

Evolution Strategies (ES):

These techniques were initially developed in Germany by Rechenberg and Schwefel . They were the first evolutionary algorithms. Their original goal was serving as a tool for solving engineering problems. Mutation is sometimes the unique reproductive operator used in ES. Since their appearance in 1965, several variants have been developed: (1 + 1) − ES, (μ + lamda) -ES; and PAES versions of multi-objective evolution strategies.

Genetic Algorithms (GA):

The GA are the best known evolutionary algorithms and the most widespread variant. They were conceived by Holland . His work has had a great influence in the development of the field.

Genetic algorithms are based on the principles of survival and reproduction .

these heuristics are used to generate useful solutions to optimization and search problems.they search to improve the current population.

GAs use recombination (or crossover) operator as the primary search tool this is there main Characteristic. In these algorithms the parts of solution can be discovered independently and combined later. Additionally, mutation is also used, as secondary operator.

There are several varieties of genetic algorithms: the algorithms mono-objective, multi-objective, generational (generational GA), the continuous generation algorithms

(Steady-state GA).The algorithms NSGA-II and SPEA2 are the best known multi-objective genetic algorithms. They are based on the concept of dominance to rank the solutions.

SPEA 2: The Strength Pareto Evolutionary Algorithm 2 is a recent technique for finding -optimal set for multi-objective optimization problems. , hence, this algorithm has been used in many applications because he has shown very good performance. SPEA 2 is based on SPEA but it was designed to overcome the complicated problems.

NSGA-II: NSGA-II is a very famous multi-objective optimization algorithm and one of the most efficient multi-objective evolutionary algorithms using elitist approach proposed by Deb et al.

In different studies these algorithms had shown very good solutions in comparison to other multi-objective evolutionary algorithms and many computers scientists and mathematicians have referenced on this type of algorithms to solve multi-objective problems. However, there are others multi-objectives algorithms which the first date from the 1980s: VEGA, VOES, RWGA, MOGA, NPGA2

There is an interaction between these families; they were not isolated from each other. so as a result of this interaction new variants have emerged . We can cite the following:

Evolution Programs:

This term is due to Michalewicz , and comprises techniques of functioning of GAs, with a complex data structures.

Genetic Programming (GP):

These techniques were appeared in the work of Cramer and initially developed by Koza.

It is a specialization of genetic algorithms (GA) where each individual is a computer program. Such programs are encoded by trees.

Memetic Algorithms (MA):

these techniques are an extension of the traditional genetic algorithm. It uses a local search technique These algorithms are useful in solving complex problems.

Multi-objective Bin packing:

The problems that we encounter in the real world are always a lot difficult; there are always many constraints that complicate getting even an optimal solution.

So to be more near to the real word, we should add extra constraints as the gravity , Another constraint may be the weight because real objects have mass and weight, and we may not range a large, heavy objects also certain objects require priority.

In fact the constraints are endless and the classic-bin packing problem does not take these constraints into account, for reasons of simplifications. When we add this constraint we speak about the multi-objective bin packing.

3.1 Definition

Multi-objective Bin Packing problems are a class of optimization problem