進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-0408201615305600
論文名稱(中文) 雙向線性單排佈置之圖型論求解方法發展-考慮總物料搬運成本
論文名稱(英文) A Cut-Based Heuristic for Solving Bidirectional Single-Row Layout Problem
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 陳佳君
研究生(英文) Chia-Chun Chen
學號 R36034163
學位類別 碩士
語文別 中文
論文頁數 76頁
口試委員 指導教授-李賢得
口試委員-利德江
口試委員-王清正
口試委員-林耀三
中文關鍵字 機器佈置  雙向線性單排佈置  定址網路  網路切割法 
英文關鍵字 machine layout  bidirectional single row layout  locale network  cut approach 
學科別分類
中文摘要   本研究探討雙向線性單排機器佈置問題,其中輸入站與輸出站分別位於線性佈置之最前端與最末端,每一台機器即為一個加工站,物料搬運系統在不同機器間進行順向及逆向之工件運送,依據加工順序,產品由輸入站進入系統,物料搬運機具將工件依序運送至各個機器加工站停留並進行加工,待產品完成所有加工程序後再經由輸出站離開系統。本研究即在探討如何將所有機器安排於此一線性單排佈置環境中,使得總物料搬運成本最小。
  本研究針對上述線性單排佈置問題建構數學規劃模式,依據順向搬運及逆向搬運之特性,當逆向單位流量單位距離運送成本大於或等於順向單位流量單位距離運送成本時,可證明最小化總物料搬運成本與最小化總逆流搬運成本所求得之最佳佈置方案相同,並將等距之線性佈置問題轉換為對等網路問題,發現總物料搬運成本相當於網路圖型中所有分段切割值之總和,而在對應之定址網路中,最小切割值即為此佈置下之最小總逆向單位距離搬運成本。
  根據上述特性,本論文發展一計算複雜度為O(n^4)之兩階段啟發式演算法,其先藉由網路切割法求得初始解,再進行改善程序,以求得等距線性單排佈置問題之近似最佳解。依據實驗結果,發現本啟發式演算法求得之佈置解其總物料搬運成本與精確最佳解之總物料搬運成本,其平均偏差為0.56%;在求解效率上,本解法之求解時間會隨著機器個數及流量矩陣密度增加而增加,但仍可在低次多項式函數內,其平均時間維持於1秒內,相對而言,數學規劃軟體Gurobi之求解時間則會隨機器個數增加呈指數成長,故整體而言,本演算法在求解品質與求解效率上均表現良好。
英文摘要 A bidirectional single-row machine layout problem is investigated in this thesis. Part enters the system from the input station which is located at one end of the layout, traverses to some workstation based on routing sequence, and leaves the output station at the other end. The objective is to determine the optimal layout sequence of machines along the linear layout so as to minimize the total material handling cost.
Both non-equidistant and equidistant linear layout problems are formulated as mixed integer programming models. It can be shown that the equidistant linear layout problem can be transformed into a locale network problem by graph theory. In addition, we show that minimization of the total material handling cost is equivalent to minimization of the total backtracking cost. A polynomial time Ο(n^4) cut-based heuristic is developed, where n is the number of machines in the layout problem. The computational study has demonstrated that the proposed heuristic is efficient and effective. The average cost deviation is less than 0.6%, when the approximate solution is compared with that in the integer programming model.
論文目次 摘要 I
Extended Abstract II
誌謝 VI
表目錄 IX
圖目錄 X
第一章 緒論 1
1.1研究背景 1
1.2研究動機 1
1.3研究目的 2
1.4研究架構與流程 2
1.5研究成果與發現 4
第二章 文獻回顧 5
2.1傳統設施佈置數學模式與解法發展 5
2.2 機器佈置問題 8
2.3線性單排設施佈置模式與解法發展 10
2.3.1 精確解法 10
2.3.2 啟發式演算法 11
2.3.3 萬用啟發式演算法 13
第三章 線性單排佈置數學模式與理論性質 17
3.1 雙向線性單排佈置問題與數學模式 17
3.2 理論特性之發現 23
3.3 對等網路轉換 28
第四章 啟發式演算法發展與演算實驗 35
4.1啟發式演算法發展 35
4.2演算範例說明 41
4.2.1 範例一 41
4.2.2 範例二 46
4.2.3 範例三 50
4.3 演算實驗 50
第五章 研究發現與未來研究議題 55
5.1研究發現 55
5.2後續研究議題 56
參考文獻 57
附錄:演算法之程式碼 63
參考文獻 中文部分
蘇鈺婷. (2013). 線性單排機器佈置設計─網路切割解法之發展. 成功大學工業與資訊管理學系學位論文

英文部分
Amaral, A. R. (2009). A new lower bound for the single row facility layout problem. Discrete Applied Mathematics, 157(1), 183-190.
Anjos, M. F., & Vannelli, A. (2008). Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS Journal on Computing, 20(4), 611-617.
Armour, G. C., & Buffa, E. S. (1963). A heuristic algorithm and simulation approach to relative location of facilities. Management Science, 9(2), 294-309.
Braglia, M. (1996). Optimisation of a simulated‐annealing‐based heuristic for single row machine layout problem by genetic algorithm. International Transactions in Operational Research, 3(1), 37-49.
Chiang, W. C., & Kouvelis, P. (1996). An improved tabu search heuristic for solving facility layout design problems. International Journal of Production Research, 34(9), 2565-2585.
Chung, J., & Tanchoco, J. M. A. (2010). The double row layout problem. International Journal of Production Research, 48(3), 709-727.
Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations research, 6(6), 791-812.
Datta, D., Amaral, A. R., & Figueira, J. R. (2011). Single row facility layout problem using a permutation-based genetic algorithm. European Journal of Operational Research, 213(2), 388-394.
Deb, S. K., & Bhattacharyya, B. (2005). Solution of facility layout problems with pickup/drop-off locations using random search techniques. International Journal of Production Research, 43(22), 4787-4812.
Djellab, H., & Gourgand, M. (2001). A new heuristic procedure for the single-row facility layout problem. International Journal of Computer Integrated Manufacturing, 14(3), 270-280.
Drezner, Z. (1987). A heuristic procedure for the layout of a large number of facilities. Management Science, 33(7), 907-915.
Foulds, L. R., & Robinson, D. F. (1976). A strategy for solving the plant layout problem. Operational Research Quarterly, 845-855.
Hassan, M. M., Hogg, G. L., & Smith, D. R. (1986). SHAPE: a construction algorithm for area placement evaluation. International Journal of Production Research, 24(5), 1283-1295.
Heragu, S. S., & Kusiak, A. (1988). Machine layout problem in flexible manufacturing systems. Operations Research, 36(2), 258-268.
Heragu, S. S., & Kusiak, A. (1991). Efficient models for the facility layout problem. European Journal of Operational Research, 53(1), 1-13.
Houshyar, A., & McGinnis, L. F. (1990). A heuristic for assigning facilities to locations to minimize WIP travel distance in a linear facility. The International Journal of Production Research, 28(8), 1485-1498.
Kaufman, L., & Broeckx, F. (1978). An algorithm for the quadratic assignment problem using Bender's decomposition. European Journal of Operational Research, 2(3), 207-211.
Keller, B., & Buscher, U. (2015). Single row layout models. European Journal of Operational Research, 245(3), 629-644.
Khalil, T. M. (1973). Facilities relative allocation technique (FRAT). International Journal of Production Research, 11(2), 183-194.
Kim, J. Y., & Kim, Y. D. (1995). Graph theoretic heuristics for unequal-sized facility layout problems. Omega, 23(4), 391-401.
Kim, J. G., & Kim, Y. D. (1999). A branch and bound algorithm for locating input and output points of departments on the block layout. Journal of the Operational Research Society, 50(5), 517-525.
Koopmans, T. C., & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society, 53-76.
Kothari, R., & Ghosh, D. (2013a). Insertion based Lin–Kernighan heuristic for single row facility layout. Computers & Operations Research, 40(1), 129-136.
Kothari, R., & Ghosh, D. (2013b). Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods. European Journal of Operational Research, 224(1), 93-100.
Kouvelis, P., & Chiang, W. C. (1992). A simulated annealing procedure for single row layout problems in flexible manufacturing systems. International Journal of Production Research, 30(4), 717-732.
Kouvelis, P., & Kim, M. W. (1992). Unidirectional loop network layout problem in automated manufacturing systems. Operations Research, 40(3), 533-550.
Kouvelis, P., & Chiang, W. C. (1996). Optimal and heuristic procedures for row layout problems in automated manufacturing systems. Journal of the Operational Research Society, 47(6), 803-816.
Kumar, K. R., Hadjinicola, G. C., & Lin, T. L. (1995). A heuristic procedure for the single-row facility layout problem. European Journal of Operational Research, 87(1), 65-73.
Lacksonen, T. A. (1997). Preprocessing for static and dynamic facility layout problems. International Journal of Production Research, 35(4), 1095-1106.
Lawler, E. L. (1963). The quadratic assignment problem. Management science,9(4), 586-599.
Lee, S. D., Huang, K. H., & Chiang, C. P. (2001). Configuring layout in unidirectional loop manufacturing systems. International Journal of Production Research, 39(6), 1183-1201.
Lee, R. C., & Moore, J. M. (1967). CORELAP-computerized relationship layout planning. Journal of Industrial Engineering, 18(3), 195-200.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2), 498-516.
Meller, R. D., & Bozer, Y. A. (1996). A new simulated annealing algorithm for the facility layout problem. International Journal of Production Research, 34(6), 1675-1692.
Meller, R. D., Narayanan, V., & Vance, P. H. (1998). Optimal facility layout design. Operations Research Letters, 23(3), 117-127.
Montreuil, B. (1991). A modelling framework for integrating layout design and flow network design. In Material Handling’90 (pp. 95-115). Springer Berlin Heidelberg.
Nearchou, A. C. (2006). Meta-heuristics from nature for the loop layout design problem. International Journal of Production Economics, 101(2), 312-328.
Palubeckis, G. (2012). A branch-and-bound algorithm for the single-row equidistant facility layout problem. OR spectrum, 34(1), 1-21.
Picard, J. C., & Queyranne, M. (1981). On the one-dimensional space allocation problem. Operations Research, 29(2), 371-391.
Rajasekharan, M., Peters, B. A., & Yang, T. (1998). A genetic algorithm for facility layout design in flexible manufacturing systems. International Journal of Production Research, 36(1), 95-110.
Rosenblatt, M. J. (1986). The dynamics of plant layout. Management Science, 32(1), 76-86.
Samarghandi, H., & Eshghi, K. (2010). An efficient tabu algorithm for the single row facility layout problem. European Journal of Operational Research, 205(1), 98-105.
Samarghandi, H., Taabayan, P., & Jahantigh, F. F. (2010). A particle swarm optimization for the single row facility layout problem. Computers & Industrial Engineering, 58(4), 529-534.
Sarker, B. R., Wilhelm, W. E., Hogg, G. L., & Han, M. H. (1995). Backtracking of jobs in one-dimensional machine location problems. European Journal of Operational Research, 85(3), 593-609.
Simmons, D. M. (1969). One-dimensional space allocation: an ordering algorithm. Operations Research, 17(5), 812-826.
Singh, S. P., & Sharma, R. R. (2006). A review of different approaches to the facility layout problems. International Journal of Advanced Manufacturing Technology, 30(5-6), 425-433.
Solimanpur, M., Vrat, P., & Shankar, R. (2004). Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. European Journal of Operational Research, 157(3), 592-606.
Solimanpur, M., Vrat, P., & Shankar, R. (2005). An ant algorithm for the single row layout problem in flexible manufacturing systems. Computers & Operations Research, 32(3), 583-598.
Tompkins, J. A., & REED Jr, R., (1976). An applied model for the facilities design problem. International Journal of Production Research, 14(5), 583-595.
Zhang, Z., & Murray, C. C. (2012). A corrected formulation for the double row layout problem. International Journal of Production Research, 50(15), 4220-4223.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-08-04起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw