(18.204.2.190) 您好!臺灣時間:2021/04/19 08:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:劉秋蘭
研究生(外文):Chiu-lan Liu
論文名稱:多重作業方式及資源限制下最大淨現值專案排程模式暨求解演算法之研究
論文名稱(外文):Multi-mode resource constrained project scheduling model to maximize net present value and a Solution Algorithm
指導教授:顏上堯顏上堯引用關係
指導教授(外文):Shang-yao Yan
學位類別:碩士
校院名稱:國立中央大學
系所名稱:土木工程研究所
學門:工程學門
學類:土木工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:71
中文關鍵詞:多重作業方式及資源限制下之專案排程淨現值時空網路含額外限制整數網路流動問題
外文關鍵詞:MRCPSPDCFnet present valuetime-space networkinteger network flow problem with side constrain
相關次數:
  • 被引用被引用:6
  • 點閱點閱:147
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在全球化經濟快速發展下,企業為求得生存與發展需更有效地利用有限的資源、盡量縮短專案時間週期及降低作業成本,以求得最大的利潤。然而隨著專案規模的迅速成長,專案排程問題牽涉的相關因素逐漸複雜。雖然過去的專案排程有利用要徑法與計畫評核術進行專案作業排程,但是近幾年來因環境資源匱乏,單憑考量時程的控管而未考量有限的資源,則決策缺乏整體最佳化分析,常非最佳及最有效率之決策。若能將資源限制及不同作業方式等因素加以考量,並建立決策模式,則可望幫助決策者有效地求解此類複雜的專案作業排程。
本研究針對多重作業方式及資源限制下最大淨現值專案排程問題,考量現金流量時間價值及相關作業流程與資源限制,利用時空網路流動技巧及數學規劃方法構建一數學模式,以整合有限的資源規劃專案作業排程。此模式為一含額外限制整數網路流動問題,可以利用CPLEX數學規劃軟體求解。為測試本研究模式及演算法的求解績效,本研究以國際測試題庫(PSPLIB)所提供之專案資訊,進行一範例研究,測試結果良好,顯示本研究模式應可為學術及實務業者之參考。
Due to the fast development of global economy, the enterprises must efficiently use limited resources and essentially reduce the working time period and the operating cost for the project in order to maximize its profit. Because the project size grows rapidly nowadays, these factors involving project scheduling are more and more complex than before. Traditionally, the critical path method (CPM) and the program evaluation and review technique (PERT) were used to formulate the project scheduling. The past time-controlled process for CPM and PERT is neither efficient nor effective from a system perspective, especially due to the short of environment resources recently. A model incorporating the resource-constrained and the different ways of working is expected to help the decision maker to efficiently solve the complicated project scheduling problem.

Dealing with the multi-mode resource constrained project scheduling problem with discounted cash flow (MRCPSPDCF), this research adopts the time-space network technique to formulate a mathematical programming model which considers the cash flow value of time and related operating and resource constraints. The mode is formulated as an integer network flow problem with side constraints, which is characterized as NP-hard in terms of optimization. We employ the CPLEX mathematical programming solver, to solve the problem. To evaluate the performance of the proposed model, numerical tests regarding the project scheduling problem library (PSPLIB) are performed. The test results show that the model could be useful references for academics and practicals.
目 錄
摘要 i
ABSTRACT ii
目 錄 iii
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與程式架構 3
第二章 文獻回顧 5
2.1考慮淨現值之多重作業方式及資源限制下專案排程設計 5
2.2淨現值用於專案排程相關文獻 7
2.3 時空網路設計相關文獻 9
2.4 文獻評析 10
第三章 模式構建 11
3.1 基本假設與已知資訊 11
3.2 虛擬作業節線設計 13
3.3 最早及最晚開始/完成時間設計 17
3.3.1求解最早開始時間運算方式 18
3.3.2求解最晚開始時間運算方式 20
3.4作業流時空網路設計 23
3.4.1 流量調整係數 27
3.4.2 符號說明 28
3.4.3 數學定式 29
3.5小範例驗證 30
3.6 模式檢討與應用 34
3.7 小結 34
第四章 範例測試 35
4.1 資料分析 35
4.2 模式發展 37
4.2.1 問題規模 37
4.2.2 模式輸入資料 38
4.3電腦演算環境及設定 38
4.3.1 電腦演算環境 38
4.3.2 相關程式(參數)設定 38
4.3.3 模式輸出資料 40
4.4 測試結果與分析 40
4.4.1 淨現值最大化目標下之測試結果 40
4.4.2 工期最小化目標下之測試結果 42
4.5 敏感度分析 44
4.5.1 專案總經費之敏感度分析 44
4.5.2 折現率變動之敏感度分析 46
4.5.3 懲罰/獎勵比率變動之敏感度分析 49
4.6 方案分析 51
4.6.1 不同問題規模及誤差下之方案分析 51
4.6.2 不同問題規模及目標下之方案分析 53
4.7小結 55
第五章 結論與建議 56
5.1 結論 56
5.2 建議 57
5.3 貢獻 58
參考文獻 59
附錄 63
附錄一 CPLEX Callable Library Code 63


圖目錄
圖 1. 研究方法與流程圖 4
圖 2. 作業網路圖 13
圖 3. AoA作業連結網路圖 16
圖 4. 虛擬作業連接關係示意圖 17
圖 5. 最早開始時間網路示意圖 20
圖 6. 最晚開始時間網路示意圖 22
圖 7. 作業流時空網路示意圖 26
圖 8. 流量調整係數設計示意圖 27
圖 9. 小範例作業流動節線示意圖 33
圖 10. 專案總經費與目標值關係圖 45
圖 11. 最小工期目標下專案總經費與目標值關係圖 46
圖 12. 折現率與目標值關係圖 47
圖 13. 最小工期目標下折現率與目標值關係圖 49
圖 14. 懲罰/獎勵比率與目標值關係圖 50


表目錄
表 1. 國際測試題庫提供之資料資訊 14
表 2. 前置作業及結合點編號資訊 15
表 3. 各作業結合點編號連結資訊 15
表 4. 最早開始及最晚開始計算所需資訊 18
表 5. 前置作業及最短工期 19
表 6. 後續承接作業及最長工期 21
表 7. 作業流時空網路之節線設計 25
表 8. 小範例已知資訊 30
表 9. 專案作業排程模式之求解結果表 32
表 10. 專案作業排程模式之細部解結果表 32
表 11. 研發總經費預算表 36
表 12. 各項資源費用估算表 37
表 13. 專案作業排程模式問題規模表 37
表 14. 淨現值最大化專案作業排程模式之求解結果表 40
表 15. 專案作業排程模式細部解 41
表 16. 工期最小化專案作業排程模式之求解結果 42
表 17. 專案作業排程模式細部解 43
表 18. 專案總經費於各成本百分比下之敏感度分析 44
表 19. 專案總經費細部解 45
表 20. 最小工期目標下專案總經費於各成本百分比下之目標值表 46
表 21. 折現率變動之敏感度分析 47
表 22. 折現率細部解 48
表 23. 最小工期目標下折現率變動之敏感度分析 48
表 24. 懲罰/獎勵比率之敏感度分析 49
表 25. 懲罰/獎勵比率細部解 50
表 26. 不同方案之規模估算表 51
表 27. 淨現值最大化不同問題規模及誤差下之方案分析表 52
表 28. 工期最小化不同問題規模及誤差下之方案分析表 53
表 29. 不同問題規模及目標下之方案分析表 54
參考文獻
1.朱麗穎、陳春益,「航商現金流動模式之研究」,碩士論文,國立成功大學交通管理科學研究所 (1997)。
2.林士鈞,「定期貨櫃運輸船舶排程暨船期表建立之研究」,碩士論文,國立中央大學土木工程系 (2006)。
3.邱明琦、陳春益、林佐鼎,「海運貨櫃排程模式之研究」,運輸計劃季刊,第三十一卷,第三期,第495-522頁 (2002)。
4.許秀影等編著,專案管理基礎知識與應用實務,三版,社團法人中華專案管理學會,台北市,民國97年。
5.張軍、陳偉能 、黃韜,「運用蟻群算法優化項目調度中的折現現金流的方法」,中華人民共和國中山大學,Computer systems based on biological models (2008)。
6.張佩璇,「航空公司資金流動規劃模式之建立」,碩士論文,國立中央大學土木工程系 (2000)。
7.曾貽威,「考量現金流量之專案多重資源排程最佳化之研究」,碩士論文,朝陽科技大學營建工程學系 (2001)。
8.黃培修,「專案排程與資源調派整合模式」,碩士論文,國立成功大學土木研究所 (1999)。
9.楊建邦、陳春益、張永昌,「動態網路應用於航現金流動問題之研究」,中華民國第四屆運輸網路研討會 (1999)。
10.陳妙珍、顏上堯、張珮璇,「航空公司資產與負債管理模式之建立」,第四屆海峽兩岸會計與管理學術研討會論文集,武漢 (2000)。
11.鄭逸亮,「以最大-最小螞蟻系統解決多模式有限資源專案排程問題之研究」,碩士論文,國立高雄第一科技大學電腦與通訊工程系 ( 2007)。
12.盧華安,「因應班機延遲之最佳化即時機門指派」,運輸計劃季刊,第三十卷,第四期,第849-869頁 (2001)。
13.顏上堯、翁綵穗,「季節轉換間緩衝期飛航排程之研究」,運輸計劃季刊,第三十卷,第四期,第891-921頁 (2001)。
14.經濟部小型企業創新研發計畫:計劃書範本。2011年5月22日,取自http://www.sbir.org.tw/SBIR/Web/Template_data.aspx?GUID=2061c7d3-9392-4ee0-9178-39d562f109b4。
15.Ballestin, F., Barrios, A. and Valls, V., “An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags,” Journal of Scheduling, Vol. 14, No.4 , pp. 391-406 (2011).
16.Chen, W.N., Zhang, J., Chung, H.S., Huang, R.Z., and Liu, O., “Optimizing Discounted Cash Flows in Project Scheduling-An Ant Colony Optimization Approach,” IEEE Transactions on system, Vol. 40, No.1 (2010).
17.Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M. and Soumis, F., “Daily aircraft routing and scheduling,” Management Science, Vol. 43, pp. 841-855 (1997).
18.Garey, M. R. and Johnson, D.S., “Computers and intractability: a guide to the theory of NP-completeness,” San Francisco, CA: Freeman (1979).
19.Hartmann, S., “Project scheduling with multiple modes - A genetic algorithm,” Annals of Operations Research, Vol. 102, No.1-4, pp. 111-135 (2001).
20.Icmeli, O., and Erenguc, S.S., “The resource constrained time cost tradeoff project scheduling problem with discounted cash flows,” Journal of Operations Management, Vol. 14, pp. 255-275 (1996).
21.Kolisch, R., Sprecher, A. and Drexl, A., “Characterization and generation of a general class of resource-constrained project scheduling problems, ” Management Science Vol. 41, pp. 1693–1703 (1995).
22.Levin, A., “Some fleet routing and scheduling problems for air transportation systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA (1969).
23.Lai, M. F. and Lo, H. K., “Ferry service network design: Optimal fleet size, routing, and scheduling,” Transportation Research Part A, Vol. 38, pp. 305-328 (2004).
24.Mesquita, M. and Paixao, J., “Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithm,” in Desrochers, M. and Rousseau, J. M.(eds.), Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195 (1992).
25.Mika, M., Waligora, G., and Węzglarz, J., “Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models,” European Journal of Operational Research, Vol. 164, Issue. 3, pp. 639-668 (2005).
26.Ozdamar, L., Dundar, H., “A flexible heuristic for a multi-mode capital constrained project scheduling problem with probabilistic cash inflows,” Computers and Operations Research, Vol. 24, Issue. 12, pp. 1187-1200 (1997).
27.Ozdamar, L. “A genetic algorithm approach to a general category project scheduling problem,” IEEE Transactions on system, Man, and Cybernetics, Part C, Vol. 29, pp. 44-59 (1999).
28.Powell, W.B. and Ioannis, A.K., “Shipment routing algorithms with tree constraints,” Transportation Science, Vol. 26, pp. 230-245 (1992).
29.Russell, A.H., “Cash flows in networks,” Management Science, Vol.16, pp.357-373 (1970).
30.Sepil, C. And Ortac, N., “Performance of the heuristic procedures for constrained projects with progress payments,” Journal of the Operational Research Society , Vol. 48, pp.1123-1130 (1997).
31.Teodorovic, D. and Guberinic, S., “Optimal dispatching strategy on an airline network after a schedule perturbation,” European Journal of Operational Research, Vol. 15, pp. 178-182 (1984).
32.Teodorovic, D., Airline Operations Research, Gordon and Breach Science Publishers, New York (1988).
33.Ulusoy, G., and Cebelli, S., “An equitable approach to the payment scheduling problem in project management,” European Journal of Operational Research, Vol. 127, pp. 262-278 (2000).
34.Ulusoy, G., Sivrikaya-S_erifo_glu, F., S_ahin, S., “ Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows, ” Annals of Operations Research, Vol. 102 ,pp. 237–261 (2001).
35.Wang, D. Z. W. and Lo, H. K., “Multi-fleet ferry service network design with passenger preferences for differential services,” Transportation Research Part B, Vol. 42, pp. 798-822 (2008).
36.Yang, K.K., Talbot, F.B. and Patterson, J H., “Scheduling a project to maximize its net present value: An integer programming approach,” European Journal of Operational Research, Vol. 64, pp. 188-198 (1993).
37.Yan, S. and Young, H. F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,” Transportation Research, Vol. 30A, pp. 379-398 (1996).
38.Yan, S. and Chen, H. L., “A Scheduling Model and a Solution Algorithm for Inter-city Bus Carriers,” Transportation Research, Vol. 36A, pp. 805-825 (2002).
39.Yan, S. and Tseng, C.H., “A passenger demand based model for airline flight scheduling and fleet routing,” Computers and Operations Research, Vol. 29, pp. 1559-1581 (2002).
40.Yan, S., Chi, C. J. and Tang, C. H., “Inter-city Bus Routing and Timetable Setting under Stochastic Demands,” Transportation Research, Vol. 40A, pp.572-586 (2006).
41.Yan, S. and Shih, Y. L., “A Time-Space Network Model for Work Team Scheduling after a Major Disaster,” Journal of the Chinese Institute of Engineers, Vol. 30, No. 1, pp. 63-75 (2007)
42.Yan, S. and Chen, C. H., “Coordinated flight scheduling models for allied airlines,” Transportation Research Part C, Vol. 15, pp. 246-264 (2007).
43.Yan, S. and Tang, C. H., “A heuristic approach for Airport Gate Assignments for Stochastic Flight Delays,” European Journal of Operational Research, Vol. 180, Issue 2, pp. 547-567 (2007).
44.Yan, S., Lai, W., and Chen, M., “Production scheduling and truck dispatching of ready mixed concrete,” Transportation Research, Part E, Vol. 44, Issue 1, pp. 164-179 (2008a).
45.Yan, S., Tang, C.H., and Fu, T.C., “An airline scheduling model and solution algorithms under stochastic demands,” European Journal of Operational Research, Vol. 190, pp. 22-39 (2008b).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔