A Branch and Bound Algorithm for Solving Facility Layout Problems Using Symmetries

DOI Web Site 1 Citations 9 References

Bibliographic Information

Other Title
  • 対称性を利用した設備最適配置問題解法のための分枝限定アルゴリズム
  • タイショウセイ オ リヨウ シタ セツビ サイテキ ハイチ モンダイカイホウ ノ タメ ノ ブンシ ゲンテイ アルゴリズム

Search this article

Abstract

We consider facility layout problems where mn machines (facility modules) are assigned mn to cells. These cells are arranged into a rectangular pattern with m rows and n columns. As the objective function, we consider flow costs and adjacent factors between machines. In these facility layout problems, we aim to obtain the machine layout that has the minimum objective value, namely the optimal layout. In obtaining the optimal layout with the existing branch and bound algorithm, we must try to search all layouts. However, in these layouts, there exist obviously many layouts having the same objective function values. For one layout, there exist some layouts obtained by rotation and/or reverse operation. These layouts obviously have the same objective function value. Even if using the existing branch and bound algorithm, we must search the above layouts, and this seems to be inefficient. In this paper, we propose a theorem that states the condition which enumerates only original layouts and automatically removes the layouts that are different due to rotation and/or reverse operation. This condition is called the condition for removing symmetry in this paper. We also propose an efficient algorithm for these facility layout problems using this theorem, which is based on a branch and bound method. We executed some numerical experiments with a personal computer in order to compare our proposed algorithm with the existing algorithms. The results show that our proposed algorithm is useful.

Journal

Citations (1)*help

See more

References(9)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top