(54.236.58.220) 您好!臺灣時間:2021/03/01 00:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:簡佑丞
研究生(外文):Yu-Cheng Chien
論文名稱:結合啟發式演算法於雙重粒子群優化法求解多模式專案排程之研究與實例應用
論文名稱(外文):Dual Particle Swarm Optimization with Heuristics for Multi-mode Project Scheduling Problem and Application Study
指導教授:陳瑞茂
指導教授(外文):Ruey-Maw Chen
學位類別:碩士
校院名稱:國立勤益科技大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:66
中文關鍵詞:多模式資源有限之專案排程問題超啟發式演算法粒子群優化法随機鏈結拓撲
外文關鍵詞:Multi-mode resource-constrained project scheduling problem (MRCPSP)metaheuristicparticle swarm optimization (PSO)rand-link topology
相關次數:
  • 被引用被引用:0
  • 點閱點閱:228
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:37
  • 收藏至我的研究室書目清單書目收藏:0
多模式資源受限之專案排程問題(Multi-mode Resource-Constrained Project Scheduling Problem, MRCPSP)是一項複雜的專案排程問題,並且此問題已被證實為NP-hard組合式問題。近年來,超啟發式演算法(Meta-heuristics)已被廣泛的應用於求解各種NP-hard問題上,同時,在求解MRCPSP問題中,MRCPSP可以被視為兩種子問題,其一為模式分配問題,另一為活動優先順序問題。因此本文欲藉由雙重粒子群演算法(Particle Swarm Optimization, PSO)求解MRCPSP這兩種子問題。
本文中,我們使用標準粒子群優化法(standard PSO)中收縮版本的速度更新規則,而非原始的PSO所使用之速度更新方式,同時,應用離散版本的粒子群演算法(discrete PSO)於解決模式分配的子問題。此外,我們提出一種新的群體溝通拓撲,該拓撲用於粒子的群體經驗,使其降低傳統粒子收斂速度緩慢及過快的情形,此溝通模型的拓撲結構命名為隨機鏈結(rand-link)。除此之外,本文結合兩種基於模式和活動優先權規則的啟發式演算法(Heuristics)於幫助粒子群優化法的產生更好的初始解。
首先,本論文將針對著名的benchmark進行模擬測試,該問題即PSPLIB中的MRCPSP例題。之後再應用此最佳化演算法於人力資源規畫的專案排程問題中。在現實世界中,人力資源規劃的專案排程問題與MRCPSP的種種條件限制如出一轍,因此,我們使用本文的方法並以半人-工(half-man-day)當作資源單位的方式找出最佳的人力資源需求量。模擬結果表明,本論文提出的方法能提供一個有效且有效率的解決現實世界中的人力資源規劃問題。
A multi-mode resource-constrained project scheduling problem (MRCPSP) is a complex project scheduling problem which has been confirmed to be an NP-hard combinatorial problem. Recently, meta-heuristic schemes have been widely applied to solve various NP problems. Basically, solving MRCPSPs can be regarded as solving two sub-problems; mode assignment and activity priority determination sub-problems. Therefore, this thesis proposed dual particle swarm optimization for solving the two sub-problem of MRCPSP.
In this thesis, a constriction version of the velocity update rule in standard PSO is suggested instead of using that of the original PSO. Moreover, discrete version PSO is included to solve the mode assignment sub-problem. Furthermore, we propose a new communication topology of global experience for particle swarm optimization; which balances slow and premature convergence. This proposed communication topology is named rand-link topology. Meanwhile, this work combined two heuristics based on mode and activity priority rules were introduced to generate better initial solutions made assignment and activity priority to enhance efficiency.
First, this thesis focuses on testing the well-known benchmark, where the problem is the MRCPSP instances of PSPLIB. Then, this approach is applied to human resource planning project scheduling problem. In real world, all the conditions of human resource planning project scheduling problem is similar to the MRCPSP. Hence, we applied the suggested scheme and well-used the Half-Man-Day as the unit of resource to find the optimal human resource. Simulation results demonstrate that the proposed scheme provides an effective and efficient method to solve real-world human resource planning for project scheduling problems.
中文摘要 III
英文摘要 IV
誌 謝 V
表 目 錄 VIII
圖 目 錄 IX
一、 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究方法 3
1.4 研究貢獻 4
二、 多模式資源受限之專案排程問題 6
2.1 專案排程問題 6
2.2 多模式資源受限之專案排程問題(MRCPSP) 9
2.3 可行解與不可行解 11
2.4 專案排程人力資源規劃問題 15
2.5 問題複雜度 16
三、 粒子群優化法 17
3.1 粒子群優化法(Particle Swarm Optimization; PSO) 17
3.1.1 粒子群優化法的概念 17
3.1.2 粒子群優化法的更新 19
3.2 其它版本的粒子群優化法 21
3.2.1 離散粒子群優化法 21
3.2.2 “標準”粒子群優化法 23
四、 求解排程問題的相關方法 25
4.1 排程產生法(Schedule Generation Schemes) 25
4.1.1 序列排程產生法 25
4.1.2 並行排程產生法 27
4.2 前後排程法(Forward-bakcward scheduling methods) 29
4.3 基於優先權規則的啟發式演算法 30
4.3.1 基於“模式”優先權規則的啟發式演算法 31
4.3.2 基於“活動”優先權規則的啟發式演算法 32
4.4 其它相關方法 33
4.4.1 修補機制(Repair mechanism) 33
4.4.2 懲罰機制(Penalty mechanism) 35
五、 方法設計 37
5.1 改良群體溝通模型 37
5.2 解的編碼(Encoding)設計 39
5.2.1 模式表的編碼設計 39
5.2.2 活動表的編碼設計 41
5.3 以啟發式演算法提供起始位置設計 42
5.4 解的合適度計算 43
5.5 以雙重粒子群優化法求解MRCPSP 43
六、 效能分析比較與實作 45
6.1 實驗設計 46
6.2 Rand-Link對粒子群演算法的影響及比較 46
6.3 啟發式演算法使用比例的影響及比較 47
6.4 通訊拓撲對演算法在效能上的影響 48
6.5 與其它演算法在效能上的比輬 51
6.6 專案排程之人力資源規劃實例應用的模擬結果 52
6.7 實作最佳化實務專案的應用程式 58
七、 結論 61
參考文獻 63
[1] Liu, K. H., Wilson, B. J., Wei, J. Y., (2000), “A scheduling application for WDM optical networks”, IEEE Journal on Selected Areas in Communications, vol. 18, Issue 10, pp. 2041-2050, Oct. 2000.
[2] Ross, K., Bamos, N., (2005), “Dynamic quality of service control in packet switch scheduling”, IEEE International Conference on Communications 2005 (ICC 2005), vol. 1, pp. 396-401, May. 2005.
[3] Humo, E., Vejzovic, Z., (2007), “A Mathematical Model of Classroom-Period Schedule De-fragmentation”, The International Conference on Computer as a Tool EUROCON 2007, pp. 2034-2038, Sept. 2007.
[4] Decker, K., Li, J., (1998), “Coordinated hospital patient scheduling”, Proceedings of International Conference on Multi Agent Systems, pp. 104-111, Jul. 1998.
[5] Ohki, M., Morimoto, A., Miyake, K., (2006), “Nurse Scheduling by Using Cooperative GA with Efficient Mutation and Mountain-Climbing Operators”, The 3rd International IEEE Conference on Intelligent Systems, pp. 164-169, Sept. 2006.
[6] Spry, C. W., Lawley, M. A., (2005), “Evaluating hospital pharmacy staffing and work scheduling using simulation”, Proceedings of the 37th conference on Winter Simulation Conference, pp. 4-8, 4-7 Dec. 2005.
[7] Ciesielski, V., Scerri, P., (1998), “Real time genetic scheduling of aircraft landing times”, Proceedings of The 1998 IEEE International Conference on Evolutionary Computation, pp. 360-364, May 1998.
[8] Saraf, A. P., Slater, G. L., (2006), “An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports”, 2006 IEEE Aerospace Conference, pages 11 pp., 2006.
[9] 陳毓卿, (2007), “因應臨時事件航機停機修護排程調整最佳化之研究”, 國立中央大學, 土木工程學系碩士論文
[10] Chiang, T.-W., Hau, H.-Y., (1995), “Railway Scheduling System Using Repair-based Approach”, Seventh International Conference on Tools with Artificial Intelligence, pp. 71, 1995.
[11] Xie, T., Qin, X., (2006), “Scheduling security-critical real-time applications on clusters”, IEEE Transactions on Computers, vol. 55, Issue 7, pp. 864-879, Jul. 2006, doi: 10.1109/TC.2006.110.
[12] Berkwitt, G. J., (1975), “Management Rediscovers CPM”, Engineering Management Review IEEE, vol. 3, Issue 3, pp. 50-52, Sept. 1975.
[13] Gray, C. F., Larson, E. W. (2005), “Project Management: The Managerial Process”, McGraw-Hill, Irwin, Jan. 2005.
[14] Gido, J., Clements, J. P., (2005), “Successful Project Management”, South-Western College Pub, Oct. 2005
[15] Alcaraz, J., Maroto, C., (2001), “A robust genetic algorithm for resource allocation in project scheduling”, Annals of Operations Research, vol. 102, no. 1-4, pp. 83–109, 2001.
[16] Merkle, D., Middendorf, M., Schmeck, H., (2002), “Ant colony optimization for resource-constrained project scheduling”, IEEE Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 333–346, Aug. 2002.
[17] Thomas, P. R., Salhi, S., (1998), “A Tabu Search Approach for the Resource Constrained Project Scheduling Problem”, Journal of Heuristics, vol. 4 no. 2, pp. 123-139, 1998.
[18] 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, vol. 149, Issue 2, pp. 268-281, Sep. 2003.
[19] Chen, R.-M., (2011), “Particle Swarm Optimization with Justification and Designed Mechanisms for Resource-Constrained Project Scheduling Problem,” Expert Systems With Applications, vol. 38, no. 6, Jun. 2011.
[20] Chen, R.-M., Wu, C.-L., Wang, C.-M., Lo, S.-T., (2010), “Using A Novel Particle Swarm Optimization Scheme to Solve Resource-Constrained Scheduling Problem in PSPLIB”, Expert Systems With Applications, vol. 37, no. 3, pp. 1899-1910, Mar. 2010.
[21] Lo, S.-T., Chen, R.-M., Huang, Y.-M., Wang, C.-M., (2008), “Multiprocessor System Scheduling with Precedence and Resource Constraints Using an Enhanced Ant Colony System”, Expert Systems With Applications, vol. 34, no. 3, pp. 2071-2081, Apr. 2008.
[22] Kolisch, R., Sprecher, A., (1997), “PSPLIB - A project scheduling problem library : OR Software - ORSEP Operations Research Software Exchange Program”, European Journal of Operational Research, vol. 96, pp. 205-216, 1997.
[23] Blazewicz, J., Lenstra, J., Rinnooy Kan, A., (1983), “Scheduling subject to resource constraints: classi_cation and complexity”, Discrete Applied Mathematics, vol. 5, Issue 1, pp. 11-24, Jan. 1983.
[24] Kolisch, R., Drexl, A., (1997), “Local search for nonpreemptive multi-mode resource-constrained project scheduling”, IIE Transactions, vol. 29, no. 11, pp. 987-999, 1997.
[25] Drexl, A., Gruenewald, J., (1993), “Nonpreemptive multi-mode resource-constrained project scheduling”, IIE Transactions, vol, 25, Issue, 5. pp. 74 – 81. 1993.
[26] Kennedy, J., Eberhart, R., (1995), “Particle swarm optimization”, in Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, Nov. 1995.
[27] Sha D.Y., Hsu, C.-Y., (2006), “A hybrid particle swarm optimization for job shop scheduling problem”, Computers & Industrial Engineering, vol. 51, Issue 4, pp. 591-808, Dec. 2006.
[28] Kuo, I-H., Horng, S.-J., Kao, T.-W., Lin, T.-L., Lee, C.-L., Terano, T., Pan, Y., (2008), “An Efficient Flow-shop Scheduling Algorithm based on a Hybrid Particle Swarm Optimization Model”, Expert System with Applications, vol. 36, Issue 3, part 2, pp. 7027-7032, Aug. 2008.
[29] Kennedy, J., Eberhard, R. C., (1997), “A Discrete Binary Version of the Particle Swarm Algorithm”, in Proceedings of IEEE Conference on Systems, Man, and Cybernetics, Piscataway, vol. 5, pp. 4104–4109. Oct. 1997.
[30] Jarboui, B., Damak, N., Siarry, P., Rebai, A., (2008), “A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems”, Applied Mathematics and Computation, vol. 195, pp. 299-308, 2008.
[31] Pugh, J., Martinoli, A., (2007), “Discrete multi-valued particle swarm optimization,” Proceedings of IEEE Swarm Intelligence Symposium, pp. 103-110, 2007.
[32] Liao, C.-J., Tseng, C.-T., Luarn, P., (2007), “A discrete version of particle swarm optimization for flowshop scheduling problems”, Computers & Operations Research, vol. 34, pp. 3099-3111, 2007.
[33] Bratton, D., Kennedy, J., (2007), “Defining a Standard for Particle Swarm Optimization”, in Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, pp. 120-127, 2007.
[34] Kolisch, R., (1996), “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”, European Journal of Operational Research, vol. 90, Issue 2, pp. 320-333, Apr, 1996.
[35] Buddhakulsomsiri, J., Kim, D. S., (2007), “Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting”, European Journal of Operational Research, Discrete Optimization, vol. 178, Issue 2, pp. 374-390, Apr. 2007.
[36] Watts, D. J., Strogatz, S. H., (1998), “Collective dynamics of ‘small-world’ networks”, Nature 393, pp. 440-442, Jun. 1998.
[37] Kolisch, R., Hartmann, S., (1999), “Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis”, in Project Scheduling, Recent Models, Algorithms and Applications, J. Weglarz, Ed. Kluwer Academic Publishers, MA: Norwell, 1999, ch. 7, pp. 147-178.
[38] Chen, R.-M., Wang, C.-M., (2011), “Project Scheduling Heuristics Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid”, Abstract and Applied Analysis, vol. 2011, ID. 589862, doi:10.1155/2011/589862.
[39] 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, vol. 54, no. 6, pp. 614–626, 2003.
[40] Józefowska, J., Mika, M., Różycki, R., Waligóra, G., Węglarz, J., (2001), “Simulated annealing for multi-mode resource constrained project scheduling”, Annals of Operations Research., vol. 102, no. 1-4, pp. 137-155, 2001.
[41] Hartmann, S., Drexl, A., (1998), “Project scheduling with multiple modes: A comparison of exact algorithms”, Networks 32, pp. 283–297, 1998.
[42] Hartmann, S., (2001), “Project scheduling with multiple modes: A genetic algorithm”, Annals of Operations Research, vol. 102, no. 1-4, pp. 111-135, 2001.
[43] Heilmann, R., (2003), “A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags”, European Journal of Operational Research, Discrete Optimization, vol. 144, Issue 2, pp. 348-365, Jan. 2003.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔