資源限制專案排程問題財務風險最小化之研究

FINANCIAL MODELS FOR RESOURCE-CONSTRAINED PROJECT SCHEDULING ON PROJECT CASH AVAILABILITY

陳芝傑(Zhi-Jie Chen)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/博士(2012年)

https://doi.org/10.6838/YZU.2012.00069

摘要

在實務上，專案的執行也伴隨著專案中各個作業現金的進出（cash in- and out-flows），論文的目的即為降低資源限制專案排程問題（resource-constrained project scheduling problem, RCPSP）於專案執行時的財務風險。研究提出的最大化專案現金可用量問題（project cash availability maximization problem, PCAMP）中，每個作業完成時會得到對應的現金收入並可在專案結束之前被運用，因而，作業的現金－時間值（money-time value）即為作業的現金流入值乘上作業完成時間到專案結束的時間區間值，專案的現金可用量（cash availability）之計算則為所有作業現金－時間值的總和，其提供一保守的現金可用量估計，因在多數情形，如利息，現金會隨著時間的進行而變動。
　　第三章提出三個演算法求解處理單組態的PCAMP模式，分別為GRASP（greedy randomized adaptive search procedure）、MA（memetic algorithm）和VNS（variable neighborhood search）。對於每一個演算法，求解的機制與發展皆由標竿測試題進行分析與比較，而最好的結果將作為此演算法的代表與其他兩者相較。基於最後的結果：GRASP為reactive GRASP結合長期記憶表單（long term memory list）與路徑重連（path relinking）技巧；MA則有兩個，一者為結合GRASP產生初始母體與轉進（restart）母體，另一則使用regret biased sampling產生；VNS的代表則為double VNS （DVNS），其採用一小型的VNS作為每個鄰近解的區域搜尋方式。實驗分析採用以ProGen產生的標竿測試題做為比較分析，其結果顯示結合GRASP的混合MA演算法在各個求解品質之中皆表現最佳，而DVNS則最省計算時間。
　　第四章在於求解多組態的PCAMP，研究提出一兩階段的求解方式，第一階段在於決定各作業的組態指派且滿足專案交期與資源限制，找到最小專案執行成本的排程，此專案執行成本來自各作業執行組態的成本總和，而第二階段則在此組態固定之下，以第三章的模式與演算法求解對應的單組態PCAMP。因而，第四章主要目的即在於求解第一階段的問題。此章提出三個演算法，分別是 (1) BBMA：branch and bound procedure用於決定專案組態指派，而MA則求解某專案組態指派下的單組態問題，並將結果回饋予branch and bound procedure。 (2) DPMA：其包含了兩個步驟，前置步驟（preprocessing）以較短暫的BBMA篩選出個體進入母體，接著以兩個母體進行演化步驟。(3) SA-MA：此方法以多重啟始（multi-start）的方式尋找，每一次開始，每個啟始解，SA皆以CPLEX決定符合不可恢復資源限制的背包問題用以決定啟始的專案組態，如BBMA，SA用於決定組態，而MA求解對應的單組態排程問題。三個演算法的評估採用ProGen與RanGen兩個標竿測試題產生器，對於中小型的題目，以BBMABB求得最佳解與與各演算法相較，而大型問題則與CPLEX取得的下限值做為比較基準，並進一步與一目前知名的演算法BPGA（bi-population genetic algorithm），唯BPGA在原文是用以求解多組態最小化專案完工時間問題。實驗結果顯示BBMA在中小型測試題中表現良好，而SA-MA提供一比較的基準並在大型題目的表現上則優於其他演算法。

關鍵字

資源限制專案排程 ； 多組態 ； 現金可用量 ； 萬用啟發式演算法 ； 瀰集進化演算法 ； 混合式方法 ； 最佳解法 ； 區域搜尋法

並列摘要

In practice, a project usually involves cash in- and out-flows associated with each activity. This thesis aims to minimize the risk of payment failure during project execution for the resource-constrained project scheduling problem (RCPSP), where the net cash in-flow occurs at the completion time of each activity, and this cash amount can be used during the rest of project execution time. To achieve this goal, the money-time value, which is the product of the cash in-flow and the length from the time the cash received to the project makespan, can provide a financial evaluation of project cash availability. The cash availability of a project schedule is then defined as the sum of these money-time values associated with all activities. The metric provides a conservative estimate of cash in-flows during the project execution, since cash on hand will grow in value over time. Using this metric will not only reduce the model complexity, but also serve as a cautious model to minimize the financial risk during the project makespan. We shall refer to the problem under study as the project cash availability maximization problem (PCAMP).
Chapter 3 deals with the PCAMP for the single-mode RCPSP. Three solution approaches are presented – greedy randomized adaptive search procedure (GRASP), memetic algorithm (MA), and variable neighborhood search (VNS). For each solution approach, several algorithms were developed and compared to each other through benchmark instances. The most effective methods in each solution approach are then selected for further comparison. As a consequence, four algorithms are selected: (1) reactive GRASP which combines the use of long term memory list and path relinking post-optimization technique; (2) two hybrid MAs, one using regret biased sampling rule to generate initial and restart populations and the other using GRASP to generate both populations; (3) double variable neighborhood search (DVNS) which uses a small version of VNS as the local search method. An experiment is conducted to evaluate the performance of these algorithms based on the same number of solutions using ProGen generated benchmark instances. The results indicate that the hybrid MA with GRASP achieves the best performance in terms of solution quality, whereas DVNS is efficient in producing promising results
Chapter 4 focuses on solving the PCAMP for the multi-mode RCPSP (MRCPSP). A two-phase approach is proposed to solve this problem: Phase 1 aims to find a minimum-cost project mode that contains a resource-feasible schedule with makespan no greater than a specified time constraint (deadline); Phase 2 solves the PCAMP for the selected single mode RCPSP. The algorithms introduced in chapter 3 can be used in phase 2. Thus, the focus of Chapter 4 will be on solving the Phase 1 problem. Three hybrid methods are presented: (1) the first method incorporates a branch-and-bound scheme with a memetic algorithm (BBMA); (2) the second method consists of two phases: a truncated BBMA for preprocessing and an integration approach termed “DPMA” for population evolution; (3) the third method is a multi-start hybrid meta-heuristic termed (SA-MA), where the SA searches for the lowest cost project mode and the MA determines the deadline feasibility for each selected project mode. The performance of the three hybrid algorithms on small size problems are measured against the optimal solutions found by an exact solution method termed BBMABB, which is an extension of BBMA. In addition, we also code a modified version of the state-of-the-art algorithm termed “bi-population genetic algorithm (BPGA)” for the purpose of performance comparison. The original BPGA aims to minimize the makespan of the MRCPSP. Experiments using ProGen and RanGen benchmark instances indicate that BBMA is superior to the other algorithms on small-sized problem instances, whereas SA-MA is useful in solving large-sized problem instances, as well as providing a comparison standard.

並列關鍵字

Resource constrained project scheduling ； multiple modes ； cash availability ； meta-heuristics ； memetic algorithms ； hybridization ； exact solution method ； Local search

參考文獻

Abbasi, B., Shadrokh, S., Arkat, J. (2006). Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Applied Mathematics and Computation, 180(1):146-152.

Agarwal, A., Colak, S., Erenguc, S. (2011). A neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, 38(1):44-50.

Ahmadi, S., Osman, I. H. (2005). Greedy random adaptive memory programming search for the capacitated clustering problem. European Journal of Operational Research, 162:30-44.

Akkan, C., Drexl, A., Kimms, A. (2005). Network decomposition-based benchmark results for the discrete time-cost tradeoff problem. European Journal of Operational Research, 165:339-358.

Alcaraz, J., Maroto, C. (2001). A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102:83–109.