- 學位論文
兩目標資源限制專案排程問題解算之研究－最小化總完工與總權重流程時間
Multi-Objective Discrete PSO Algorithms Based on Decomposition for the Resource-Constrained Project Scheduling with Makespan and Total Weighted Flow Time Criteria
摘要
在實務中，專案經理人考慮之專案排程問題目標往往是多方面，這些目標尤以專案執行時間長短最為重要，此因素攸關專案執行效率。本研究即以此因素做為考量，具代表性目標為專案完工時間 (project makespan)；同時也考慮專案作業之重要程度，優先考量其關鍵作業之完工時間，此目標為總權重流程時間 (total weighted flow time)。因此本研究所求解專案排程問題即為兩目標之最小化。 本研究提出兩個離散化粒子群演算法 (D-PSO及W-PSO) 求解此問題，兩者分別參考二進制PSO (BPSO) 及慣性權重PSO (IWA-PSO) 之概念。演算法之測試題採用國際測試題庫PSPLIB，其測試題皆由標準專案產生器ProGen產生。研究中設計多項實驗進行檢測，並建立雙目標整數規劃模式，採取逐步增加完工期限限制方式使用Gurobi最佳化軟體求解小型問題之柏拉圖前緣。實驗以各演算法對每題測試題進行10次演算。 實驗包含檢測學習因子參數、個體粒子最佳解選擇策略、初始母體產生策略及區域搜尋法。實驗中顯示學習因子 (c1, c2) = (3, 2) 演算效果最佳；個體粒子採用混和策略效果較好，此策略令粒子分別使用線性權重、柴比雪夫權重(weighted Tchebycheff)、nadir distance及hyper volume ratio法；D-PSO之初始母體產生策略應為隨機選擇法 (random)，W-PSO則以權重抽樣最短作業時間 (WSSPT) 較佳，且兩者中DPSO-random略顯較好；區域搜尋法則以D-PSO採用機率式選擇法 (DPSO-Prob.) 為最佳。
並列摘要
Over the years, the project scheduling problem has been intensively studied due to its broad applications in industry and business society. Some of the examples are software development, construction planning, production manufacturing, and research and development. Most of these studies focus on resource constrained project schedule problems (RCPSP) with a single objective, mainly on time and finance related aspects such as project makespan and net present value. However, in practical situations, management concerns are often multi-fold. This research presents a discrete version of particle swarm optimization algorithm (D-PSO) for the RCPSP with the objective of simultaneously minimizing makespan and total weighted flow time. The former endeavors to complete the project within a short time, and the latter attempts to finish important activities at possibly early times. The proposed D-PSO algorithm was developed using the ideas of Binary PSO (Kennerdy and Eberhart 1997) and decomposition approach (Zhang and Li 2007). Each particle in the population aims to search optimally the solution subspace of the bi-objective RCPSP. Four types of search directions are considered: linear weighted and Tchebycheff weighted metric methods, hyper-volume ratio, and nadir distance. The performance of the D-PSO algorithms are compared with another discrete version of inertia weight PSO using the benchmark instances of problem sizes j20, j30, and j60 activities in the PSPLIB. In order to evaluate the performance of these algorithms based on optimal Pareto front, a mathematical formulation of the bi-objective RCPSP was developed and used with the commercial software Gurobi to optimally solve all j20 instances and j30 easy instances. For difficult j30 instances and j60 instances, the performance evaluations are based on the best non-dominated front formed by all algorithms. The numerical results indicate that the proposed D-PSO performs best in terms of metrics such as Purity, Error ratio, Generational distance, Nadir distance, and Hyper-volume. For small and easy problems, the D-PSO often achieves the same optimal solutions as obtained by Gurobi, but the D-PSO uses much less computation time. In addition, four local search methods are studied and compared: forward backward improvement (FBI), insertion (INS), biased sampling selection, and both FBI and INS. Our numerical results show that biased sampling selection outperforms the others.
參考文獻
延伸閱讀
- 雷鵬遠（2007）。多組態資源限制專案排程-最小成本組態選擇問題解算之研究〔碩士論文，元智大學〕。華藝線上圖書館。https://doi.org/10.6838/YZU.2007.00137
- Fakhrzad, M. B., & Heydari, M. (2008). 啟發式演算法求解混合式流程生產排程之最小化總提早及遲延成本. 工業工程學刊, 25(2), 105-115. https://doi.org/10.29977/JCIIE.200803.0002
- （2006）。雙機流程型工廠在無等待時間且單一設置人員下之總完工時間最小化排程問題〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200600534
- Allahverdi, A. (2008). 具設置及加工時間界限之三機台流程式排程問題之最後完工時間最小化. 工業工程學刊, 25(1), 52-61. https://doi.org/10.29977/JCIIE.200801.0006
- Hsieh, S. Y. (2014). The Design and Analysis of Deploying Algorithms along with Optimization Methods for the Long Term Evolution Heterogeneous Networks [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2014.02931