Solution methods to the machine layout problem

Rasmus Andersen

AbstractIn a production facility machine locations are an important factor when calculating the material handling cost.

This report reviews different methods for optimizing the placement of the machines. The methods try to minimize the distance that the materials and semi fabrics will have to move to get from one machine to another when also taking into account that a rearrangement of machines has a price.

The first method uses reduced integer programming. It locates the machines in a hexagonal graph in order to determine the relative positioning between the machines. This information is used to nd a small size integer program that solves the problem.

The second method uses ant colony optimization to solve the problem. Ant colony optimization is a meta-heuristic that uses a methods similar to that of ants when these find the shortest path from their nest to a food source. This method has been implemented and tested on various problems.

The last method uses simulated annealing to solve the problem. Various neighborhood generating methods have been reviewed and tested. Different machine layout problems have been solved using simulated annealing and ant colony optimization to investigate their relative performance.

The solutions found using reduced integer programming are not as good as those found using simulated annealing or ant colony optimization. When comparing simulated annealing and ant colony optimization it is concluded that for small problems ant colony optimization is better than simulated annealing, but for large problems it is the opposite.
TypeMaster's thesis [Academic thesis]
Year2006
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-Thesis-2006-41
NoteSupervised by Jens Clausen, IMM
Electronic version(s)[pdf] [ps]
BibTeX data [bibtex]
IMM Group(s)Operations Research