基因演算法應用於設施佈置問題之研究

A Study of Facility Layout Problem by Genetic Algorithm

王明展(Ming-Jaan Wang)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/博士(2003年)

摘要

基因演算法應用於設施佈置問題之研究
學生：王明展 指導教授：胡黃德 博士
元智大學工業工程與管理研究所
摘 要
尋找最低的物料搬運成本，是設施佈置設計人員長久以來追求的目標。然而大部門數的設施佈置其最佳解的求算常是耗時不易得的，因此許多的啟發式演算法如：模擬退火（Simulated Annealing, SA）、塔布搜尋（Tabu Search, TA）、基因演算（Genetic Algorithm, GA）等方法被發展出來，以求得近似最佳解。本論文使用基因演算法及應用專家系統IF-THEN的規則發展一套空間填滿曲線（Space Filling Curve, SFC），來求間斷式設施佈置的最佳解。有關面積相等部門的佈置問題，其目標函數值的衡量是以物料流動因素成本（Material Flow Factor Cost, MFFC）為唯一考量。而有關面積不相等部門的佈置問題，其目標函數值的衡量是以總佈置成本 (Total Layout Cost, TLC)最小為考量，TLC為一多考量因素的目標函數，除了考慮物料流動因素成本外，更加入了形狀比率因素（Shape Ratio Factor, SRF）及面積利用率因素（Area Utilization Factor, AUF）。過去已發表的間斷式設施佈置文獻，少有針對部門的不規則形狀與廠房面積使用情形作一衡量與改善。本論文提出一套改善面積100%使用與調整部門不規則形狀成規則矩形形狀的方法。經由八個面積相等、五個面積不相等案例的實證結果得知，不論在面積相等部門或面積不相等部門的設施佈置問題上，本論文所發展方法均獲得較佳的成效。
關鍵字：基因演算法、空間填滿曲線、物料流動因素成本、形狀比率因素、面積利用率因素、總佈置成本

關鍵字

基因演算法 ； 空間填滿曲線 ； 物料流動因素成本 ； 形狀比率因素 ； 面積利用率因素 ； 總佈置成本

並列摘要

A Study of Facility Layout Problem by Genetic Algorithm
Student : Ming-Jaan Wang Advisor : Dr. Michael H. Hu
Institute of Industrial Engineering and Management
Yuan-Ze University
ABSTRACT
Minimal material handling cost (MHC) achievement is one of the critical objectives in facilities layout problems for layout designers. However, solving the larger departments of facilities layout problem accompanying with the optimal MHC is time-consuming or even infeasible. Therefore, many heuristic algorithms such as simulated annealing (SA), tabu search (TA), and genetic algorithm (GA) were developed to find out near-optimal solutions for MHC. This study used genetic algorithm and a rule-based expert system to implement and create space filling curve (SFC), for achieving the optimal solution of the discrete facility layout problem. Concerning the equal area department problems, the objective function is mainly according to the measurement of material flow factor cost (MFFC). However, the objective function for unequal area department problem in this study is a multiple criteria, involving MFFC, shape ratio factor (SRF), and area utilization factor (AUF) to reach minimal total layout cost (TLC). Then, a method of modified the irregular-shape departments to regular-shape ones and eliminate the redundant areas based on the principle of 100% area utilization is proposed. The experimental results show that the proposed approach is much more feasible for dealing with the facilities layout problems and better than existed results.
Keyword: Genetic Algorithm, Space Filling Curve, Material Flow Factor Cost, Shape Ratio Factor, Area Utilization Factor, Total Layout Cost

並列關鍵字

Genetic Algorithm ； Space Filling Curve ； Material Flow Factor Cost ； Shape Ratio Factor ； Area Utilization Factor ； Total Layout Cost

參考文獻

Abdinnour-Helm, S. and S. W. Hadley, “Tabu search based heuristics for multi-floor facility layout,” International Journal of Production Research, 38(2), pp. 365-383, 2000.

Apple, J. M., Plant Layout and Material Handling, John Wiley & Sons, Inc., New York, 1983.

Aromur, G. C. and E. S. Buffa “A heuristic algorithm and simulation approach to the relative location of facilities,” Management Science, 9(2), pp. 294-309, 1963.

Banerjee, P., B. Montreuil, and C. L. Moodie, “A modeling of interactive facilities layout designer reasoning using qualitative patterns,” International Journal of Production Research, 30(3), pp. 433-453, 1992.

Bargholdi, J. J. and L. K. Platzman, “An O(n log n) planar travelling salesman heuristic based on spacefilling curves,” Operational Research Letter, 1(4), pp. 121-125, 1982.