前言 本論文以資源限制專案排程(Resource Constrained Project Scheduling; RCPSP)之理論為基礎

Presentation on theme: "前言 本論文以資源限制專案排程(Resource Constrained Project Scheduling; RCPSP)之理論為基礎"— Presentation transcript:

1 強化資源限制專案排程之 雙目標模型建立 a bi-objective model for robust resource- constrained project scheduling

2 前言 本論文以資源限制專案排程(Resource Constrained Project Scheduling; RCPSP)之理論為基礎
目的: 解決非預期因素對專案排程之影響 模型建立: 包含兩大目標的資源限制專案排程模型，稱為雙目標資源限制專案排程(Bi-Objective Resource Constrained Project Scheduling; BRCPSP) 。

3 資源限制專案排程(RCPSP) 定義: 1.在步驟J中由n個動作組成 2.動作i必須在其先行動作pi先完成後才能開始 3.有k種可恢復性資源
4.rik 代表i動作可使用的資源量 5.所耗用的資源量不可超過每一種資源可提供的使用量

4 資源限制專案排程(RCPSP) 求解方法-- 1.exact algorithms-- 例如: 分枝法(B&B)、動態規劃(DP)
2.heuristics algorithms

5 資源限制專案排程(RCPSP) RCPSP的最佳解原則-- 1. makespan minimization
2. NPV maximization 3. cost minimization

6 雙目標資源限制專案排程BRCPSP 模型建立動機— 在實務上，常存有一些非預期因素 (例如: 重工、
檢驗及修正暇疵)影響專案的完工時間並增加額外的 成本。 希望藉由雙目標資源限制專案排程模型的建立，使排程更具彈性，降低非預期因素的衝擊 以達到完工時間最小。

7 雙目標資源限制專案排程BRCPSP 雙目標定義— 1.專案工期最小化(makespan minimization) 專案工期:
專案從開始到結束所需花費的總時間 2.預防能力最大化(robustness maximization) 預防能力: 指在面對非預期因素影響下，排程能如期完成的能力 即為所有寬鬆時間的總合

8 雙目標資源限制專案排程BRCPSP 模型建構方法-- 1.exact algorithms
在多目標組合最佳化問題(MOCO)中，主要有三種求解方法: 1.exact algorithms 2.approximate algorithms 3.decision maker (DM)

9 雙目標資源限制專案排程BRCPSP 模型建構方法-- 第二種方法中的塔布搜尋法 (Tabu Search;TS) 為基礎
以修正後的MOTS (Multi-Objective Tabu Search)的演算法，求出近似有效解組合，簡稱 AE。

10 雙目標資源限制專案排程BRCPSP 建構方法—MOTS演算法 Schedule representation
Neighborhood structure Selection strategy Tabu list attributes & aspiration criterion Approximation of the efficient

11 MOTS演算法 Schedule representation Neighborhood structure
藉由SGS (schedule generation scheme)方法計算排程 將各作業的ES、EC、FS、FC、Slack time 紀錄在precedence feasible list;L Neighborhood structure 從以上的列表隨機選取N個移動路徑以產生N個鄰近解: (u=1,…,N)

12 MOTS演算法 Selection strategy Tabu list attributes 將解和解之間的移動路徑儲存在塔布列表內
藉由 公式求算每一個鄰近解的專案工期和預防能力值 :權重概念，有助於找到有效解 Tabu list attributes 將解和解之間的移動路徑儲存在塔布列表內 aspiration criterion 選擇採用塔布列表內 某些可能產生很好的解的移動路徑

13 雙目標資源限制專案排程BRCPSP 參數定義— precedence feasible list
initial schedule = j=activity approximate set tabu list Weight， v=0,1…,s s = the number of steps neighbor schedule u=1,2…,N set of neighbors neighbor schedule’s makespan neighbor schedule’s robustness new neighbor schedule 最大迭代次數

14 雙目標資源限制專案排程BRCPSP 模型介紹 1.由SGS方法 算出一初始排程 並將其紀錄在列表L中: 2.令AE， TL為空集合
3.令 v=0,…,s

15 雙目標資源限制專案排程BRCPSP 4.隨機選取N個非塔布列表內的移動路徑或符合凌駕原則的移動路徑 5.形成一個鄰近解集合 6.依據
分別去計算每一鄰近解的專案工期和預防 能力值 7.在鄰近解集合載入近似有效解組合內

16 雙目標資源限制專案排程BRCPSP 8.假定現有一新鄰近解，其所產生的結果是優於目前的最佳解，則新解取代現有的最佳解並更新塔布列表
9. 重複幾次相同動作，直到運算次數達到最大迭代次數，AE不再有任何變化時，運算即可結束

17 結論 對企業的影響— 專案工期最小化: 花最少的時間完工 快速地回應全球化競爭 預防能力最大化: 提高專案完成的穩健度 縮短工時

18 報告完畢 感謝您的聆聽