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, a version of a bin-packing problem exists when loading multiple parts into the build cylinder of a rapid prototyping machine. 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. Dconen et. al. have developed a GA for rapid prototyping called GARP, which utilizes a three-dimensional chromosome structure for the bin-packing of the Sinterstation 2000's 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 initial development of a distributed 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 packing the build cylinder for the rapid prototyping machine.
展开▼
