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.
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 problems which the goal is to pack a collection of objects together into the minimum number of fixed-size bins while optimizing the set of objectives.
3.2 Problem Formulation:
In general, a Multi-objective bin packing problem has two or more objectives involving many decision variables and constraints. Such the classic version of bin packing problem ,the first objective to minimize is the number of the bins also others objectives can be added to optimize them. These problems are formulated as:
Min f1=“n j=1 yj
Opt f2
.
.
Opt fp
gj (x) <= j{1, . . . ,G}
hk (x) = 0 k{1, . . . ,H}
xil <= xi <= xiu {1, . . . , n}
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
with f(f1, f2,.. ,fp) represents the different objectives of the problem, and the vector x= (x1j, x2j, . . . , xkj) means the optimization variables. The functions gj and hk respectively express the constraints of inequalities and equalities of the problem.
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.
Bin Packing: literature review
4.1 Classic Bin Packing
for solving Bin-Packing problem several exact methods were proposed in the literature. The exact resolution of these problems adopt approaches of linear programming, dynamic programming, or branch and bound technique [Beasley (1985) Cung and Hifi (1985)].
Among the theoreticians in this field, Silvano Martello and Daniel Vigo have published several papers that describe exact and approximation algorithms for two and three dimensional bin packing problem. They have presented a lower bound for two-dimensional bin-packing problems with rectangular shapes that may be rotated by 90 degrees [8]. A branch and bound algorithm was used to test the effectiveness of the lower bound. Clautiaux et al. (2006) have also proposed an exact method for 2BP it’s summarized by a dichotomic search of the value of an optimal solution.
4.2 Multi-objective Bin Packing
In the literature many articles were published concerning the multi-objective bin packing problems and many methods had been proposed to solve it and until now the research continues the developing to improve the last results due to the importance of these problems in the real word.
A summary of these publications and the methods of resolutions were presented below:
Solutions Approaches
articles
Researchers
Description
Criteria to satisfied
1DBP
genetic algorithm NSGA-II .
Solving bi-objective many-constraint bin packing problems in automobile sheet metal forming processes
Madan Sathe,
Olaf Schenk,
Helmar Burkhart
this article presents a solution for solving bi-objective bin packing
problems with many constraint using a genetic algorithm NSGA-II combined with clustering algorithm . This method generates always feasible solutions independent of the number of constraints
Minimizing the number of bins
Minimizing costs
2DBP
The multi-objective evolutionary particle swarm optimization algorithm (MOEPSO)
On solving multi-objective bin packing problems using evolutionary particle swarm optimization(2007)
D.S. Liu
K.C. Tan
S.Y. Huang
C.K. Goh
W.K. Ho
It’s a robust method producing good solutions consist despite the difficulty of real word bin packing problem. This method is based on a flexible optimization algorithm which can manipulate permutation in bin level.
minimize the bins
balance the load of each bin
the genetic algorithm with a a new coding scheme
Extending Two-Dimensional Bin Packing Problem: Consideration of
Priority for Items(2009)
Majid Shakhsi-Niyaei
Fariborz Jolai
Jafar Razmi
A genetic algorithm is introduced to solve the problem of maximizing the total profit by considering both revenues and costs, and taking into account the priority of items
maximize the total profit
respect priority of items
Multi-objective algorithm for Strip packing(MOSP) with the best fit heuristic
Multi-objective strip packing using an evolutionary algorithm
(2007)
Simon Illic
Lyndon While
Luigi Barone,
there is a use of multi-objective evolutionary algorithm with the best-fit heuristic that generates solution to this problem.
minimize the height of a packing
minimizing the number of independent cuts required by a packing
3DBP
A heuristic algorithm for solving the multi-criteria problem
A particular approach for the Three-dimensional Packing Problem with additional constraints(2010)
Ana de Almeida
Marisa B.
Figueiredo
two new heuristic methods for the approximation of the 3-BPP without rotation of boxes was presented also a new heuristic algorithm for solving the multi-criteria problem was developed
minimize the bins
accessibilities
removal dates
No Specific dimensionality
a multi-objective classic evolutionary
metaheuristic
an algorithm derived from the greedy randomized adaptive search procedure, named lamda-GRASP
a hybrid procedure
Evolutionnary,constructive and hybrid procedures for the bi-objective set packing problem(2009)
Xavier Delorm
Xavier Gandibleux
Fabien Degoutin
there is a description of the three procedures used to solve the bi-objective bin packing problem. the last one is a hybrid procedure .it’s a combination between the first and the second and it produce a good result for the bi-objective bin packing problem, also this method can be extended for the multi-objective case
the genetic algorithm with the weighting method
multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks(2004)
Akio Ima
Kazuya Sasaki
Etsuko Nishimur
Stratos Papadimitriou
Stowage planning is one of bin packing problems and it is used in transportation.
It’s formulated as multi-objective integer programming and a heuristic algorithm was developed by using the genetic algorithm with the weighting method to solve it.
ship stability
minimizing number of container rehandles required.
a heuristic approximation approach : a modified Best Fit algorithm
Bin Packing under multiple objectives a heuristic approximation approach(2008)
Martin Josef Geiger
a modified Best Fit algorithm is presented to control the heterogeneousness of the bins and to take into consideration the weights of items
Minimizing the number of bins
Minimizing the average heterogeneousness of the bins.
Conclusion
Bin-packing is an extremely well studied combinatorial optimization problem, which arises naturally in many situations. The literature is rich in articles of this problem.
In this chapter we described some of these works. We note that few studies focus on multi-objective bin packing problem, However this variant is encountered in many real problems, Then the solution of multi-objective bin packing problems is of fundamental importance for a wide range of applications such as logistics… but ,it is not easy to solve this kind of problem accurately and fast with classical methods so new approach’s were developed to solve this problems and deserves to be studied and improved more .
Order Now