People.uncw.edu



CSC 380Fall 201611/28/16Bin Packing OptimizationBy: Rachel Jackson & Kirklyn FieldsCSC380 Final Report AbstractBin packing is a commonly known problem within computer science with many algorithmic solutions and a variety of applications. Bin packing algorithms have been used for storing files on disk, job scheduling, and even shipping items. In this paper we consider three different algorithms for creating packing solutions that minimize the number of containers needed to pack a finite set of items. The purpose of this report is to detail our experimental process of designing our algorithms and report and compare the results of our findings. Introduction The problem our team has chosen to investigate this semester is the widely known bin-packing problem. There are two types of bin packing problems, online and offline. Online bin-packing is differentiated by the arrival of items that need to be packed one at a time. Contrarily, in offline bin-packing all items are present and can be dealt with at one time. For the purposes of this project we will only focus on offline bin-packing.Previously we proposed to study the optimization of parking lot designs using bin packing algorithms. However, we ran into several difficulties trying to solve the problem within the necessary constraints intrinsic to the problem domain. Because our original project boiled down to a bin-packing problem we decided to drastically simplified our project plan to study and compare algorithmic approaches to the bin-packing. The three algorithms we chose to research, implement and compare were Exhaustive Search, First-Fit Decreasing approximation and a Genetic Algorithm.Why 380?This project is worthy of study within CSC 380 because it requires us to design and implement our own realizations of the algorithms we will analyze. The bin packing problem is a widely known area of interest within Computer Science, and has several useful applications in many problem domains such as memory allocation, shipping items, and job scheduling. Literature ReviewCountless computer scientist have researched the bin backing problem and its solutions. In his article “Fast Algorithms for Bin packing”, David Johnson of the Massachusetts Institute of Technology analyzed several adaptations to First Fit and Best Fit packing algorithms. First fit packs items in arbitrary order into the left most bin [2]. On the other hand, Best Fit assigns items so as to maximize the capacity of the bin into which it goes without exceeding the maximum volume of that bin [2]. That is pack the item as tightly as possible. Johnson found the variety of heuristic variations to these common algorithms had similar worst case behavior [2]. Another researcher Gy¨orgy D?osa also explored First Fit Decreasing (FFD) focusing on the ”tight bound” of the algorithm. In their article “The Tight Bound of First Fit Decreasing Bin-Packing,” they demonstrated for an instance of items I, the optimal algorithm OPT(I) using FFD is less than or equal to 11/9OPT(I) +6/9 [1]. It is also possible to utilize the common genetic algorithm to solve the bin packing problem. Belgian researcher Emanuel Falknauer in his article “A Hybrid Grouping Genetic Algorithm for Bin Packing” compares the genetic grouping algorithm (GGA) to the classic style genetic algorithms applied to bin packing. Viewing the packing problem as a partitioning of a set of U items in to a collection of subsets, Falknauer aims to find a grouping of those items [3]. The objective of grouping is to optimize a cost function defined over a set of all valid groupings [3]. A special encoding scheme is used to make those valid grouping solutions which become the “chromosomes” of the hybrid GGA. Falknauer demonstrated the hybrid GGA was superior in creating better candidate solution than the classic genetic algorithm [3].Problem StatementsInformal Statement A collection of objects of different sizes must be packed into a finite number of containers or “bins”. Each of these bins has a fixed volume. All items must be packed in such a manner minimizes the total number of bins used. An optimal solution uses the least amount of bins, while packing all of the items. A hard constraint is the sum of weights of the items that need to be packed. Formal StatementGiven a set of bins , B with the same size S, and a list of j items each with sizes to pack inside of those bins, find the minimum number of bins ,K ,such that the sum of items within each bin is less than or equal to the capacity of the bin.Mixed Integer Programming formulation: Minimize K=i=1nBiSubject to j=1nB(wj)?≤SK = the number of bins needed to pack all items Bi = the ith bin wj = the weight of items within bin B(i)S = The capacity for every bin (all bins have the same capacity Experimental ProcedureMany algorithmic strategies already exist to solve bin packing problems, however our problem is naturally NP-hard, thus there will not be much optimization possible in respect to time. Instead we will measure which algorithm will minimize the total number of bins used to pack a fixed same array of items. The capacity of each bin will be the same. We experimented with three algorithms: Exhaustive Search, First Fit Decreasing Approximation, and a Genetic Algorithm. For the purposes of comparison and keeping run time manageable with exhaustive search, we used the same small array of items, [10,10,8,7,6,7,1,2,3], for each packing algorithm. The first algorithm we researched and implemented was Exhaustive Search, a brute for approach using combinational logic The goal of this algorithm is to generate every possible combinations of elements and select the permutation that satisfies constraints, then finding the desired result. In the bin packing problem the goal is to generate all the subsets of the set of n items and then see if any of the subsets satisfy the constraints. Finally, the last step in the algorithm will be to compare the results to return the best option. Here is some pseudocode for this algorithm:For each item in the list of items:Add item to totalif total less than size of binadd item to binif bin is fullCreate a new bin Pack item For each result of total bins from each iterationFind least amount of binsreturn resultAnother algorithm we implemented was First Fit Decreasing Approximation. This algorithm uses a greedy approximation approach that preprocesses items with a time complexity of O (nlogn). Unlike a regular First Fit approach, items are first sorted in decreasing order before they are packed into each bin. This helps to prevent the creation of excessive bins by packing the largest items first, rather than encountering those items later on in an arbitrarily ordered list and attempting to pack them into bins that will be unable to accommodate them. Initially the number of bins is set to 0, and all bins are empty. The first bin is automatically created when the first item is encountered and packed. For each item in the list, attempt to pack that item into the first available bine If that item will not fit, create a new bin and pack that item.Below is the pseudo code used to implement the algorithm:Sort items to be packed in to decreasing order. For each item:Try: place the item in the first bin If no bin is found:Create a new bin Pack item To demonstrate how First Fit Decreasing would pack a list of items [10,10,8,7,6,7,1,2,3], with a bin capacity of 30 below is table that shows the content of a bin as each item is visited within the for loop and packed into the existing bins. Items being packed???????TotalBinsUsedBin 110???????10?1010??????20?10108?????28?101087????FullBin 27???????7?76??????13?763?????16?7633????19?76332???21?763321??22????????2 BinsThe last algorithm we researched and implemented was Hybrid Genetic Algorithm. To begin a population of 100 parent solutions generating using the first fit algorithm is initialized. For a total of 50 generations, two parents were selected at random. Offspring were then created from these parents using crossover and mutation. Crossover was achieved by cloning two parents, and then picking two crossover locations to swap bins between the parents and its clone. If any, duplicate items are then removed from the child solution, and any unused items are then packed into the child. Next mutation is allowed with a 50 percent probability of occurring. Simply, random bins were selected to be destroyed and the contents of those bins were saved and then repacked. Finally, the new offspring’s fitness is graded by the function below:Fitness =i=1n(Sic)kn [cite HGGA]n = number of binssi = sum of the ith binc = capacity of the bink = 2 (can be any constant greater than1)Below is the pseudo code we used to implement this algorithm:Initialize a population of possible solutionsFor a specified amount of time:Select two parentsGenerate offspring through crossoverMutationGrade Fitness Sample output of the algorithm I implemented can be seen in the chart below with a bin size of 30.Initial population example bins: [ [7,1], [6], [7], [8], [10], [10]], [[1,8], [10]], [[1,7], [10], [10]], [[10], [1,6]], [[10], [7,1], [10], [6], [8], [7]], [[8,1]], [[10], [7,1], [6], [7], [10], [8]]…]Generation #Best Fitness ScoreBins used1.87711112.87711113.87711114.87711115.8771111…50.8771111Here I ran into some issues in implementation because the algorithm was returning the best fitness score in the population from a chromosome solution that did not pack all of the items in the list. I believe this is a result of the mutation function not properly repacking items from bins that were deleted and how the population is being updated between generations. In the future, more time and study would be needed to prefect the genetic algorithm for bin packing in order to properly compare the results to exhaustive search and FFD.Results and ConclusionsAs expected first fit decreasing and the genetic algorithm performed faster than exhaustive search and give near optimal solutions, however they do not always find the optimal packing. FFD uses at most (4M + 1)/3 bins where M is the optimal amount of bins. Below is a chart comparing the result of bin size and number of bins used between Exhaustive search and FFD. The x-axis denotes the bin size, and the y-axis is the number of bins used to pack the items in the array. As demonstrated by the graph above, both the first fit decreasing algorithm and exhaustive search algorithm both return the same result of total bins throughout the experiment. A lower bound exists on the bin capacity where the bin size must at least be as big as the largest item in the list in order to pack all items. As the bin size increase the number of bins used for both algorithms decreases. Below is a chart comparing the time complexities of FFD and Exhaustive search. As you can see Exhaustive search takes longer amount of time to execute as the bin capacity increases because the number of possible combinations of item packings increases as well. In the future we the future we would to correct the genetic algorithm so we may compare its solutions more accurately with our other two algorithms. In addition, we would like to apply these algorithms to a real world problem much like the original parking lot optimization problem we first proposed to solve.BibliographyD?osa, Gy¨orgy. "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm I." (n.d.): n. pag. Department of Mathematics, University of Pannonia, Veszpr?em,. Web.Falkenauer, Emanuel. "A Hybrid Grouping Genetic Algorithm for Bin Packing."?Journal of Heuristics?2.1 (1996): 5-30.?Springer. Web.Johnson, David S. "Fast Algorithms for Bin Packing."?Journal of Computer and System Sciences?8.3 (1974): 272-314. Web.Martello, Silvano, and Paolo Toth. "Lower Bounds and Reduction Procedures for the Bin Packing Problem."?Discrete Applied Mathematics?28.1 (1990): 59-70. Web ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download