以圖對為基礎之啟發式演算法，探討實際設施規劃問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：51

、訪客IP：3.139.86.160

姓名

林義彬(Yi-bin Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以圖對為基礎之啟發式演算法，探討實際設施規劃問題
(Exploring practical facility layout planning with a graph pair-based heuristic)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

自Koopmans與Beckmann提出設施規劃問題已五十多年。在業界以及學術界均受到重視：在業界，有效率的物料搬運及設施規劃，可降低企業10%至30%的總生產成本，由此可知，設施規劃對於生產活動之重要性可見一般；在學術界，設施規劃問題求解困難，因此，許多在作業研究及管理科學領域的研究人員對此問題進行廣泛的探討。
設施規劃為NP-complete問題，許多學者已發展相關啟發式演算法協助求解，例如，模擬退火、基因、螞蟻等。本研究發展模擬退火演算法來求解靜態設施規劃問題，以Montreuil在1990年提出的模型為基礎，並以圖對來表示模型中的二元變數值，將其轉換為線性模型。先以初始的廠房佈置為起始解，經過模擬退火演算法的程序來獲得相對最佳解，即物流成本較小。在求解相對最佳解同時，本研究亦考慮設施規劃者需求；並針對使用者的需求，開發相關的功能來運用，其功能包含：改善目前廠房佈置。本研究亦提出兩種求解動態設施規劃問題之方法。最終目的為發展一套實用化的設施規劃系統雛型以方便設施規劃人員使用。

摘要(英)

Since Koopmans and Beckmann proposed facility layout planning problem has been 50 years. It has been considered very important in both academia and industry. In the industry, efficient material handling and facilities layout planning could reduce the total production cost from 10 to 30 percent. Therefore, the facilities layout planning for the production is very important; in academics, facing the solving difficulties of the facilities layout planning problem, many researchers in the field of operations research and management science have extensively discussed the issue.
Facilities layout planning is a NP-complete problem. Many researchers have developed heuristic algorithms to help solving this problem. For example, simulated annealing algorithms, genetic algorithms, ants algorithms and so on. This study develops static simulated annealing algorithm to solve facilities layout planning. Based on the Montreuil’s model (1990), we will use graph-pair to represent the value of the binary variables, and convert it to the linear model. First, we use the original layout planning to be the initial solution, and via simulated annealing procedures to obtain the better solution, that is, less flow costs. With solving the better solution, this study also considers the demand for facility layout planners, focuses on the needs of users, and develops the corresponding functions. Its features include: improving the facility layout. This study also proposed two methods of solving the dynamic facility layout problem. Ultimately, the objective is to develop a practical prototype of the facility planning system.

關鍵字(中)

★ 圖對
★ 設施規劃系統
★ 混合整數規劃
★ 模擬退火演算法
★ 設施規劃問題

關鍵字(英)

★ facility layout system
★ mix integer programming
★ simulated annealing algorithm
★ facility layout problems
★ graph-pairs

論文目次

摘　要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vi
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與假設 2
1.4 研究架構 3
第二章文獻探討 6
2.1 最佳求解SFLP 6
2.1.1 二元指派問題 6
2.1.2 混和整數規劃 7
2.2 近似求解SFLP 11
2.2.1 混和整數規劃 11
2.2.2 啟發式演算法 12
2.2.3 大規模啟發式演算法(Meta heuristic algorithms) 13
2.3 最佳求解DFLP 14
2.4 近似求解DFLP 15
2.5 多樓層設施規劃問題 16
2.5.1 MULTIPLE 17
2.5.2 SABLE 18
2.5.3 STAGES 18
第三章運用圖對求解靜態設施規劃問題 19
3.1 SFLP基本模型 19
3.2 使用圖對表示部門相對位置 20
3.2.1 迴圈 22
3.2.2 遞移邊線 22
3.3 圖對相關演算法 23
3.4 建構圖對與操作圖對 23
3.4.1 建構初始廠房佈置 23
3.4.2 部門交換 24
3.4.3 邊線搬移 25
3.5 模擬退火演算法 26
3.6 實驗數據 29
第四章運用圖對求解其他廠房佈置問題 34
4.1 改善目前廠房佈置 34
4.2 實驗數據 35
第五章運用圖對求解動態設施規劃問題 37
5.1 以單一圖對產生每期廠房佈置 37
5.2 於每期產生相對應之圖對求解 39
第六章結論與未來研究 41
6.1 結論 41
6.2 未來研究 41
參考文獻 43

參考文獻

1. Armour, G. C., and Buffa, E. S., “A Heuristic Algorithm and Simulation Approach to the Relative Location of Facilities,” Management Science, vol. 9, no. 2, pp. 294-309, 1963.
2. Bartholdi, J. J., and Platzman, L. K., “An O(n log n) Planar Traveling Salesman Heuristic Based on Spacefilling Curves,” Operations Research Letters, vol. 1, no. 4, pp. 121-125, 1982.
3. Benders, J. F., “Partitioning Procedures for Solving Mixed Variables Programming Problems,” Numerical Mathematics, vol. 4, pp. 238-252, 1962.
4. Bondy, J.A., and Murty, U.S.R., Graph Theory with Applications, Macmillan Press, 1976.
5. Bozer, Y. A., and Meller, R. D., “An Improvement-type Layout Algorithm for Single and Multiple-floor Facilities,” Management Science, vol.40, no. 7, pp. 918-932, 1994.
6. Castillo, I., Westerlund, J., Emet, S., Westerlund, T., “Optimization of Block Layout Design Problems with Unequal Areas: A comparison of MILP and MINLP Optimization Methods,” Computers and Chemical Engineering, vol. 30, pp. 54-69, 2005.
7. CPLEX Optimization, Inc., CPLEX9.1, Incline Village, Nevada, 2005.
8. Dijkstra, E. W., “A Note on Two Problems in Connection with Graphs,” Numerical Mathematics, vol. 1, pp. 269-271, 1959.
9. Foulds, L. R., “Techniques for Facilities Layout: Deciding Which Pairs of Activities Should Be Adjacent,” Management Science, vol. 29, no.12, pp. 1414-1426, 1983.
10. Gau, K. Y., and Meller, R. D., “An Iterative Facility Layout Algorithm,” International Journal of Production Research, vol. 37, no. 16, pp. 3739-3758, 1999.
11. Geoffrion, A. M., “Generalized Benders Decomposition,” Journal of Optimization Theory Applications, vol. 10, pp. 237-260, 1972.
12. Gilmore, P.C., “Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem,” Journal of the Society for Industrial and Applied Mathematics, vol. 10, pp. 305-313, 1962.
13. Hassan, M. M. D., and Hogg, G. L., “A Review of Graph Theory Applications to the Facilities Layout Problem,” Omega, vol. 15, no. 4, pp. 291-300, 1987.
14. Holland, J. H., “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, MI, 1975.
15. Kamoun, M., and Yano, C. A., “Facility Layout to Support Just in Time,” Transportation Science, vol. 30, no.4, pp. 315-329, 1996.
16. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983.
17. Komarudin, and Wong, K. Y., “Applying Ant System for solving Unequal Area Facility Layout Problem,” European Journal of Operation Research, vol. 202, pp. 730-746, 2010.
18. Koopmans, T. C., and Beckman, M., “Assignment Problems and the Location of Economic Activities,” Econometrica, vol. 25, pp. 53-76, 1957.
19. Lacksonen, T. A., “Static and Dynamic Layout Problems with Varying Areas,” Journal of the Operational Research Society, vol. 45, pp. 59-69, 1994.
20. Lacksonen, T. A., and Enscore, E. E., Jr., “Quadratic Assignment Algorithms for the Dynamic Layout Problem,” International Journal of Production Research, vol. 31, no. 3, pp. 503-517, 1993.
21. Liu, Q., and Meller, R. D., “A Sequence-pair Representation and MIP Model Based Heuristic for the Facility Layout Problem with Rectangular Departments,” IIE Transcations, vol. 39, no. 4, pp. 377-394, 2007.
22. Meller, R. D., and Bozer, Y. A., “A New Simulated Annealing Algorithm for the Facility Layout Problem,” International Journal of Production Research, vol. 34, no. 6, pp. 1675-1692, 1996.
23. Meller, R. D., and Bozer, Y. A., “Alternative Approach to Solve the Multi-floor Facility Layout Problem,” Technical report, to appear in the Journal of Manufacturing Systems, January 1996.
24. Meller, R. D., and Gau, K. Y., “The Facility Layout Problem,” Journal of Manufacturing Systems, vol. 15, no. 5, 1996.
25. Meller, R. D., Narayanan, V., and Vance P. H., “Optimal Facility Layout Design,” Operation Research Letters, pp. 117-127, 1999.
26. Meller, R. D., Chen, W., and Sherali H. D., “Applying the Sequence-pair Representation to Optimal Facility Layout Designs,” Operations Research Letters, vol. 35, pp. 651-659, 2007.
27. Montreuil, B., and Ratliff, H. D., “Utilizing Cut Tree as Design Skeletons for Facility Layout,” IIE Transactions, vol. 21, no. 2, pp. 136-143, 1989.
28. Montreuil, B., “A Modelling Framework for Integrating Layout Design and Flow Network Design,” Proceedings of the 1990 Material Handling Research Colloquium, Hebron, Kentucky, pp. 43-58, 1990.
29. Moore, J. M., “Computer Aided Facilities Design: An International Survey,” International Journal of Production Research, vol. 25, no. 1, pp. 3-15, 1974.
30. Muther, R., Systematic Layout Planning, 2nd edition, Cahners Books, Boston, MA, 1973.
31. Rosenblatt, M. J., “The Dynamics of Plant Layout,” Management Science, vol. 32, no. 1, pp. 76-86, 1986.
32. Seehof, J. M., and Evans, W. O., “Automated Layout Design Program,” Journal of Industrial Engineering, vol. 18, pp. 690-695, 1967.
33. Tate, D. M., Smith, A. E., “A Genetic Approach to the Quadratic Assignment Problem,” Computers & OR, vol. 22, no. 1, pp. 73-83, 1995.
34. Tompkins, J. A., White, J. A., Bozer, Y. A., Frazelle, E. H., Tanchoco, J. M. A., and Trevino, J., “Facilities Planning 2nd edition,” John Wiley & Son, Inc., New York, 1996.
35. Wang, C. T., “Static and Dynamic Facility Layout Problem,” Industrial and Operations Engineering in The University of Michigan, 1999.
36. Wang, M. J., Hu, M. H., and Ku, M. H., “A Solution to the Unequal Area Facilities Layout Problem by Genetic Algorithm,” Computer in Industry, vol. 56, no. 2, pp. 207-220, 2005.

指導教授

王啟泰(Chi-tai Wang)

審核日期

2010-7-12

推文