A Genetic Algorithm for Bin Packing and Line Balancing

Algorithm for BPP running in polynomial time (and there will most probably never be one). However, [Garey and The bin packing problem can be best described in Johnson,79] cite simple heuristics which can be shown to 'transportation' terms: given a set of boxes of different be no worse (but also no better) than a rather small sizes, how should one pack them all into containers of a multiplying factor above the optimal number of bins. The given size, in order to use as few containers as possible?

idea is straightforward: starting with one empty bin, take The task of balancing of (robotized) assembly the objects one by one and for each of them first search lines is of considerable industrial importance. It consists the bins so far used for a space large enough to of assigning operations from a given set to workstations in accommodate it. If such a bin can be found, put the object a production line in such a way that (1) no assembly there, if not, request a new bin. Putting the object into the precedence constraint is violated, (2) no workstation in the first available bin found yields the First Fit (FF) heuristic. line takes longer than a predefined cycle time to perform Searching for the most filled bin still having enough space all the tasks assigned to it, and (3) as few workstations as for the object yields the Best Fit, a seemingly better possible are needed to perform all the tasks in the set. heuristic, which can, however, be shown to perform as This paper presents a genetic grouping algorithm well (as bad) as the FF, while being slower. for the two problems. We first define the two problems precisely and 1.2 The Line Balancing specify a cost function suitable for the bin packing problem. The line balancing problem (LBP) can be descri- Next, we show why the classic genetic algorithm bed as follows: given a set of tasks of various lengths, performs poorly on grouping problems and then present an subject to precedence constraints (i.e. some tasks have as encoding of solutions fitting them. prerequisite the completion of one or more other tasks, see We present efficient crossover and mutation ope- [Sacerdoti,77]), and a time constant called cycle time , how rators for the bin packing. Then we give the modification should be the tasks distributed over workstations along a necessary to fit these operators for the line balancing. production (assembly) line, so that (1) no workstation We follow with results of performance tests on takes longer than the cycle time to complete all the tasks randomly generated data. Especially the line balancing assigned to it and (2) the precedence constraints are tests largely cover the real-world problem size. complied with? We conclude with a discussion of the results and In more formal terms, we define the LBP as the areas of further research. following decision problem: Given a...

Website: www.cse.hcmut.edu.vn | Filesize: -
No of Page(s): 7
Download A Genetic Algorithm for Bin Packing and Line Balancing.pdf