A distributed chromosome genetic algorithm for bin-packing

Abstract Genetic algorithms (GAs) are excellent approaches to solving complex problems in optimization with difficult constraints. The classic bin-packing optimization problem has been shown to be a NP-complete problem. The loading multiple parts into the build cylinder of a rapid prototyping machine is a type of a bin-packing optimization problem. There are GA applications that work with variations of the bin-packing problem, such as stock cutting, vehicle loading, air container loading, scheduling, and knapsack problems. These applications are mostly based on one-dimensional or two-dimensional considerations, using very specific assumptions. Ikonen et al. (A genetic algorithm for packing three-dimensional non-convex objects having cavities and holes. In: Proceedings of the Seventh International Conference on Genetic Algorithms. Michigan State University, July 19–23, 1997.) have developed a GA for rapid prototyping called GARP, which utilizes a three-dimensional chromosome structure for the bin-packing of a Sinterstation 2000s build cylinder. GARP allows the Sinterstation 2000 to be used more productively by designing a packing method for multiple parts. GARP was developed using a sequential GA, so execution time is influenced by the number of parts to be packed. Anticipating greater use of time compression technologies, GARP's execution time needs to be reduced. This paper will detail the development of a distributed chromosome GA to reduce the execution time of GARP. The implementation of this distributed GA will improve the efficiency of GARP, by using multiple CPUs to help solve the problem of bin-packing the build cylinder for the rapid prototyping machine.