臺灣博碩士論文加值系統

工程專案中的作業可藉著機具與人力的增減來控制作業的天數，若要壓縮工期，一般須分派較高的資源或人力，也代表較多資金的投入。其中專案工期與直接成本之對應關係稱為時間成本權衡。了解工期與成本可能的組合，將協助規劃者決定各作業的最佳施工天數與資源需求。
各作業之時間成本關係函數一般可分為線性、非線性及組合型式，其中線性、非線性已能有效的以線性規劃或非線性規劃求解。但由於營建工程機具與人力均為有限且間斷的組合，組合式的時間成本關係較為接近實際的營建工程狀況。但也因此提高了求解的困難度及複雜度，再加上專案中作業項目的增加，將使得傳統啟發法與解析法無法很有效率地求得最佳解。
本研究發展質群演算法（PSO）以求解組合式時間成本權衡問題。主要利用群體智慧的概念，在可行解範圍的空間中搜尋最佳解。進一步分析領導策略、切割方式及回彈模式，以決定最適合之質群演算法。驗證部份則與窮舉法結果比較，以證明可有效求得最佳解。

Tasks in a construction project can often be accelerated using labor and equipment with higher efficiency and greater capacity. Such acceleration, however, is associated with higher cost. Thus it is important for project managers to choose among possible time-cost options to suit management needs, such as prespecified deadline. This problem is coined as the “time-cost tradeoff problem”.
For each task, the time-cost functions may be in linear, nonlinear, and discrete forms. Since the options of labor and equipment are practically finite and discrete, this study focuses on the time-cost tradeoff problem with discrete time-cost functions. The discrete time-cost tradeoff problem cannot be efficiently solved by traditional methods because the number of variables would exponentially explode as the number of tasks increases.
This study develops a new particle swarm optimization (PSO) algorithm, a class of stochastic search, to find the direct time-cost curve, which can be further used to obtain the total time-cost curve with consideration of indirect cost, delay penalty, and early bonus. The proposed PSO algorithm investigates three schemes: particle communication strategy, space zoning plan, and domain error prevention. Through a numerical case, it has been validated that the best design of the PSO algorithm consists of three schemes: (1) pair-wise swarm inter-communication; (2) single zoning, and (3) particle bouncing in domain error. The performance is measured in terms of effectiveness, efficiency, converging speed, and robustness. The proposed PSO algorithm has also been compared with exhaustive search and genetic algorithms to show its performance.

目錄......................................................I
圖目錄..................................................III
表目錄....................................................V
第一章 緒論.............................................1
1.1 研究動機............................................1
1.2 研究目的............................................2
1.3 研究方法及流程......................................3
1.4 論文架構............................................5
第二章 文獻回顧.........................................7
2.1 時間成本權衡........................................7
2.1.1 作業的時間成本關係................................8
2.1.2 專案的時間成本關係................................9
2.1.3 作業時間成本關係的種類.........................16
2.2 最佳化理論.........................................22
2.2.1 傳統最佳化方法...................................26
2.2.2 新式最佳化方法...................................28
2.3 最佳化理論用於時間成本權衡問題.....................31
2.3.1 傳統最佳化理論應用於時間成本權衡問題.............31
2.3.2 新式啟發式演算法應用於時間成本權衡問題...........34
2.4 質群演算法相關研究及應用...........................36
2.5 結論...............................................38
第三章 基本理論介紹....................................40
3.1 質群演算法理論基礎介紹.............................40
3.2 質群演算法之組成要素及參數.........................43
3.3 質群演算法之演算步驟...............................46
3.4 基因演算法與質群演算法之比較.......................48
3.5 結論...............................................49
第四章 演算法改良......................................51
4.1 傳統質群演算法運算.................................51
4.2 領導策略...........................................57
4.2.1 與每一質點相比的策略.............................57
4.2.2 與相鄰質點相比的策略.............................58
4.2.3 與第一個質點相比的策略...........................60
4.3 切割方式...........................................61
4.3.1 原始切割方式.....................................61
4.3.2 二個切割方式.....................................62
4.3.3 三個切割方式.....................................62
4.4 回彈模式...........................................63
4.4.1 質點不動.........................................63
4.4.2 質點被回彈.......................................64
4.4.3 質點被吸收.......................................65
4.5 結論...............................................65
第五章 範例實證及結果比較..............................67
5.1 窮舉法求解.........................................67
5.2 運算策略結果比較...................................70
5.2.1 領導策略結果比較.................................71
5.2.2 切割方式結果比較.................................73
5.2.3 回彈方式結果比較.................................74
5.2.4 小結.............................................76
5.3 敏感度分析.........................................77
5.3.1 粒子數...........................................78
5.3.2 慣性權重.........................................78
5.3.3 學習因子.........................................79
5.3.4 最大速度.........................................80
5.3.5 迭代次數.........................................80
5.4 與GA比較...........................................81
5.5 加入賞金罰金之狀況.................................82
5.6 結論...............................................85
第六章 結論與未來研究方向..............................87
6.1 研究結論...........................................87
6.2 未來研究方向.......................................88
參考文獻.................................................90
附錄.....................................................97


圖 目 錄

圖 1－1 研究流程圖........................................4
圖 2－1 作業的資源－時間關係圖............................9
圖 2－2 專案時間成本關係圖（一）.........................10
圖 2－3 專案時間成本關係圖（二）.........................11
圖 2－4 作業間關係示意圖.................................13
圖 2－5 開始－開始轉換示意圖.............................14
圖 2－6 結束－結束轉換示意圖.............................15
圖 2－7 開始－結束轉換示意圖.............................15
圖 2－8 作業前後關係圖...................................16
圖 2－9 時間－直接成本關係圖.............................17
圖 2－10 線性關係圖......................................18
圖 2－11 片段線性關係圖..................................18
圖 2－12 片段線性關係轉換示意圖..........................19
圖 2－13 凹型關係圖......................................19
圖 2－14 凸型關係圖......................................19
圖 2－15 混合型關係圖....................................19
圖 2－16 間斷型關係圖....................................20
圖 2－17 區域、全域最佳解示意圖..........................24
圖 2－18 區域最佳解判斷示意圖............................24
圖 2－19 基因演算法運算流程圖............................30
圖 3－1 粒子移動示意圖...................................42
圖 3－2 質群演算法運算流程圖.............................46
圖 4－1 作業施工天數選擇示意圖...........................53
圖 4－2 三維座標質點位置示意圖...........................53
圖 4－3 演算法程式流程圖.................................56
圖 4－4 鳥群移動示意圖...................................57
圖 4－5 與每一個質點比較之策略...........................58
圖 4－6 與相鄰質點比較之策略.............................59
圖 4－7 與第一個質點比較之策略...........................60
圖 4－8 不同切割數比較圖.................................61
圖 4－9 原始切割方式示意圖...............................62
圖 4－10 二個切割方式示意圖..............................62
圖 4－11 三個切割方式示意圖..............................63
圖 4－12 質點不動的碰撞策略..............................64
圖 4－13 質點被回彈的碰撞策略............................64
圖 4－14 質點被吸收的碰撞策略............................65
圖 5－1 範例作業間之前後關係.............................69
圖 5－2 運算策略組合.....................................71
圖 5－3 領導策略最佳解比較...............................73
圖 5－4 切割方式最佳解比較...............................74
圖 5－5 回彈方式最佳解比較...............................75
圖 5－6 PSO與GA結果比較圖................................82
圖 5－7 片斷線型示意圖...................................83
圖 5－8 總成本曲線.......................................84
圖 5－9 工期－成本關係圖.................................85


表 目 錄

表 2－1 時間成本關係函數之相關文獻.......................21
表 2－2 傳統用於求解時間成本權衡問題之方法...............33
表 2－3 基因演算法於營建時間成本權衡應用之相關文獻.......35
表 2－4 質群演算法之相關文獻.............................37
表 3－1 基因、質群演算法之比較...........................49
表 5－1 範例之作業天數工期選項...........................67
表 5－2 各工期對應之最小成本統計表.......................69
表 5－3 領導策略結果統計.................................72
表 5－4 切割方式結果統計.................................74
表 5－5 回彈方式結果統計.................................75
表 5－6 質點碰撞被吸收的運算策略比較.....................76
表 5－7 粒子數測試結果比較...............................78
表 5－8 慣性權重測試結果比較.............................79
表 5－9 學習因子測試結果比較.............................79
表 5－10 最大速度測試結果比較............................80
表 5－11 迭代次數測試結果比較............................81
表 5－12 各工期對應之最小總成本統計表....................84

【1】王秋竹（1995），「以動態規劃法為基礎之汽電共生廠最佳化運轉研究」，大同工學院電機工程學系碩士論文。
【2】王珮珮 （2005），「使用粒子群最佳化進行分散式系統之最佳工作分配」，暨南國際大學資訊管理學系研究所碩士論文。
【3】呂運慧（2003），「不動產估價之作業系統研究」，國立彰化師範大學商業教育系碩士論文。
【4】李燕松（1973），「線性規劃在會計上應用之研究」，東吳大學會計學研究所碩士論文。
【5】李建漳（2003），「以禁忌搜尋法應用於專案工期/成本權衡問題最佳化之研究」，朝陽科技大學營建工程研究所碩士論文。
【6】李世炳、鄒忠毅，「簡介導引模擬退火法及其應用」，物理雙月刊，24卷2期307-319 （2002年4月）。
【7】吳孟訓（2002），「動態規劃應用於公共空間火災逃生避難決策支援系統之初研」，國立台北科技大學土木與防災技術研究所碩士論文。
【8】林耀煌（2000）。營建工程施工規劃與管理控制（4版）。臺北：長松。
【9】邱彥勳（2004），「生物演算法於船舶自航器設計之研究」，國立高雄海洋科技大學/輪機工程研究所碩士論文。
【10】林師檀（2001），「禁忌搜尋法與遺傳演算法混合模式在地下水復育優選問題之應用」，國立中興大學環境工程學系碩士論文。
【11】洪裕政（2004），「線性規劃於煉油廠原油選擇應用之研究」，國立政治大學經營管理碩士論文。
【12】郭定（1989），「以整數規劃法作列車班次排點」，國立交通大學資訊工程研究所碩士論文。
【13】范植職（2004），「以整數線性規劃模式 探討產能擴充計劃--以某科技擴廠為例」，國立中正大學企業管理研究所碩士論文。
【14】胡曉輝，「粒子群優化算法介紹」，http://icdweb.cc.purdue.edu/~hux，2002年4月。
【15】高群峰（1994），「加權模糊線性規劃在多目標運輸問題上的應用」，中華大學工業研究所碩士論文。
【16】夏萬春（2000），「禁制搜尋法於車輛排班之探討」，高雄第一科技大學機械與自動化工程系碩士論文。
【17】陳坤茂（2003）。作業研究（2版）。臺北：華泰。
【18】陳孟駿、劉振隆，「建立高效率之禁忌基因演算法求解高維度之全域最佳化問題」，第十屆人工智慧與應用研討會。
【19】許維群（1997），「遺傳演算法與非線性規劃混合模式在地下水復育問題上之應用」，國立中興大學環境工程學研究所碩士論文。
【20】葉恩仲（2002），「模擬退火演算法在地下水復育優選問題之應用」，國立中興大學/環境工程學系碩士論文。
【21】張嘉君（2003），「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」，朝陽科技大學營建工程研究所碩士論文。
【22】葉思緯（2004），「應用粒子群最佳化演算法於多目標存貨分類之研究」，元智大學工業工程與管理學系研究所碩士論文。
【23】賴世若（1995），「以整數規劃與模擬求解服務業班別排程問題」，中原大學工業工程研究所碩士論文。
【24】劉昱江（2001），「基因演算法在重複性工程時間成本分析之應用」，朝陽科技大學營建工程研究所碩士論文。
【25】蘇木春、張孝德（2000）。機器學習：類神經網路、模糊系統以及基因演算法則。臺北：全華。
【26】http://chern.ie.nthu.edu.tw/Ant_Algorithms.htm。（2006/5/26摘錄）
【27】http://www.en.ctu.edu.tw/EN309/products_en309.htm。（2006/5/26摘錄）
【28】Angeline, P.J. （1998）, ”Using selection to improve particle swarm optimization,” In: Proceedings of the IEEE Congress on Evolutionary Computation, Anchorage, Alaska.
【29】Chan, W. T., D. K. H. Chua, and G. Kannan,（1996）, ”Construction resource scheduling with genetic algorithms,” Journal of Construction Engineering and Management, Vol. 122, Issue 2, pp.125-132.
【30】Chu, W. M., M. J. Yao, S. E. Elmaghraby, and T. Y. Tseng. （2003）, “A Simulation-based Genetic Algorithm for the Optimal Resource Allocation in Probability Activity Networks,” The Fifth Metaheuristics International Conference, Kyoto, Japan.
【31】Clerc, M. (1999), ”The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proc. I999 Congress on Evolutionary Computation,Washington, DC, Vol. 3, pp.1-1957.
【32】David, C., D. Marco, and G. Fred,（1999）, “New Ideas in Optimization,” pp.379-387.
【33】De, P., E. J. Dunne, J. B. Ghosh, and C. E. Wells,（1995）, ”The discrete time-cost tradeoff problem revisited,” European Journal of Operational Research, Vol. 81, No. 2, pp.225-238.
【34】Deckro, R.F., J. E. Hebert, W. A. Verdini, P. H. Grimsrud, S. Venkateshwar,（1995）, ”Nonlinear time/cost tradeoff models in project management,” Computers and Industrial Engineering, Vol. 28, No. 2, pp.219-229.
【35】Eberhart, R.C. and Y. Shi.,（1998）, ”Comparison between genetic algorithms and particle swarm optimization,” Annual Conference on Evolutionary Programming, San Diego.
【36】Eberhart, R. C and Y. Shi,（2001）, ”Particle swarm optimization: developments applications and resources,” Proc. IEEE Int.conf.On Evolutionary Computation, pp.81-86.
【37】Elmaghraby, SE. and A. Salem, (1981), “Optimal project compression under convex cost functions II,” OR Technical Report 157, North Carolina State University at Raleigh.
【38】Falk, JE. and JL. Horowitz, (1972), “Critical path problems with concave cost-time curves,” Mgmt Sci Vol. 19, pp.446-455.
【39】Feng, C. W., L. Liu., and S. A. Bruns, (1997), “Using genetic algorithms to solve construction time-cost trade-off problems,” Journal of Construction Engineering and Management, ASCE, Vol. 11, No. 3, pp.184-189.
【40】Feng, C. W., L. Liu, and S. A. Burns.（2000）, ”Stochastic Construction Time-Cost Trade-Off Analysis,” Journal of Computing in Civil Engineering, Vol. 14, Issue 2, pp.117-126.
【41】Foldes, S. and F. Sourmis, (1993), “PERT and crashing revisited: mathematical generalizations,” European Journal of Operational Research, Vol. 64, pp.286-294.
【42】Fulkerson, DR., (1961), “A network flow computation for project cost curves,” Mgmt Sci, Vol. 7, pp.167-178.
【43】Gottfried, B. S. and J. Weisman,（1976）, “Introduction to optimization theory,” Englewood Cliffs, N.J. : Prentice-Hall.
【44】Harris, R. B.,（1978）, “Precedence and arrow networking techniques for construction,” John Wiley & Sons, Inc., New York, N.Y.
【45】Hegazy, T., and Ayed, A. （1999）,”Simplified Spreadsheet Solutions：Models for Critical Path Method and Time-Cost-Tradeoff Analysis,” Cost Engineering, AACE International, AACE, Vol. 41, No. 7, pp.26-33.
【46】Holland, J. H.,（1975）, ”Adaptation in natural and artificial systems,“ University of Michigan press, Ann Arbor, Mich.
【47】Kapur, KC., (1973), “An algorithm for the project cost/duration analysis problem with quadratic and convex cost functions,” IIE Transactions, Vol. 5, pp.314-322.
【48】Kelley, JE. and Mr. Walker, (1959), “Critical path planning and scheduling: An introduction,” Mauchly Associates, Ambler, PA.
【49】Kelley, JE., (1961), “Critical path planning and scheduling: Mathematical basis,” Ops Res, Vol. 9, pp.296-320.
【50】Kennedy, J. and R. Eberhart, (1995), ”Particle Swarm Optimization,” IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, IV: 1942-1948.
【51】Leite, J. P. B. and B. H. V. Topping,（1999）, ”Parallel simulated annealing for structural optimization,” Computers and Structures, Vol. 73, No. 1, pp.545-564.
【52】Leu, S. S. and C. H. Yang,（1999）, ”GA-Based Multicriteria Optimal Model for Construction Scheduling,” Journal of Construction Engineering and Management, Vol. 125, Issue 6, pp. 420-427.
【53】Li, H., and P. Love,（1997）,”Using Improved Genetic Algorithms to Facilitate Time-Cost Optimization,” Journal of Construction Engineering and Management, Vol. 123, Issue 3, pp.233-237.
【54】Li, H., J. N. Cao, and P. E. D. Love,（1999）,”Using Machine Learning and GA to Solve Time-Cost Trade-Off Problems,” Journal of Construction Engineering and Management, Vol. 125, Issue 5, pp.347-353.
【55】Moder, J.J., C. R. Phillips, and E. W. Davis, (1995), “Project management with CPM,PERT and precedence diagramming. 3rd edition,” Blitz Publishing Company, Wisconsin.
【56】Moselhi, O.,（1993）, ”Schedule compression using the direct stiffness method,” Can. J. Civ. Eng., Ottawa, Vol. 20, No. 1, pp.65-72.
【57】Papadimitriou, C. H. and K. Steiglitz,（1982）, “Combinatorial Optimization：algorithms and complexity,” Englewood Cliffs, N.J. : Prentice-Hall.
【58】Patterson, J. H. and D. Huber., （1974）, ”A horizon-varying, zero-one approach to project scheduling,” Management Science, Vol. 20, No. 6, pp.990-998.
【59】Prabuddha, D., E. J. Dunne, J. B. Ghosh, and C. E. Wells, （1997）, ”Complexity of the Discrete Time-Cost Tradeoff Problem for Project Networks,” Operations Research, Vol. 45, No. 2, pp. 302-306.
【60】Scott, A. B., L. Liu, and C. W. Feng, (1996), “The LP/IP hybrid method for construction time-cost trade-off analysis,” Construction Management and Economics, Vol. 14, No. 3, pp.265-276.
【61】Shi, Y. and R. Eberhart,（1998）, ”A Modified Particle Swarm Optimizer,” IEEE International Conference on Evolutionary Computation, May 1998, Anchorage, Alaska, USA.
【62】Shi, Y. and R. Eberhart,（1998）, “Parameter selection in particle swarm optimization,” Evolutionary Programming VII: Proc. EP 98 pp.591-600.Springer-Verlag, New York.
【63】Siemens, N.,（1971）, “A simple CPM time-cost trade-off algorithm,” Management Science, Vol. 17, No. 6, pp.354-363.
【64】Skutella, M.,（1998）, ”Approximation algorithms for the discrete time-cost tradeoff problem,” Mathematics of Operations Research, Vol. 23, No. 4, pp.909-929.
【65】Trelea, I. C.,（2003）, ”The particle swarm optimization algorithm: convergence analysis and parameter selection,” Information Processing Letters, Vol. 85, Issue 6, pp.317-325.
【66】Yang, I. T.,（2005）, “Chance-constrained time-cost tradeoff analysis considering funding variability,“ Journal of Construction Engineering and Management, ASCE, Vol. 131, Issue 9, pp. 1002-1012.
【67】Zheng, D. X. M., S. T. Ng, and M. M. Kumaraswamy,（2004）, ”Applying a Genetic Algorithm-Based Multiobjective Approach for Time-Cost Optimization,” Journal of Construction Engineering and Management. Vol. 130, Issue 2, pp.168-176.
【68】Zhang, H., X. Li, H. Li, and F. Huang,（2005）, ”Particle swarm optimization-based schemes for resource-constrained project scheduling,” Automation in Construction, Vol. 14, pp.393-404.