以圖對為基礎之啟發式演算法，求解動態設施規劃問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：18.188.85.175

姓名

謝祥凡(Hsiang-fan Hsieh) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以圖對為基礎之啟發式演算法，求解動態設施規劃問題
(Solving the Dynamic Facility Layout Problem with graph pair-based heuristics)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

近年來，隨著科技技術日新月異，企業間競爭力不斷增長，公司內廠房佈置顯得特別重要，且會影響特定空間之整體作業效率。許多製造組織因企業環境天性，對部門配置進行週期性調整，因此，設施佈置也應擬訂相關動態設施佈置計劃，以配合不同的生產策略。相較之下，傳統單期設施規劃著重於單一時間之廠房佈置，且未考慮長期性之廠房規劃，以致於廠房將因應需求，對廠房佈置進行設施重置時，額外支出多餘成本及規劃時間。因此，本研究將提出一套動態啟發式演算法，求解動態設施規劃問題，以提供一套考慮多時期之設施佈置方案。而動態指部門位置於下一期之需求產生變動，其需求可能為部門面積改變、部門邊長比例大小、變動部門位移成本、部門間物流量及成本及廠房面積。因此，本研究致力於發展彈性化設施佈置，運用靜態設施規劃問題及圖對為方法基礎，其包括以圖對表示部門間相對位置、混合整數規劃模型及靜態啟發式演算法，以發展一套動態啟發式演算法。

摘要(英)

Recently, competitions among companies have been increased by advanced technology. Therefore, the facility layout of corporation will play an important role in the future and it will have influence on operational efficiency. In the past, traditional facilities planning always focused on the single-period. Because it did not consider the long-term layout planning for the future, it should pay extra cost and time when it need to re-layout. Basically, manufacturing organizations often adjust and vary layout periodically for the business strategy. For example, expanding, shrinking and moving the departments. Dynamic strategy is adjusting design of moving materials, varying space of departments via planning periods, to design and arrange the most efficient facility layout. But it will produce some relocation costs since change the layout from certain period to the next. However, we proposed a heuristic algorithm to minimize both material handling costs and relocation costs. Assuming all the departments are rectangular in shape, varying departments in area, given facility in area and planning period. We operate graph-pair to control the location of departments in layout. Solving the dynamic facility layout by a mixed-integer programming and dynamic heuristic algorithm.

關鍵字(中)

★ 廠房佈置
★ 模擬退火法
★ 混合整數規劃
★ 圖對
★ 動態設施規劃

關鍵字(英)

★ simulated annealing
★ facilities layout planning
★ dynamic facility layout problem

論文目次

目錄
摘要 i
Abstract ii
圖目錄 vi
表目錄 viii
第一章緒論 1
1.1 研究背景及動機 1
1.2 研究目的 2
1.3 研究範圍與假設 2
1.4 論文架構 3
第二章文獻探討 5
2.1 靜態設施規劃問題(SFLP) 6
2.1.1 確切式求解 6
2.1.2 啟發式求解 9
2.2 動態設施規劃問題(DFLP) 11
2.2.1 確切求解方法 12
2.2.2 啟發式方法 15
2.3 設施規劃電腦應用系統 19
第三章運用圖對求解靜態設施規劃問題 20
3.1 本章介紹 20
3.2 SFLP-MIP模型 20
3.3 以圖對表示部門間相對位置 21
3.3.1 迴圈 23
3.3.2 t-edge 23
3.4 圖對之相關演算法 23
3.5 圖對的建構及操作 24
3.5.1 建構初始設施佈置 24
3.5.2 部門交換 24
3.5.3 節線搬移 25
3.6 啟發式演算法 25
第四章運用圖對求解動態設施規劃問題 27
4.1 本章介紹 27
4.2 DFLP之假設 27
4.3 決定部門是否位移 28
4.3.1 部門擴張之位移成本 29
4.3.2 部門縮減之位移成本 30
4.3.3 部門(面積不變)移動之位移成本 31
4.4 DFLP-MIP模型 31
4.5 建構一列設施佈置 33
4.6 動態啟發式演算法 35
第五章實驗數據 37
5.1 測試題目：7個部門，1期 37
5.2測試題目：9個部門，2期 41
5.3測試題目：16個部門，2期 43
第六章結論與建議 46
6.1 結論 46
6.2 未來研究建議 46
參考文獻 47
附錄 A 51
附錄 B 52

參考文獻

參考文獻
1. Armour, G. C., and Buffa, E. S., “A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities,” Management Science, vol. 9, no. 2, pp. 294-309, 1963
2. Balakrishnan, J., and Cheng, C., “Genetic Search and the Dynamic Layout Problem,” Computers & Operations Research, vol. 27, pp. 587-593, 2000
3. Balakrishnan, J., Cheng, C., and Wong, K., “FACOPT: a User Friendly Facility Layout Optimization System,” Computers & Operations Research, vol.30, pp. 1625-1641, 2003
4. Banerjee, P., Montreuil, B., Moodie, C. L., and Kashyap, R. L., “A Modeling of Interactive Facilities Layout Designer Reasoning Using Qualitative Patterns,” International Journal of Production Research, vol. 30, no. 3, pp. 433-453, 1992
5. Baykasoglu, A., Dereli, T., and Sabuncu, I., “An Ant Colony Algorithm for Solving Budget Constrained and Unconstrained Dynamic Facility Layout Problems,” The International Journal of Management Science, vol. 34, pp. 385-396, 2006
6. Baykasoglu, A., and Gindy, N. N.Z., “A Simulated Annealing Algorithm for Dynamic Layout Problem,” Computers & Operations Research, vol. 28, pp. 1403-1426, 2001
7. Bondy, J. A., and Murty, U. S. R., Graph Theory Application, Macmillan Press, 1976
8. Burkard, R. E., and Bonniger, T., “A Heuristic for Quadratic Boolean Programs with Applications to Quadratic Assignment Problems,” European Journal of Operational Research, vol. 13, pp. 374-386, 1983
9. Castillo, I., and Westerlund, T., “An -accurate Model for Optimal Unequal–area Block Layout Design,” Computers & Operations Research, vol. 32, pp. 429-447, 2005
10. Dijkstra, E. W., “A Note on Two Problem in Connection with Graphs,” Numerical Mathematics, vol. 1, pp. 269-271, 1959
11. Dunker, T., Radons, G., and Westkamper, E., “Combining Evolutionary Computation and Dynamic Programming for Solving a Dynamic Facility Layout Problem,” European Journal of Operational Research, vol. 165, pp. 55-69, 2005
12. Foulds, L. R., “LayoutManager: A Microcomputer-based Decision Support System for Facilities Layout,” Decision Support Systems, vol. 20, pp. 199-213, 1997
13. Gambardella, L. M., Taillard, E.D., and Dorigo M., “Ant Colonies for the Quadratic Assignment Problem,” The Journal of the Operational Research Society, vol. 50, no. 2, pp. 167-176, 1999
14. Hillier, F. S., and Connors, M. M., “Quadratic Assignment Problem Algorithms and the Location of Indivisible Facilities,” Management Science, vol. 13, no. 1, pp. 42-57, 1966
15. Kulturel-konak, S., Smith A. E., and Norman B. A., “Bi-objective Facility Expansion and Relayout Considering Monuments,” IIE Transactions, vol. 39, pp. 747-761, 2007
16. Lacksonen, T. A., and Enscore E. E., “Quadratic Assignment Problem for the Dynamic Layout Problem,” International Journal of Production Research, vol. 31, no. 3, 1993
17. Kulturel-konak, S., “Approaches to Uncertainties in Facility Layout Problems: Perspectives at the Beginning of the 21 century,” Journal of Intelligent Manufacturing, vol. 18, pp. 273-284, 2007
18. Kirkpatrick, S., Gelatt, C. D., Jr., and Vecchi, M. P., “Optimization by Simulated Annealing,” Science, vol. 220, pp. 671-680, 1983
19. Koopmans, T. C., and Beckman, M., “Assignment Problems and the Location of Economic Activities,” Econometrica, vol. 25, no. 1, pp. 53-76, 1957
20. Lacksonen, T. A., “Static and Dynamic Layout Problems with Varying Areas,” The Journal of the Operational Research Society, vol. 45, no. 1, pp. 59-69, 1994
21. Lacksonen, T. A., “Preprocessing for Static and Dynamic Facility Layout Problems,” International Journal of Production Research, vol. 35, no. 4, pp. 1095-1106, 1997
22. Lacksonen, T. A., and Hung, C.Y., “Project Scheduling Algorithm for Re-layout Projects,” IIE Transactions, vol. 30, pp. 91-99, 1998
23. Liu, Q., and Meller, R., “A Sequence-pair Representation and MIP-model-based Heuristic for the Facility Layout Problem with Rectangular Department,” IIE Transactions, vol. 39, pp. 377-394, 2007
24. McKendall, A. R. J., Shang, J., and Kuppusamy, S., “Simulated Annealing Heuristic for the Dynamic Facility Layout Problem,” Computers & Operations Research, vol. 33, pp. 2431-2444, 2006
25. Meller, R. D., Narayanan V., and Vance, P. H., “Optimal Facility Design,” Operations Research Letters, vol. 23, 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., “A Modeling Framework for Integrating Layout Design and Flow Network Design,” Proceedings of the 1990 Material Handling Research Colloquium, Hebron, Kentucky, p.p. 43-58, 1990.
28. Montreuil, B., and Venkatadri, U., “Strategic Interpolative Design of Dynamic Manufacturing Systems Layout,” Management Science, vol. 37, no. 6, 1991
29. Murata, H., Fujiyoshi, K., Nakatake S., and Kajitani, Y., “Rectangle Packing-based Module Placement,” IEEE International Conference on Computer-Aided Design, pp. 472-479, 1995
30. Picone, C. J., and Wilhelm, W. E., “A Perturbation Scheme to Improve Hillier’s Solution to the Facilities Layout Problem,” Management Science, vol. 30, no. 10, 1984
31. Rosenblatt, M. J., “The Dynamic of Plant Layout,” Management Science, vol. 32, no. 1, pp. 76-86, 1986
32. Sherali, H. D., Fraticelli, B. M. P., and Meller, R. D., “Enhanced Model Formulations for Optimal Facility Layout,” Operations Research, vol. 51, no. 4, pp. 629-644, 2003
33. Suresh, G., Vindo, V. V., and Sahu, S., “A Genetic Algorithm for Facility Layout,” International Journal of Production Economics, vol. 33, no. 12, pp. 3411-3423, 1993
34. Tate, D. M., and Smith, A. E., “A Genetic Approach to the Quadratic Assignment Problem,” Computers & Operations Research, vol. 22, no. 1, pp. 73-83, 1995
35. Wang, C. T., “Static and Dynamic Facility Layout Problem,” Industrial and Operations Engineering in The University of Michigan, 1999.
36. Yang, T., and Peters, B. A., “Flexible Machine Layout Design for Dynamic and Uncertain Production Environments,” European Journal of Operational Research, vol. 108, no.1, pp. 49 -64 , 1998

指導教授

王啟泰(Chi-tai Wang)

審核日期

2010-7-16

推文