(3.235.108.188) 您好!臺灣時間:2021/02/27 03:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蕭博文
研究生(外文):Po-Wen Hsaio
論文名稱:應用禁忌搜尋法求解營建工程專案多重資源排程最佳化之研究
論文名稱(外文):A study on multi-resources scheduling optimization using tabu search method.
指導教授:潘乃欣潘乃欣引用關係
指導教授(外文):Nai-Hsin Pan
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:營建工程系碩士班
學門:工程學門
學類:土木工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:75
中文關鍵詞:禁忌搜尋法限制資源資源排程
外文關鍵詞:tabu searchresources schedulinglimited resources
相關次數:
  • 被引用被引用:25
  • 點閱點閱:436
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:68
  • 收藏至我的研究室書目清單書目收藏:2
摘要
營建工程專案資源排程之主要目標有三:(1)使所有施工作業項目均能適時獲得資源供應開始施作,在預定工期內完成作業施作項目;(2)當資源受到限制時,能最充份有限的利用資源分配給予各項施工作業,使工期延誤之可能降到最低;(3)有效的運用施工資源以得到較佳之工程財務管理,進而增加收益。
由於營建工程專案規模日益龐大,在考慮有限資源的情況下,使資源排程相對的更加複雜。若是以傳統的計算模式來求解這類問題,雖然可以求得最佳解,但繁複的過程以及求解效率不彰為其缺點。所以綜觀前人的研究均提出新的演算法來改善求解效率,如啟發式演算法、基因演算法等。禁忌搜尋法在工業工程領域已廣泛的應用於求解各種組合最佳化問題,且已有不錯的成效。其原理是應用其特有的彈性記憶架構以及凌駕準則,擴大搜尋鄰近之範圍,以導引搜尋法跳離區域最佳解之陷阱。本研究在考量資源限制的情況下,利用禁忌搜尋法建立新的演算模式,應用禁忌搜尋法所建構之演算模式分析求解多重資源排程問題,並改善傳統計算模式的缺點,使得求解品質佳且效率更高。
Abstract
There are three objectives on the construction project resource scheduling: (1) to let all of the activities get their resources and then complete the works before the required finish date; (2) to make resource allocation and utilization efficiently to reduce the delay possibility of the works when the capacity; (3) to utilize there sources more effectively to get the better financial management performance and also increase our revenue.
Considering the conditions of the constrained resources, resources scheduling become more difficult as of the scope of construction engineering projects become larger and more complex. Although using traditional models to solve this sort of problems could obtain the optimal solution, the process of evaluation will be complex and inefficiency. In the previous studies, most of the studies focus on finding a new algorithm such as genetic algorithm to improve the speed of searching feasible solutions. The research uses a new algorithm, namely Tabu search, to solve the problem of resource scheduling which are constrained. Tabu search method was widely applied to solve the various kinds of combinatorial optimization problems in the industrial engineering area and got distinguished results. It is based on introducing flexible memory structures in conjunction with strategic restrictions and aspiration levels as a means for exploiting search spaces. The research will explore the feasibility of this algorithm and implements the concept of tabu search method to set up a new model considering constrained resources. The research found using this new model built by tabu search could solve the multi-resources problems of construction project, but also provide a precise solutions in some cases, Furthermore, this model also makes improvement on the disadvantages of traditional models and both make the better solution quality and higher efficiency of evaluation.
第一章緒論...............................................1
1.1研究動機……………………………………………………… 1
1.2研究目的……………………………………………………… 1
1.3 研究方法與流程…………………………………………………… 2
1.4 論文架構…………………………………………………………… 5
第二章 文獻回顧……………………………………………………………… 6
2.1資源排程最佳化之相關研究………………………………………… 6
2.2禁忌搜尋法(tabu search)之相關研究…………………………… 9
2.2.1 禁忌搜尋法之相關研究……………………………………… 9
2.3 結語…………………………………………………………………. 10
第三章 基本理論介紹…………………………………………………….…. 12
3.1 資源排程之基本理論………………………………………………. 12
3.1.1 資源分配…………………………………………………….. 12
3.1.2 資源拉平…………………………………………………... 14
3.2 禁忌搜尋法之基本理論……………………………………………. 15
3.2.1 禁忌搜尋法之組成要素…………………………………….. 16
3.2.2 禁忌搜尋法之演算步驟…………………………………….. 18
第四章 模式架構建立……………………………………………………... 23
4.1 資源分配……………………………………………………………. 23
4.1.1 目標值與目標函數之建立……………...………………… 23
4.1.2 禁忌搜尋法之起始解………………...…………………… 25
4.1.3 禁忌搜尋法之鄰近解結構………………………………….. 28
4.1.4 禁忌搜尋法之禁忌列表結構……………………………….. 29
4.1.5 禁忌搜尋法之移動路徑…………………………………….. 30
4.1.6 結束規則…………………………………………………….. 31
4.2 資源拉平……………………………………………………………. 33
4.2.1 目標值與目標函數之建立………………………………….. 33
4.2.2 禁忌搜尋法之鄰近解結構………………………………….. 34
4.2.3 禁忌搜尋法之禁忌列表結構……………………………….. 34
4.2.4 禁忌搜尋法之移動路徑…………………………………….. 35
4.2.5 結束規則…………………………………………………….. 35
4.2.6 演算流程…………………………………………………….. 36
4.3 結語…………………………………………………………………. 36
第五章 案例實證…………………………………………………………….. 38
5.1資源分配問題……………………………………………………… 39
5.1.1 案例說明…………………………………………………... 40
5.1.2 結果討論…………………………………………………….. 44
5.2 資源拉平問題………………………………………………………. 48
5.2.1 案例說明…………………………………………………….. 48
5.2.2 結果討論…………………………………………………….. 50
5.3 案例敏感性分析……………………………………………………. 53
5.4 結語…………………………………………………………………. 58
第六章 結論與建議………………………………………………………….. 59
6.1 結論…………………………………………………………………. 59
6.2 未來研究方向與建議………………………………………………. 60
參考文獻……………………………………………………………………… 62

表目錄
表5.1 硬體配備及環境………………………………………………………. 38
表5.2 案例一之執行結果……………………………………………………. 45
表5.3 案例二之執行結果...………………………………………………….. 45
表5.4 案例五之執行結果……………………………………………………. 51
表5.5 案例六之執行結果……………………………………………………. 51
表5.6 案例七之執行結果……………………………………………………. 52

圖目錄
圖 1.1 研究流程圖…………………………………………………………… 4
圖 3.1 啟發式方法之比較………………………………………………… 14
圖 3.2 交換式移步swap move示意圖………………………….……… 17
圖 3.3 插入式移步insert move示意圖……………………….………… 17
圖 3.4 禁忌搜尋法之基本運算流程………………………………………. 21
圖 4.1 目標函數二,競爭淘汰式法則示意圖……………………………. 25
圖 4.2 MINSLK求得之起始解之流程圖…………………………………. 27
圖 4.3 MINSLK求得之起始解之結構示意圖………………………….. 27
圖 4.4 交換式移步中啟發式法則示意圖…………………………………... 29
圖 4.5(a) swap move禁忌列表示意圖…………………………………… 30
圖 4.5(b) insert move禁忌列表示意圖…………………………………… 30
圖 4.6 資源分配之演算流程圖…………………………………………….. 32
圖 4.7 資源拉平之鄰近解結構示意圖…………………………………….. 35
圖 4.8 禁忌列表結構示意圖………………………………………………. 35
圖 4.9 資源拉平計算之演算流程圖…………………………………….… 37
圖 5.1 程式畫面一…………………………………………….…………….. 39
圖 5.2 程式畫面二…………………………………………….…………….. 39
圖 5.3 程式畫面三…………………………………………….…………….. 39
圖 5.4 程式畫面四…………………………………………….…………….. 39
圖 5.5 案例一網圖……………………………………...…….…..…………. 41
圖 5.6 案例一之各項資料數據………..…………………………………… 41
圖 5.7 案例二之網圖……….……………………………………….……… 42
圖 5.8 案例二之各項資料數據………...…………………………………… 42
圖 5.9 案例三之網圖及各項資料……...…………………………………… 43
圖 5.10 案例四之網圖及各項資料…...…………………………………… 43
圖 5.11 案例一A資源之每日使用情形…..………………………………. 46
圖 5.12 案例一B資源之每日使用情形……..……………………………. 46
圖 5.13 案例一C資源之每日使用情形……..……………………………. 46
圖 5.14 案例二R1資源之每日使用情形………………………………… 47
圖 5.15 案例二R2資源之每日使用情形………………………………… 47
圖 5.16 案例二R3資源之每日使用情形………………………………… 47
圖 5.17 案例二R4資源之每日使用情形………………………………… 47
圖 5.18 案例二R5資源之每日使用情形………………………………… 47
圖 5.19 案例二R6資源之每日使用情形………………………………… 47
圖 5.20 案例五網圖…………………..…………………………………… 48
圖 5.21 案例五之各項資料數據………………………………………….. 49
圖 5.22 案例六網圖…………………..…………………………………… 49
圖 5.23 案例六之各項資料數據……………...…………………………….. 49
圖 5.24 案例七網圖…………………..……………………………………. 50
圖 5.25 案例七之各項資料數據…………………………………………… 50
圖 5.26 案例五資源拉平前後之山積山崩圖…………………………….… 52
圖 5.27 案例六資源拉平前後之山積山崩圖…………………………….… 52
圖 5.28(a) 案例七資源A拉平前後之山積山崩圖……………………….… 53
圖 5.28(b) 案例七資源B拉平前後之山積山崩圖……………………….… 53
圖 5.29 以swap移步方式求解結果………………………………………… 55
圖 5.30 以insert移步方式求解結果……………………………………….. 56
圖 5.31 資源分配之禁忌列表敏感性分析…………………………………. 56
圖 5.32 資源分配之候選名單敏感性分析…………………………………. 56
圖 5.33 資源拉平之禁忌列表敏感性分析…………………………………. 58
圖 5.34 資源拉平之候選名單敏感性分析…………………………………. 58

公式目錄
4.1式、資源分配之目標方程式一……………………………………………..24
4.2式、資源分配之目標函數一之限制式…..…………………………………24
4.3式、資源分配之目標方程式二……….…………………………………….24
4.4式、資源拉平之目標方程式………….…………………………………….33
參考文獻
中文部分:
1.方曉嵐,1996,「排程方法研究」,技術與訓練,第21卷,第1期,第149-155頁。
2.呂紹煌、廖經芳,1999,「以塔布搜尋法求解開放工廠排程問題」,碩士論文,朝陽科技
大學工業工程研究所,台中
3.沈進發,1997,「營建管理工程規劃與管制」。
4.吳泰熙、張欽智,1997,「以禁忌搜尋法則求解推銷員旅行問題」,大葉學報,第六卷,
第一期,第87-99頁。
5.吳泰熙、張欽智,1998,「應用禁忌搜尋法則於多目標推銷員旅行問題之求解」,
Journal of the Chinese Institute of Industrial Engineers,15(6), pp.589-603.
6.吳琴玲,蘇純繒,2000,「物流配送系統之區位-途程問題研究」,碩士論文,國立雲林
科技大學工業工程與管理研究所,雲林。
7.林宏勳、王晉元,1995,「節線排程問題路線改善方法之研究」,碩士論文,國立交通大
學土木工程研究所,新竹。
8.林耀煌,1998,「營建工程施工規劃與管理控制」,長松出版社。
9.張文貴、林柏新,1995,「資源限制下之專案優勢排程方法」,管理與系統,第2卷,第2
期,第191-203頁。
10.陳正雄、張百棧,2000,「塔布搜尋法在塑化業排程之應用-以BOPP FILM為例」,碩士
論文,元智大學工業工程研究所。
11.陳安亭、呂守陞,1998,「專案工程模糊排程最適化求解之探討」,碩士論文,國立台
灣科技大學營建工程技術研究所,台北。
12.黃文孝、葉怡成,1994,「以遺傳演算法作資源限制排程最佳化之研究」,碩士論文,
中華工學院土木工程研究所。
13.黃志榮、宋明弘,1993,「啟發法在資源限制專案排程之應用-特性預測績效之實驗性研
究」,碩士論文,大業大學事業經營研究所,彰化。
14.曾貽威、潘乃欣,2001,「考慮現今流量專案之多重資源最佳化之研究」,碩士論文,
朝陽科技大學,台中
15.楊崇揮、呂守陞,1997,「多評準施工流程最適化計算模式之探討」,碩士論文,國立
台灣科技大學營建工程技術研究所,台北
16.鄭瑞富、李宇欣,2000,「公路平縱面線形最佳化設計模式」,博士論文,國立成奶j
學土木工程學系,台南。
17.劉福勳,1997,「營建管理概論」,漢天下工程管理顧問有限公司。
18.劉自強、李榮貴、蔡志弘,1999,「以限制理論為基礎之專案排程及執行控制研究」,
碩士論文,國立交通大學工業工程與管理學系,新竹。
19.駱景堯,1999,「禁忌搜尋法在彈性零工型製造系統排程之探討」,Journal of the
Chinese Institute of Industrial Engineers,16(5), pp.605-615.
英文部分:
20.Ahuja, N. H. et al.(1994), ”Project Management techniques in planning and
controlling construction project.”, pp.127-162.
21.BenDaya, M. and AlFawzan, M. (1998), “A tabu search approach for the flow
shop scheduling problem.” European Journal of Operational Research, 109, 88-
95.
22.Chan, W. T. , Chua, D. K. H. and Kannan, G. (1996), “Construction resource
scheduling with genetic algorithms.” J. Constr. Engrg. and Mgmt., ASCE, 122
(2), 125-132.
23.Callahan, T. M. et al.(1992),”Construction project scheduling.”, pp.277-
291.
24.Cooper, D. F. (1976), “Heuristics for scheduling resource constrained
projects :An experimental investigation.” Management Science., 22(11), 1186-
1194.
25.Davis, E. W. (1973), “Project scheduling under resource constraints
historical review and categorization of procedures.” AIIE Trans., 5(4), 297-
312.
26.Davis, E. W. and Patterson, J. H., (1975), “A comparison of heuristic and
optimum solutions in resource-constrained project scheduling.” Management
Science., 121(8), 944-955.
27.Easa, S. M. (1989), “Resource leveling in construction by optimization.”
J. Constr. Engrg. and Mgmt., ASCE, 115(2), 302-316
28.Faniran, O. O., Love, P. E. D., and Li, H. (1999), “Optimal allocation of
construction planning resources.” J. Constr. Engrg. and Mgmt., ASCE, 125
(5), 311-319.
29.Glover, F. (1997), “tabu search”
30.Glover, F. et al. (1995), “Genetic Algorithms and Tabu Search hybrids for
optimization.” Computers Ops Res., 22(1), 111-134.
31.Hegazy, T. (1999), “Optimization of resource allocation and leveling using
genetic algorithms.” J. Constr. Engrg. and Mgmt., ASCE, 125(3), 167-175.
32.Hiyassat, M. A. S. (1999), “Modification of minimum moment approach in
resource leveling.” J. Constr. Engrg. and Mgmt., ASCE, 126(4), 278-284.
33.Kolahan, F. M. and Liang, M. Z. (1995), “Solving the combined part
sequencing and tool replacement center: a tabu search approach.” Computer
Industrial Engineering., 28(4), 731-743.
34.Leu, S. S., Chen, A. T., and Yang, C. H. (1999), “Fuzzy optimal model for
resource-constrained construction scheduling.” J. Comp. Civ. Engrg., ASCE,
13(3), 207-216.
35.Moder, J. J.(1983), ”Project management with CPM, PERT and precedence
diagramming.”, pp.191-227.
36.Morse, L., and Whitehouse, G. (1988), “A study of combining heuristics for
scheduling projects with limited multiple resources.” Comp. and Industrial
Engrg., 15(4), 153-161.
37.Nowicki, E. and Smutnicki, C. (1996), “A fast search for the permutation
flow-shop problem.” European Journal of Operational Research, 91, 160-175.
38.Padilla, E. M. and Carr, R. (1991), “Resource strategies for dynamic
project management.” J. Constr. Engrg. and Mgmt., ASCE, 117(2), 279-293.
39.Pirlot, M. (1996), “General local search methods.” European Journal of
Operational Research, 92, 493-511.
40.Son, J., and Skibniewski, M. J. (1999), “Multiheuristic approach for
resource leveling problem in construction engineering : Hybrid Approach.”
J. Constr. Engrg. and Mgmt., ASCE, 125(1), 23-31.
41.Wen, U. P. and Ching-I, Y. (1997), “Tabu search methods for the flow shop
sequencing problem.” Journal of Chinese Institute of Engineers, 20(4), 465-
470.
42.Widmer, M. and Hertz, A. (1989), “A new approach solving the sequencing
problem.” European Journal of Operational Research, 41, 186-193.
43.Wiest, J., D., (1963), “The scheduling of large project with limited
resource,” Unpublished Ph.D. thesis, Carngie Institute of Technology.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔