以圖對及混合整數規劃模型求解不等面積設施規劃問題

Using Graph-Pairs and MIP-Models to Solve Unequal Area Facility Layout Problems

謝佩珊(Pei-shan Hsieh)

指導教授 ： 王啟泰

國立中央大學/管理學院/工業管理研究所/碩士(2011年)

摘要

自Koopmans與Beckmann提出設施規劃問題至今已五十多年，在業界及學術界均扮演重要角色。於業界，有效率的物料搬運及設施規劃，可降低企業的總生產成本；於學術界，許多學者於近幾年使用不同啟發式方法求解此困難之設施規劃問題。由此可知，設施規劃問題對於生產活動是非常重要的。

許多學者已發展啟發式演算法求解不等面積設施規劃問題，例如，模擬退火演算法、基因演算法、螞蟻演算法等。本研究以Montreuil (1990)提出的混合整數規劃模型為基礎，以圖對表示模型中的二元變數值，並發展一混和模擬退火演算法與螞蟻演算法以求解不等面積設施規劃問題；期盼此研究方法能獲得相對最佳解，即物流成本較小解。

關鍵字

混合整數規劃 ； 螞蟻演算法 ； 模擬退火演算法 ； 設施規劃問題 ； 圖對

並列摘要

Koopmans and Beckmann (1957) have proposed facility layout planning problem for 50 years and it played an important role in both academia and industry. For the industry, the more efficient facilities layout planning, the lower material handling of total production cost. For the academics, many researchers still use different heuristic method and try to solve the difficult facility layout problems recently. Therefore, the facilities layout planning for the production issue is very important.

Many researchers have developed heuristic algorithm to help solving unequal area facility layout problems (UA-FLPs); for example, simulated annealing algorithms (SA), genetic algorithms, ant colony optimization (ACO), and so on. This research propose a hybrid of SA and ACO which combines graph-pairs to represent the value of the binary variables with Montreuil’s (1990) mix-integer programming (MIP) models to solve UA-FLPs. We hope to obtain better solutions via SA and ACO procedures, that is, generate lower flow and material costs.

並列關鍵字

graph-pairs ； mix integer programming ； ant colony optimization ； simulated annealing ； facility layout problems

參考文獻

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

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

3. Blum, C., 2005. Beam-ACO-Hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research, 32(6), 1565-1591.

4. Blum, C., 2005. Ant colony optimization: introduction and recent trends. Physics of Live Reviews, 2(4), 353-373.

5. Bozer, Y.A., Wang, C. T., 2011. A Graph-Pair Representation and MIP-Model-Based Heuristic for the Unequal-Area Facility Layout Problem. Working paper.