Maximum weight matching and genetic algorithm for fixed-shape facility layout problem |
| |
Authors: | B Sirinaovakul T Limudomsuk |
| |
Affiliation: | 1. Computer Engineering Department , King Monkut's University of Technology Thonburi , 91 Suksawasd 48, Bangkok 10140, Thailand boon@kmutt.ac.th;3. Computer Engineering Department , King Monkut's University of Technology Thonburi , 91 Suksawasd 48, Bangkok 10140, Thailand |
| |
Abstract: | To achieve efficient facility design, the problem of finding an initial slicing tree of a complete graph may influence the layout solutions in many ways. We introduce a maximum weight-matching algorithm to generate the slicing tree, which is used as an initial solution. This initial solution produces modifications to generate alternative layouts for further selection. The system employs a genetic algorithm (GA) as the search engine with a relationship weight function to obtain good solutions. The model is proposed to solve a fixed-shape layout problem. The research has made contributions to two areas. First, it defines a quality function for the clustering technique to generate an initial slicing tree. Second, it designs a process for generating layout alternatives that can take predetermined location constraints and weights based on relationships among facilities into consideration. We compare our initial slicing tree GA with other approaches in the literature. In addition, computational results to demonstrate the performance characteristics of our algorithm are also evaluated. |
| |
Keywords: | Facility layout Floor plan Maximum weight matching Slicing tree Genetic algorithm |
|
|