跳到主要內容

臺灣博碩士論文加值系統

(216.73.216.35) 您好!臺灣時間:2025/12/17 15:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:趙文琦
研究生(外文):Wen-Chi Chao
論文名稱:利用改良式禁忌搜尋演算法求解設施規劃問題
論文名稱(外文):Using improved tabu search for the facility layout problem
指導教授:梁永魯
指導教授(外文):Lou Y.Liang
學位類別:碩士
校院名稱:立德管理學院
系所名稱:應用資訊研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:92
中文關鍵詞:配置二次指派問題最佳化禁忌搜尋法設施規劃問題
外文關鍵詞:quadratic assignment problemfacility layout problemtabu searchlayoutcombinatorial optimization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:341
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
設施規劃問題係屬於人工智慧領域之決策與設計最佳化之應用,為二次指派問題之一支,其問題旨在尋求一可行的設施配置方法,來滿足配置需求最佳化之目的。由於二次指派問題已被證明屬於NP-Complete,若使用窮舉法來找尋最佳解,因其求解範圍過於寬廣,當搜尋空間達到一定程度以上時,將嚴重降低其最佳化效率。因此,釵h人工智慧領域的相關研究均提出使用啟發式演算法來求解二次指派問題,諸如:基因演算法、蟻群演算法、禁忌搜尋演算法、模擬退火法等,來求解二次指派問題;本論文將針對傳統禁忌搜尋演算法,提出一個改良式的搜尋法則,用於求解二次指派問題中的設施規劃問題,並以兩個案例作為實驗數據來源,由實驗結果證明本研究所提出之改良法則,的確優於原來使用其他最佳化方法所得的規劃結果。
The facility layout problem is a part of the application in the artificial intelligence. It is belong to the combinatorial optimization and quadratic assignment problem. For many artificial intelligence tools, the tabu search algorithm is widely applied to a lot of combinatorial optimization problems. In this research, an improved tabu search algorithm is developed to solve a NP-complete problem in the facility layout problem. The approach on the two facilities layout problems is examined. The first one is a construction site layout problem, and the second one is a hospital facility layout problem. In order to get better layout result, this research has tried the different setting in this algorithm by altering the values of parameters. This research can provide a good algorithm to solve the quadratic assignment problem in facility layout arrangement.
中文摘要.......................i
英文摘要.......................ii
誌謝.......................iii
目錄.......................iv
表目錄.......................vi
圖目錄.......................vii
第壹章 緒論.......................1
第一節 研究背景.......................1
第二節 研究動機.......................3
第三節 研究目的.......................4
第四節 章節簡介.......................5
第五節 論文架構流程圖.......................6
第貳章 文獻探討.......................7
第一節 設施規劃相關文獻回顧.......................7
第二節 求解設施規劃問題.......................14
第三節 小結.......................20
第參章 設施規劃問題.......................21
第一節 指派問題.......................21
第二節 案例研究.......................23
第三節 退火類神經網路.......................32
第四節 小結.......................33
第肆章 研究方法.......................34
第一節 禁忌演算法之基本概念.......................34
第二節 禁忌搜尋法六大基本元素.......................35
第三節 改良式禁忌搜尋演算法.......................44
第四節 小結.......................52
第伍章 實驗結果與分析.......................54
第一節 實作平台.......................54
第二節 實驗設定.......................54
第三節 實驗結果與分析.......................56
第四節 小結.......................83
第陸章 結論與未來建議.......................84
第一節 結論.......................84
第二節 建議與後續研究.......................85
參考文獻.......................86
Karray, F., Zaneldin, E., Hegazy, T., Shabeeb, A., & Elbeltagi, E.(2000), “Computational Intelligence Tools for Solving the Facilities Layout PlanningProblem.”, Proceedings of the American Control Conference, Chicago, Illinois.

Dickey, J. W. & Hopkins, J. W. (1972), “Campus building arrangement using TOPAZ”, Transportation Research, 6:59–68.

Eschermann, B. & Wunderlich, H.-J. (1990) , “Optimized Synthesis of Self-Testable Finite State Machines”, Proceedings of 20th International Symposium. Fault- Tolerant Computing, Newcastle Upon Tyne, UK.

Yeh, I. C. (2006), “Architectural layout optimization using annealed neural network”, Automation in Construction, 15(4):531-539

Sahni, S. & Gonzalez, T. (1976), “P-complete approximation problems”, Journal of the Association for Computing Machinery (JACM), 23(3):555-565.

Lim, M. H., Yuan, Y. & Omatu, S. (2000), “Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem”, Computational Optimization and Applications, 15(3):249–268.

Tate, D. M. & Smith, A. E. (1995), “A genetic approach to the quadratic assignment problem”, Computers & Operations Research, 22(1): 73–83.

Gambardella, L. M. & Taillard, E. & M. Dorigo (1999), “Ant colonies for the quadratic assignment problem”, Journal of the Operational Research Society, 50(2):167–176.

Bolte, A. & Thonemann, U. W. (1996), “Optimizing simulated annealing schedules with genetic programming”, European Journal of Operational Research, 92(2): 402–416.

Connolly, D. T. (1990), “An improved annealing scheme for the QAP”, European Journal of Operational Research, 46(1): 93–100.

Daskin, M. S. (1983), “A Maximum Expected Covering Location Model --Formulation, Properties and Heuristic Solution”, Transportation Science, 17(l): 48-69.

Daskin, M. S. (1983), “Logistics: An Overview of the State of the Art and Perspectives on Future Research”, Transportation Research, 19(5): 383-404.

Erlenkotter, D. (1997), “Facility Location with Price-Sensitive Demands: Private, Public And Quasi-Public”, Management Science, 24(4): 378-386.

Drezner, Z. & Wesolowsky, G. O. (1991), “Facility Location When Demand is Time Dependent”, Naval Research Logistics, 38: 763-777.

Hotelling, H. (1929), “Stability in Competition”, Economic Journal,39(153): 41-57.

Hakimi, S. L. (1964), “Optimal Location of Switching Centers and the Absolute Centers and Medians of a Graph”, Operations Research, 12(3): 450-459

Current, J., Min, H. & Schilling, D. (1990), “Multiobjective Analysis of Facility Locations”. European Journal of Operation Research, 49(3): 295-307.

Moon, I. D., & Chaudhry, S. S. (1984), “An Analysis of Network Location Problems with Distance Constraints”, Management Science, 30(3): 290-307.

Church, R. J. (1984), “The Planar Maximal Covering Location Problem”, Journal of Regional Science, 24(2):185-201.

Halpern, J. (1978), “Finding Minimal Center-Median Convex Combination”, Management Science, 24(5): 535-544.

Handler, G. Y. (1976), “Medi-Centers of a Tree”, Transportation Science, 19(3): 246-260.

Leonardi G. (1981), “A unifying framework for public facility location problems -- part 1: A critical overview and some unsolved problems”, Environment and Planning A, 13(8) 1001-1028.

Revelle, C., Marks, D., & Lieman J. C. (1970), “An Analysis of Private and Public Sector Location Model”, Management Science, 16(11): 692-705.

Koopmans, T. & Beckmann, M. (1957), “Assignment problems and the location of economic activities”, Econometrical, 25(1): 53–76.

Kazuhiro, T. Sunil, B., & Yoshiyasu, T. (1995), “A neural network approach to facility layout problems”, European Journal of Operational Research, 89(3): 556-563.

Seppanen, J. J., & Moore, J. M.(1970), “Facilities planning with graph theory”, Management Science, 17(4): 242-253.

Foulds, L. R. & Robinson, D. F. (1978), “Graph theoretic heuristics for the plant layout problem”, International Journal of Production Research, 16(1): 27-37.

Sha, D. Y. & Shih, M.(1992) , “Network algorithm for designing of AGV route system” , Proceedings of the Second International Conference on Automation Technology, Taipei, Taiwan.

Wascher, G., & Merker, J. (1997), “A comparative evaluation of heuristics for the adjacency problem in facility layout planning”, International Journal of Production Research, 35(2): 447-466.

Love, R.F., & Wong, J.Y. (1976), “Solving quadratic assignment problem with rectilinear distance and integer programming”, Naval Research Logistics Quarterly, 23: 623-627.

Montreuil, B. (1991), “A modeling framework for integrating layout design and flow network design”, Proceedings of the Material Handling Research Colloquium, Hebron, Kentucky.

Drezner, Z. (1980), “DISCON: A New Method for the Layout Problem”, Operations Research, 28(6): 1375-1384.

Kusiak, A. & Heragu, S. S. (1987), “The Facility Layout Problem”, European Journal of Operational Research, 29(3): 229-251.

Foulds, L. R. (1983), “Techniques for facilities layout: Deciding which pairs of activities should adjacent”, Management Science. 29(2):1414-1426.

Meketon, M. S. (1987), “Optimization in Simulation : A Survey of Recent Results”, Proceedings of the 1987 Winter Simulation Conference.

Grobelny, J. (1987), “The fuzzy approach to facilities layout problems”, Fuzzy Sets and Systems, 23(2): 175-190.

Evans, G. W., Wilhelm, M. R., & Karwowski, W. (1987), “A layout design heuristic employing the theory of fuzzy sets”, International Journal of Production Research, 25(10): 1431-1450.

Langevin, A., Montreuil, B. & Riopel, D.(1994), “Spine layout design”, International Journal of. Production Research, 32(2): 429-442.

Peters, B. A. & Yang, T. H.(1997), “Integrated facility layout and material handling system design in semiconductor fabrication facilities”, IEEE Transactions on Semiconductor Manufacturing,10(3):360-369.

Heragu S. S. & Alfa A. S.(1992), “Experimental analysis of simulated annealing based algorithms for the layout problem”, European Journal of Operational Research, 57(2):190-202.

Huang, Chikong(1993), “A Simulated Annealing Procedure for Single Closed Loop Layout Problems in Automatic Manufacturing Systems”, Proceedings of the Chinese Institute of Industrial Engineers National Conference 1993, Tainan, Taiwan.

Glover, F. (1989), “Tabu search: Part I”, ORSA Journal on Computing, 1(3): 190–206.

Glover, F. (1990), “Tabu search: Part II”, ORSA Journal on Computing, 2(1): 4–32.

Ting, J. H. & Tanchoco, J. M. A. (2001), “Optimal Bidirectional Spine Layout for Overhead Material Handling Systems”, IEEE Transactions on Semiconductor Manufacturing, 14(1): 57-64.

Dickey, J. W. & Hopkins, J. W. (1972), “Campus building arrangement using TOPAZ”, Transportation Research, 6: 59-68.

Richard, L.C.(1990), “The Regionally Constrained P-Median Problem”, Geography Analysis, 9: 23-32.

Labbé, M. (1985), “Outcomes of Voting and Planning in Single Facility Location Problems”, European Journal of Operation Research, 20(3): 299-313.

Vohra, R. V. (1989), “Distance Weighted Voting and A Single Facility Location Problem”, European Journal of Operation Research, 41(3): 314-320.

Hansen, P., & David, S. (1989), “The Capacitated Maximal Covering Location Problem with Backup Service,” Annals of Operations Research, 18(1-4) 141-154.

Rajan, B., & Narasimha, R. M. (1990), “Covering-Location Models for Emergency Situations That Require Multiple Response Units”, Management Science, 36(1): 16-23.

Wesolowsky, G. O. & Truscott, W. G. (1975), “The multiperiod location-allocation problem with relocation of facilities”, Management Science, 22(1): 57-65.

Wesolowsky, G. O. (1973), “Dynamic Facility Location”, Management Science, 19(11): 1241-1247.

Yeh, I. C. (1995), “Construction-Site Layout Using Annealed Neural Network”, Journal of Computing Civil Engineering, 9(3): 201-208

Mayer, D. G., Belward, J. A. & Burrage, K. (1998), “Tabu Search Not an optimal Choice for Models of Agricultural Systems”, Agricultural Systems, 58(2): 243-251.

Misevičius, A. (2005), “A tabu search algorithm for the quadratic assignment problem”, Computational Optimization and Applications, 30(1): 95-111.

馮正民(1979),都巿計劃中之交通運輸規劃方法,台灣省住宅及都巿發展局巿鄉規劃處理研究報告

解鴻年(1990),臺灣地區科技廠商區位特性研究,國立成奶j學都市計畫研究所碩士論文。

施鵬程(1980),以區位模式輔助郵局區位決策分析之研究-以嘉義市為例,國立交通大學交通運輸研究所碩士論文。

蕭再安(1992),設施區位問題多目標決策之研究,國立交通大學交通運輸研究所博士論文。

柯于璋(1991),公共設施設置區位之研究-以臺北市有線電視經營分區之劃設為例,國立中興大學公共政策研究所碩士論文。

梁豐裕(1994),都市行政中心區位選定之研究─以桃園縣蘆竹鄉為例,淡江大學建築研究所碩士論文。

劉建志和沙永傑,製造設施規劃之並行式啟發法」,中華民國工業工程學會八十五年度年會論文集,530~535
頁,中華民國台北市。

沙永傑(1996),應用模糊數學方法於設施佈置之研究,中華民國工業工程學會八十五年度年會論文集(上冊), pp. A44-A51。

廖晉廷(2001),動態停車場區位選擇之研究,朝陽科技大學建築及都市設計研究所碩士論文。

古美玉 (1999),應用模擬退火法於脊椎式設施佈置之研究─以半導體廠為例,元智大學工業工程研究所碩士論文。

彭國銘 (2001),晶圓製造廠設施規劃改善之研究,中原大學工業工程研究所碩士論文。

戴瑞德(2002),晶圓製造廠系統化設施規劃,中原大學工業工程研究所碩士論文。

陳昭吉(2003),應用遺傳基因演算法於晶圓製造廠之設施佈置問題,元智大學工業工程與管理研究所碩士論文。

魏士淵(2005),汽車貨運業線上型車輛派遣模式之研究,中華大學科技管理研究所,碩士論文。

林佳宜(2003),印刷電路板組裝高速機之多料架指派問題研究,大葉大學工業工程學系碩士論文。

周志隆(2003),以螞蟻演算法求解蜂巢式行動通訊系統之頻率指派問題,中原大學工業工程研究所碩士論文。

黃碧玉(2001),泛用機上印刷電路板插件順序問題之研究─以CNC機器為例,元智大學工業工程與管理學系碩士論文。

張企宏(2003),貨櫃碼頭分派問題之研究,元智大學工業工程與管理學系碩士論文。

李仁鐘(2001),以族群為基礎之啟發式演算法應用於武器對目標指派問題,國立台灣科技大學電機工程系博士論文。

張壯營(1997),塔布搜尋法在流物中心品項儲位指派問題之應用,國立台灣科技大學管理技術研究所碩士論文。

洪英傑(2001),以基因演算法研究電腦組裝工廠之產品及人員指派問題,國立成奶j學製造工程研究所碩士論文。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top