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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：4

、訪客IP：3.139.64.42

姓名

謝佩珊(Pei-shan Hsieh) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以圖對及混合整數規劃模型求解不等面積設施規劃問題
(Using Graph-Pairs and MIP-Models to Solve Unequal Area Facility Layout Problems)

相關論文

★ 半導體化學材料銷售策略分析-以跨國B化工公司為例	★ TFT-LCD CELL製程P檢點燈不良解析流程改善之關聯法則應用
★ 金融風暴時期因應長鞭效應的策略 –以X公司為例	★ 勞動生產力目標訂定之研究-DEA 資料包絡法應用
★ 應用田口方法導入低溫超薄ITO透明導電膜於電容式觸控面板之研究	★ 多階不等效平行機台排程與訂單決策
★ 多準則決策之應用-以雷射半導體產業為例	★ 專案管理模式進行品管圈活動-以半導體機台保養測機流程改善為例
★ 應用e8D降低不合格品之效益分析-以快速消費品製造為例	★ 供應商評選模式之建構-以塑膠射出成型機製造為例
★ 應用協同規劃預測補貨於伺服器備品存貨改善之研究－以Q代工公司為例	★ 船用五金拋光作業之生產規劃
★ 以SCOR模型探討汽車安全輔助系統供應鏈-以A公司採購作業改善為例	★ 研發補助計畫執行成效評估之研究以「工業基礎技術專案計畫」為例
★ 運用生態效益發展永續之耳機產業	★ 失效模式設計審查(DRBFM)之應用-以筆記型電腦為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

自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

論文目次

摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vi
1. Introduction 1
1.1 Background and motivation 1
1.2 Research objective 1
1.3 Thesis organization 2
2. Literature Review 3
2.1 Definitions of model 3
2.2 Using Graph-Pairs as layout representation 7
2.2.1 Circuits and t-Edges in Graph-Pairs 7
2.2.2 Constructing and manipulating graph-pairs (NR/EM) 8
2.3 Exact approaches 8
2.4 Heuristic approaches 9
2.5 Ant colony optimization 9
2.5.1 Ant variant 10
2.5.2 Max-Min ant system 11
2.5.3 Application of ACO 11
3. Using Graph-Pairs and MIP-Models with hybrid Simulated Annealing and Ant Colony Optimization to Solve UA-FLPs 13
3.1 Introductions 13
3.2 Using pheromone to generate initial layout and improvement layout 14
3.3 Improvement procedure 18
3.4 Illustrate the process of algorithm 19
3.4.1 Graph-pairs and layout construction 19
3.4.2 Graph-pairs manipulation with NR/EM 20
3.4.3 A hybrid SA and ACO alforithm 21
4. Numerical experiments and results 26
5. Conclusions 29
Appendices 30
References 31

參考文獻

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.
6. Bullnheimer, B., Sreauss, H. R., 1999. A new rank-based version of the ant system: a computational study. Central European Journal for Operations Research and Economics, 7(1), 25-38.
7. Costa, D., Hertz, A., 1997. Ants can color graphs. Journal of the Operational Research Society, 48, 295-305.
8. den Besten, M.L., Stützle, T., and Dorigo,M., 2000. Ant colony optimization for the total weighted tardiness problem. In: Schoenauer, M. et al., editors. Proceedings of PPSN-VI, sixth international conference on parallel problem solving from nature. Lecture Notes in Computer Science, 1917, 611-620.
9. Dijkstra, E. W., 1959. A note on two problems in connection with graphs. Numerical Mathematics, 1, 269-271.
10. Dorigo, M., 1992. Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano.
11. Dorigo, M., Blum, C., 2005. Ant colony optimization theory: A survey. Theoretical Computer Science, 344, 243-278.
12. Dorigo, M., Gambardella, L. M., 1997. Ant colony system: A Cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
13. Dorigo, M., Maniezzo, V., and Colorni, A., 1991. Positive feedback as a search strategy. Technical Report, 91-016.
14. Dorigo, M., Maniezzo, V., and Colorni, A., 1996. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on System, Management, and Cybernetics-Part B: Cybernetics, 26(1), 29-41.
15. Gagné, C., Price, W.L., and Gravel, M., 2002. Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence dependent setup times. Journal of the Operational Research Society, 53, 895-906.
16. Gambardella, L.M., Taillard, É.D., and Agazzi, G.1999. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne, D., Dorigo, M., Glover, F., editors. New ideas in optimization. London: McGraw-Hill, 63-76.
17. Hani, Y. Amodeo, L., Yalaoui, F., and Chen, H., 2007. Ant colony optimization for solving an industrial layout problem. European Journal of Operational Research, 183, 633-642.
18. Kao, Y., Cheng K., 2006. An ACO-based clustering algorithm. Lecture Notes in Computer Science, 4150, 340-347.
19. Komarudin, and Wong, K. Y., 2010. Applying ant system for solving unequal area facility layout problem. European Journal of Operational Research, 202, 730-746.
20. Koopmans, T. C., and Beckman, M., 1957. Assignment problems and the location of economic activities. Econometrica, 25, 53-76.
21. Liu, Q., Meller, R. D., 2007. A sequence-pair representation and MIP-model-based heuristic for the facility layout problem with rectangular department. IIE Transctions, 39, 377-394.
22. Maniezzo, V., 1999. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal on Computing, 11, 358-369.
23. Maniezzo, V., Colorni, A., Dorigo, M., 1994. The ant system applied to the quadratic assignment problem. Technical report IRIDIA, Universite′ Libre de Bruxelles, 94-128.
24. Meller, R. D., Chen W., and Sherali, H. D., 2007. Applying the sequence-pair representation to optimal facility layout designs. Operations Research Letters, 35(5), 651-659.
25. Meller, R. D., Narayanan, V., and Vance, P. H., 1999. Optimal facility layout design. Operations Research Letters, 23(3-5), 117-127.
26. Montreuil, B., 1990. A modelling framework for integrating layout design and flow network design. Proceedings of the 1990 Material Handling Research Colloquium, 43-58.
27. Reimann, M., Doerner, K., and Hartl, R.F., 2004. D-ants: savings based ants divide and conquer the vehicle routing problems. Computers & Operations Research, 31(4), 563-591.
28. Sherali, H. D., Fraticelli, B. M. P., and Meller, R. D., 2003. Enhance model formulations for optimal facility layout. Operations Research, 51(4), 629-644.
29. Socha, K., Sampels, M.,and Manfrin, M., 2003. Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Raidl G. et al., editors. Applications of evolutionary computing, proceedings of EvoWorkshops, 2611, 334-345.
30. Stützle, T., 1998. An ant approach to the flow shop problem. In: Proceedings of the 6th european congress on intelligent techniques & soft computing (EUFIT’98), 1560-1564.
31. Stützle, T., Dorigo, M., 1999. ACO algorithm for the quadratic assignment problem. Technical report IRIDIA, Universite′Libre de Bruxelles, 99–102.
32. Stützle, T., Hoors, H., 1997. Max-Min ant system and local search for the traveling salesman problem. IEEE Evolution Computation Conf., 309-314.
33. Stützle, T., Hoos, H., 2000. MAX-MIN ant system. Future Generation Computer Systems, 16, 889-914.
34. Tate, D. M., Smith, A. E., 1995. Unequal-area facility layout by genetic search. IIE Transactions, 27, 465-472.
35. Tong, X., 1991. SECOT: A sequential construction technique for facility design. PhD thesis, University of Pittsburgh.
36. van Camp, D.J., 1989. A nonlinear optimization approach for solving facility layout problem. PhD thesis, University of Toronto.
37. van Camp, D.J., Carter, M.W., Vannelli, A., 1992. A nonlinear optimization approach for solving facility layout problems. European Journal of Operational Research, 57 (2), 174-189.
38. Wang, C. T., 1999. Static and Dynamic Facility Layout Problem. PhD thesis, University of Michigan.

指導教授

王啟泰(Chi-tai Wang)

審核日期

2011-7-20

推文