淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0107201418124500
中文論文名稱 應用兩階層規劃求解多模式資源受限的多專案排程問題
英文論文名稱 Solving the Multi-mode Resource-constrained Multi-project Scheduling Problem by Bi-level Programming
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 102
學期 2
出版年 103
研究生中文姓名 駱巧瑜
研究生英文姓名 Chiao-Yu Lo
學號 601630774
學位類別 碩士
語文別 中文
口試日期 2014-06-21
論文頁數 56頁
口試委員 指導教授-鄭啟斌
委員-蕭育如
委員-張昭憲
委員-鄭啟斌
中文關鍵字 多專案排程  多模式資源限制排程問題  兩階層分散式規劃  組合拍賣  模糊規劃 
英文關鍵字 Multi-project scheduling  Multi-mode resource-constrained project scheduling problem  Bi-level decentralized programming  Combinatorial auction  Fuzzy programming 
學科別分類
中文摘要 實務上,專案管理通常是在多專案且資源受限的情況下進行,而資源使用的方式也非單一的,舉例而言,某作業可透過資源之不同組合而改變其完工時間。本研究所考慮的即是在多模式資源限制下的多專案排程問題。以往大多數的多專案排程研究假設資源可在專案間共享,因此多專案可合併為單一專案以求解排程問題。本研究所考慮的則是資源不可共享的情境,因此須先決定資源在各專案間之分配。當資源分配至各專案後,各專案管理者所面對的即為一典型的多模式資源限制專案排程問題。觀察此一決策架構,本研究擬以兩階層分散式規劃來建模此決策問題。在求解方法上,考慮到專案之資源使用實為一資源組合的問題,因此本研究提出以組合拍賣的機制來決定資源在各專案間的配置。其中,低階決策者(亦即專案經理人)藉由假設不同交期要求的條件下,求解其完成專案所需之最低成本的資源組合,並以這些組合連同其可達成之完工時間作為標案,提交給高階決策者。高階決策者則針對所有低階決策者所提之標案,求解一贏家決定問題,以決定資源在各專案間之配置。本研究並提出一模糊組合拍賣模型,以解答當總資源不足時,如何擴充資源以改善專案之延遲情況。本研究以ILOG CPLEX 12.5.1.0提供的JAVA API實作求解演算法,並以文獻中之問題集測試本研究所提方法之績效。實驗結果顯示本研究方法之績效不但可與文獻中之方法相抗衡,且在運行時間上遠低於文獻中之方法。
英文摘要 In practice, project management is often performed in a multi-project context, where individual projects compete for source resources. Moreover, the activities in a project could be accomplished in one out of several execution modes, in which, each execution mode represents an alternative combination of resource requirement of the activity and its duration. This study aims to deal with such a multi-project, multi-mode, and resource-constrained project scheduling problem. Previous studies on multi-project scheduling problems generally assumed that resources can be shared among projects, and thus, the multiple projects can be combined into a single project, and solved by available algorithms that are formulated for single project scheduling. The present study considers a different case where resources cannot be shared among projects and hence the resources need to be allocated to individual projects; after the resources are allocated to each project, the project manager of each project faces a typical multi-mode resource constrained project scheduling problem. Owing to the above hierarchical decision-making structure, this study suggests using the bi-level decentralized programming to model the problem. The resources used in a project in fact is a combination of various resources. Thus, it is ideal to allocate resources to projects in a combinatorial manner. Combinatorial auction is suitable for dealing with such a problem. In the combinatorial action mechanism considered in this study, upper-level decision-maker is the auctioneer and the project managers at the low-level are bidders. Project managers submit bids, which are in the form of resource combination and are obtained by solving a least-cost multi-mode resource-constrained projects scheduling problem, to the upper-level decision-maker. After receiving all bids from project managers, the upper-level decision-maker solves a winner determination problem to determine the winning bids which represent the result of the resource allocation decision. In addition to the regular combinatorial auction model, this study proposes a fuzzy combinatorial auction model to deal with the situation where the resources are not enough to complete projects by their due dates. The solution of the fuzzy combinatorial auction model shows the trade-off between resource expansion and tardiness improvement. The proposed solution procedure is programmed by JAVA with CPLEX library, and uses problem instances of Besikci et al. (2013) to evaluate the performance of the proposed approach. The results show the solutions of our approach not only able to compete with that of literature, and outperform the literature in computation times.
論文目次 目錄
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究方法 3
1.3 研究目的 5
1.4 研究範圍與限制 6
1.5 研究架構 8
第2章 文獻探討 9
2.1 多模式資源限制多專案排程問題 9
2.1.1 多模式資源限制單專案排程問題 11
2.1.2 多專案排程問題 12
2.2 兩階層規劃問題 14
2.3 模糊規劃 17
2.4 組合拍賣機制 19
第3章 多專案多模式專案排程模型 21
3.1 多模式資源限制單專案排程 21
3.2 多模式資源限制多專案排程 23
第4章 求解演算法 28
4.1 以組合拍賣機制決定資源配置 28
4.1.1 標案制定問題 29
4.1.2 贏家決定問題 31
4.2 模糊組合拍賣 32
4.3 求解演算法例示 36
4.3.1 範例說明 36
4.3.2 範例求解 38
第5章 方法驗證 41
第6章 結論 47
6.1 研究發現 48
6.2 未來研究方向 48
參考文獻 50

表目錄
表4-1專案P在不同交期下的標案 30
表4-2高階各專案及資源資料表 37
表4-3個別專案資源使用模式與對應時程 38
表4-4專案P=1, 2, 3在不同交期下的標案 39
表5-1 專案權重及到期日 42
表5-2 T值對計算時間之影響 43
表5-3 專案含22個作業的題組 44
表5-4專案含32個作業的題組 44

圖目錄
圖2-1有限資源專案排程問題分類圖 10
圖4-1 隸屬函數 (A)可恢復資源 (B)不可恢復資源 (C)延遲時間 33
圖4-2 求解流程圖 36
圖4-3個別專案網路圖 37

參考文獻 參考文獻
[1] 王嘉男, & 朱彥貞. (2014). 專案管理. 科學發展, (494), 64-70.
[2] 吳忠倫. (2009). 以粒子群優化法求解多模資源受限的專案排程問題. 國立勤益科技大學. 電子工程系, 碩士, 98.
[3] 吳鴻君. (2011). 台灣電視廣告市場之組合拍賣機制設計. 淡江大學資訊管理學系碩士班學位論文, 1-86.
[4] 李曉蘋. (2002). 公營汽車客運業者面臨破產因應對策之研究.逢甲大學. 交通工程與管理學系, 碩士, 91.
[5] 張亦寬. (2003). 以雙層次數學規劃建構旅客需求導向之票價設計模式-以台灣高鐵為例. 成功大學. 交通管理學系, 碩士, 92
[6] 陳柏宇. (2011). 台灣廢印表機回收費率制定問題之探討─ 兩階層規劃之 Kkt 條件與直覺模糊趨近法之比較. 淡江大學管理科學研究所碩士班學位論文, 1-90.
[7] 許珀銜. (2011). 應用兩階層規劃於提升台灣廢主機回收率之研究. 淡江大學管理科學研究所碩士班學位論文 , 1-85.
[8] 詹蕙珍(2004)。模糊多目標非線性規劃在有限資源多專案排程問題之應用. 屏東科技大學. 工業管理系, 碩士, 79.
[9] 廖慧凱(2006). 道路災害搶修與緊急物流配送問題之探討. 國立中央大學. 土木工程學系, 碩士, 95
[10] 蔡登茂. (1996). 有限資源專案排程問題之文獻回顧研究. 正修學報, (9), 57-74.
[11] 鄭有原. (2005). 考慮資源型態之營建有限資源多專案排程模式. 雲林科技大學. 營建工程系碩士班, 碩士, 106.
[12] 謝穎欣. (2005). 應用田口方法於基因演算法輸入參數設計--以求解多模式專案排程下資源撫平為例. 國立中央大學. 工業管理研究所, 碩士, 77.
[13] Alcaraz, J., Maroto, C., & Ruiz, R. (2003). Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of the Operational Research Society, 54(6), 614-626.
[14] Anandalingam, G. (1988). A mathematical programming model of decentralized multi-level systems. Journal of the Operational Research Society, 1021-1033.
[15] Bard, J. F. (1983). Coordination of a multidivisional organization through two levels of management. Omega, 11(5), 457-468.
[16] Bard, J. F., Plummer, J., & Claude Sourie, J. (2000). A bilevel programming approach to determining tax credits for biofuel production. European Journal of Operational Research, 120(1), 30-46.
[17] Bellman, R. E., & Zadeh, L. A. (1970). Decision-making in a fuzzy environment. Management Science, 17(4), B-141-B-164.
[18] Ben-Ayed, O., Boyce, D. E., & Blair III, C. E. (1988). A general bilevel linear programming formulation of the network design problem. Transportation Research Part B: Methodological, 22(4), 311-318.
[19] Beşikci, U., Bilge, U., & Ulusoy, G. (2013). Resource dedication problem in a multi-project environment. Flexible Services and Manufacturing Journal, 25(1-2), 206-229.
[20] Boctor, F. F. (1993). Heuristics for scheduling projects with resource restrictions and several resource-duration modes. The International Journal of Production Research, 31(11), 2547-2558.
[21] Bouleimen, K., & Lecocq, H. (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149(2), 268-281.
[22] Brucker, P., Drexl, A., Mohring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3-41.
[23] Candler, W., and Norton, R. (1977). Multilevel Programming. Tech. Rep. 20. World Bank Development Research Center, Washington D.C.
[24] Chain, C., & Goldratt, E. M. (1997). North river press. Great Barrington, MA, USA,
[25] Cheng, C. (2011). Reverse auction with buyer–supplier negotiation using bi-level distributed programming. European Journal of Operational Research, 211(3), 601-611.
[26] Cheng, C., Lai, Y., & Chan, K. (2011). Solving a reverse auction problem by bi-level distributed programming and genetic algorithm. International Journal of Revenue Management, 5(2), 234-260.
[27] Cleland, D. I.、Ireland, L. R.、Ireland, L.(2000)。Project manager's portable handbook McGraw Hill.
[28] De Vries, S., & Vohra, R. V. (2003). Combinatorial auctions: A survey. INFORMS Journal on Computing, 15(3), 284-309.
[29] Gido, J., & Clements, J. P. (2008). Successful project management South-Western College Publishing.
[30] Goldratt, E. M.(1997)。Critical chain North River Pr.
[31] Goncalves, J. F., Mendes, J. J., & Resende, M. G. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189(3), 1171-1190.
[32] Hannan, E. L. (1981). Linear programming with multiple fuzzy goals. Fuzzy Sets and Systems, 6(3), 235-248.
[33] Hans, E. W., Herroelen, W., Leus, R., & Wullink, G. (2007). A hierarchical approach to multi-project planning under uncertainty. Omega, 35(5), 563-577.
[34] Hartmann, S. (2001). Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 102(1-4), 111-135.
[35] Jozefowska, J., Mika, M., Rożycki, R., Waligora, G., & Węglarz, J. (2001). Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102(1-4), 137-155.
[36] Kalashnikov, V., Dempe, S., Perez-Valdes, G., and Kalashnykova, N. (2011). Natural gas cash-out problem: solution with bilevel programming tools. The Clute Institute International Academic Conferences. Retrieved 2011-05-30, from http://www.cluteonline.com/conferences/index.php/IAC/2011NO/paper/view/338.
[37] Kelley, J. E. (1963). The critical-path method: Resources planning and scheduling. Industrial Scheduling, 13, 347-365.
[38] Khatibi, V., & Montazer, G. A. (2009). Intuitionistic fuzzy set vs. fuzzy set application in medical pattern recognition. Artificial Intelligence in Medicine, 47(1), 43-52.
[39] Kim, S., & Leachman, R. C. (1993). Multi-project scheduling with explicit lateness costs. IIE Transactions, 25(2), 34-44.
[40] Kolisch, R., & Padman, R. (2001). An integrated survey of deterministic project scheduling. Omega, 29(3), 249-272.
[41] Kolisch, R., & Sprecher, A. (1996). PSPLIB—A project scheduling problem library. European Journal of Operational Research, 96, 205-216.
[42] Kolisch, R., Sprecher, A., & Drexl, A. (1995). Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, 41(10), 1693-1703.
[43] Kurtulus, I. S., & Narula, S. C. (1985). Multi-project scheduling: Analysis of project performance. IIE Transactions, 17(1), 58-66.
[44] Lai, Y. (1996). Hierarchical optimization: A satisfactory solution. Fuzzy Sets and Systems, 77(3), 321-335.
[45] Lawrence, S. R., & Morton, T. E. (1993). Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics. European Journal of Operational Research, 64(2), 168-187.
[46] Leberling, H. (1981). On finding compromise solutions in multicriteria problems using the fuzzy min-operator. Fuzzy Sets and Systems, 6(2), 105-118.
[47] Lewis, J. P. (2005). Project planning, scheduling, and control McGraw-Hill.
[48] Liberatore, M. J., Pollack-Johnson, B., & Smith, C. A. (2001). Project management in construction: Software use and research directions. Journal of Construction Engineering and Management, 127(2), 101-107.
[49] Liberatore, M. J., & Titus, G. J. (1983). The practice of management science in R&D project management. Management Science, , 962-974.
[50] Liu, Y., & Hart, S. M. (1994). Characterizing an optimal solution to the linear bilevel programming problem. European Journal of Operational Research, 73(1), 164-166.
[51] Lova, A., Maroto, C., & Tormos, P. (2000). A multicriteria heuristic method to improve resource allocation in multiproject scheduling. European Journal of Operational Research, 127(2), 408-424.
[52] Lova, A., Tormos, P., Cervantes, M., & Barber, F. (2009). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2), 302-316.
[53] Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. Evolutionary Computation, IEEE Transactions on, 6(4), 333-346.
[54] Mieritz, L. (2012). Gartner survey shows why projects fail. Retrieved JUNE 10, 2012, from http://thisiswhatgoodlookslike.com/2012/06/10/gartner-survey-shows-why-projects-fail/
[55] Mori, M., & Tseng, C. C. (1997). A genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operational Research, 100(1), 134-141.
[56] Payne, J. H. (1995). Management of multiple simultaneous projects: A state-of-the-art review. International Journal of Project Management, 13(3), 163-168.
[57] Pekeč, A., & Rothkopf, M. H. (2003). Combinatorial auction design. Management Science, 49(11), 1485-1503.
[58] Pritsker, A. A. B., Waiters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16(1), 93-108.
[59] Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998). Computationally manageable combinational auctions. Management Science, 44(8), 1131-1147.
[60] Shih, H., Lai, Y., & Stanley Lee, E. (1996). Fuzzy approach for multi-level programming problems. Computers & Operations Research, 23(1), 73-91.
[61] Sprecher, A., Hartmann, S., & Drexl, A. (1997). An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19(3), 195-203.
[62] Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197-1210.
[63] TANAKA, H., OKUDA, T., & ASAI, K. (1974). On fuzzy mathematical programming. Journal of Cybernetics, 3(4), 37-46.
[64] Tseng, C. (2008). Two heuristic algorithms for a multi-mode resource-constrained multi-project scheduling problem. Journal of Science and Engineering Technology, 4(2), 63-74.
[65] Tsubakitani, S., & Deckro, R. F. (1990). A heuristic for multi-project scheduling with limited resources in the housing industry. European Journal of Operational Research, 49(1), 80-91.
[66] Wen, U., & Hsu, S. (1991). Linear bi-level programming problems--A review. Journal of the Operational Research Society, 125-133.
[67] Werners, B. (1987). An interactive fuzzy programming system. Fuzzy Sets and Systems, 23(1), 131-14
[68] Zimmermann, H. (1978). Fuzzy programming and linear programming with several objective functions. Fuzzy Sets and Systems, 1(1), 45-55.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-07-02公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-07-02起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信