多重作業方式及資源限制下最大淨現值專案排程模式暨求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：18.221.187.121

姓名

劉秋蘭(Chiu-lan Liu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

多重作業方式及資源限制下最大淨現值專案排程模式暨求解演算法之研究
(Multi-mode resource constrained project scheduling model to maximize net present value and a Solution Algorithm)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在全球化經濟快速發展下，企業為求得生存與發展需更有效地利用有限的資源、盡量縮短專案時間週期及降低作業成本，以求得最大的利潤。然而隨著專案規模的迅速成長，專案排程問題牽涉的相關因素逐漸複雜。雖然過去的專案排程有利用要徑法與計畫評核術進行專案作業排程，但是近幾年來因環境資源匱乏，單憑考量時程的控管而未考量有限的資源，則決策缺乏整體最佳化分析，常非最佳及最有效率之決策。若能將資源限制及不同作業方式等因素加以考量，並建立決策模式，則可望幫助決策者有效地求解此類複雜的專案作業排程。
本研究針對多重作業方式及資源限制下最大淨現值專案排程問題，考量現金流量時間價值及相關作業流程與資源限制，利用時空網路流動技巧及數學規劃方法構建一數學模式，以整合有限的資源規劃專案作業排程。此模式為一含額外限制整數網路流動問題，可以利用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.

關鍵字(中)

★ 多重作業方式及資源限制下之專案排程
★ 淨現值
★ 時空網路
★ 含額外限制整數網路流動問題

關鍵字(英)

★ MRCPSPDCF
★ net present value
★ time-space network
★ integer network flow problem with side constrain

論文目次

目錄
摘要 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).

指導教授

顏上堯(Shang-yao Yan)

審核日期

2011-8-3

推文