應用兩階層規劃求解多模式資源受限的多專案排程問題

Solving the Multi-mode Resource-constrained Multi-project Scheduling Problem by Bi-level Programming

駱巧瑜(Chiao-Yu Lo)

指導教授 ： 鄭啟斌

淡江大學/商管學院/資訊管理學系碩士班/碩士(2014年)

https://doi.org/10.6846/TKU.2014.00024

摘要

實務上，專案管理通常是在多專案且資源受限的情況下進行，而資源使用的方式也非單一的，舉例而言，某作業可透過資源之不同組合而改變其完工時間。本研究所考慮的即是在多模式資源限制下的多專案排程問題。以往大多數的多專案排程研究假設資源可在專案間共享，因此多專案可合併為單一專案以求解排程問題。本研究所考慮的則是資源不可共享的情境，因此須先決定資源在各專案間之分配。當資源分配至各專案後，各專案管理者所面對的即為一典型的多模式資源限制專案排程問題。觀察此一決策架構，本研究擬以兩階層分散式規劃來建模此決策問題。在求解方法上，考慮到專案之資源使用實為一資源組合的問題，因此本研究提出以組合拍賣的機制來決定資源在各專案間的配置。其中，低階決策者(亦即專案經理人)藉由假設不同交期要求的條件下，求解其完成專案所需之最低成本的資源組合，並以這些組合連同其可達成之完工時間作為標案，提交給高階決策者。高階決策者則針對所有低階決策者所提之標案，求解一贏家決定問題，以決定資源在各專案間之配置。本研究並提出一模糊組合拍賣模型，以解答當總資源不足時，如何擴充資源以改善專案之延遲情況。本研究以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.

並列關鍵字

Multi-project scheduling ； Multi-mode resource-constrained project scheduling problem ； Bi-level decentralized programming ； Combinatorial auction ； Fuzzy programming

參考文獻

[3] 吳鴻君. (2011). 台灣電視廣告市場之組合拍賣機制設計. 淡江大學資訊管理學系碩士班學位論文, 1-86.

[6] 陳柏宇. (2011). 台灣廢印表機回收費率制定問題之探討─ 兩階層規劃之 Kkt 條件與直覺模糊趨近法之比較. 淡江大學管理科學研究所碩士班學位論文, 1-90.

[7] 許珀銜. (2011). 應用兩階層規劃於提升台灣廢主機回收率之研究. 淡江大學管理科學研究所碩士班學位論文 , 1-85.

[5] 張亦寬. (2003). 以雙層次數學規劃建構旅客需求導向之票價設計模式-以台灣高鐵為例. 成功大學. 交通管理學系, 碩士, 92

[9] 廖慧凱(2006). 道路災害搶修與緊急物流配送問題之探討. 國立中央大學. 土木工程學系, 碩士, 95