跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/08/02 11:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳孟舫
研究生(外文):Meng-FangWu
論文名稱:考慮作業等候時間限制之多模式資源限制專案排程問題
論文名稱(外文):Multi-mode resources-constrained project scheduling problem with activity waiting time
指導教授:張秀雲張秀雲引用關係
指導教授(外文):Shiow-Yun Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:工業與資訊管理學系碩博士班
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:84
中文關鍵詞:等候時間多模式資源限制專案排程基因演算法
外文關鍵詞:waiting timemulti-mode resources-constrained project scheduling problemGenetic Algorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:202
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
多模式資源限制專案排程問題 (Multi-mode Resource-Constrained Project Scheduling Problem, MRCPSP)是為了使專案排程問題更符合現實狀況而從單模式資源限制問題所衍伸而來。實際專案執行中某些作業會有等候時間限制的現象,此一等候時間雖不會直接增加作業執行時間,亦不會耗費任何可恢復以及不可恢復資源,但會影響到該作業之直接後續作業開始時間,進而影響到整個專案排程的完工時間,故本研究針對此一作業等候時間的限制,建立目標式及符合本研究的限制式,針對此一等候時間的特性發展一個以基因演算法為基礎的演算法並使用單點式交配、兩點式交配以及均勻式交配等,三種不同的親代交配方式來求解專案排程使總完工時程最小化。
本研究使用國際測試題庫(Project Scheduling Problem Library, PSPLIB)之多模式資源限制專案排程資料,隨機選取作業加入等候時間限制,且同一作業之不同執行模式亦會有不同之等候時間來測試所提出之演算法,並探討不同作業數目類型問題加入等候時間限制對排程所造成的影響,並比較不同交配方式之下所求得解品質以及系統執行時間,從測試結果可得知,使用基因演算法之兩點式交配方式來求解等候作業時間專案排程問題能得到較好品質的解,而使用單點式交配方式能在較短的運算時間求解專案問題。

To make the project scheduling problem close to realistic situation, multi-mode resources-constrained project scheduling problem (MRCPSP) is extend from the resources constrained project scheduling problem (RCPSP). During the implementation of projects, there are some waiting time limitations between activities. Although the waiting time won’t increase activity processes time directly and consume any renewable resources as well as nonrenewable resources, it affects the starting time of the direct follow-up activity and the total project makespan. This study use a genetic algorithm to solve the problems of MRCPSP with waiting time limitations, and to minimize total project makespan.
The dataset are selected from project scheduling problem library (PSPLIB). This study considered two limitations: First, randomly selected activities would be considered with the waiting time limitations. Second, there was different waiting time corresponding to each mode. Furthermore, this study try to explore the effects of schedules by examining different sizes project problems with activity waiting time.
First of all, we use the proposed algorithm to find the mutation probability for different sizes of project problems. Then, we find the feasible solution by using different crossover methods, and compare the feasible solution. The results showed that the two-point crossover can get a better feasible solution, and one-point crossover can get a feasible solution in a shorter time.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.3 研究架構 3
第二章 文獻探討 5
2.1 資源限制專案排程問題 5
2.2多模式資源限制專案排程問題 6
2.3 求解MRCPSP方法 7
2.3.1 確切程序求解法 8
2.3.2 啟發式演算法 8
2.3.3 超啟發式演算法 8
2.3.4 其他求解方法 14
2.4 其他延伸類型 15
2.5 小結 15
第三章 研究方法 18
3.1 問題描述與基本假設 18
3.2 符號定義與建立限制式 19
3.3 範例 22
3.4 演算法建構 26
3.4.1 起始母體設置 27
3.4.2 適性值評估 27
3.4.3 親代選擇及交配 28
3.4.4 子代突變 33
3.4.5 考慮作業等候時間限制 34
3.4.6 更新及終止 37
3.5 小結 37
第四章 問題測試與分析 39
4.1 求解問題描述與求解配備 39
4.2 參數設定 40
4.3 測試結果分析 42
4.4 小結 50
第五章 結論與未來研究 51
5.1 結論 51
5.2 未來研究方向 52
參考文獻 53
附錄A 求解專案問題運算時間 57
附錄B 各專案問題最佳交配方式 78

中文部分
林欣慧, 「多組態資源限制專案排程問題解算之研究-包含不可恢復資源限制」,私立元智大學工業工程與管理研究所碩士論文,2005。
蔡政峰,「求解有限資源專案排程問題最佳化之研究--以基因演算法求解」,國立成功大學工業管理學研究所碩士論文,2001。

英文部分
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, 54(6), 614-626.
Barrios, A., Ballestin, F., & Valls, V. (2011). A double genetic algorithm for the MRCPSP/max. Computers & Operations Research, 38(1), 33-43.
Boctor, F. F. (1993). Heuristics for scheduling projects with resource restrictions and several resource-duration modes. International Journal of Production Research, 31(11), 2547-2558.
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, 149(2), 268-281.
Brucker, P., Drexl, A., Mohring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3-41.
Chen, Y. L., & Tang, K. (1998). Minimum time paths in a network with mixed time constraints. Computers & Operations Research, 25(10), 793-805.
Damak, N., Jarboui, B., Siarry, P., & Loukil, T. (2009). Differential evolution for solving multi-mode resource-constrained project scheduling problems. Computers & Operations Research, 36(9), 2653-2659.
De Reyck, B., & Herroelen, W. (1999). The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 119(2), 538-556.
Debels, D., & Vanhoucke, M. (2005). A bi-population based genetic algorithm for the resource-constrained project scheduling problem. Computational Science and Its Applications, ICCSA 2005, 85-117.
Deblaere, F., Demeulemeester, E., & Herroelen, W. (2010). Reactive scheduling in the multi-mode RCPSP. Computers & Operations Research, 37(1), 63-74.
Drexl, A., & Gruenewald, J. (1993). Nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions, 25(5), 74-81.
Elloumi, S., & Fortemps, P. (2010). A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 205(1), 31-41.
Hartmann, S. (2001). Project scheduling with multiple modes: a genetic algorithm. Annals of Operations Research, 102(1), 111-135.
Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1-14.
Hartmann, S., & Drexl, A. (1998). Project scheduling with multiple modes: A comparison of exact algorithms. Networks, 32(4), 283-297.
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, 144(2), 348-365.
Jairo R. Montoya-Torres, Edgar Gutierrez-Franco, & Pirachicán-Mayorga, C. (2010). Project scheduling with limited resources using a genetic algorithm. International Journal of Project Management, 28(6), 619-628.
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, 195(1), 299-308.
Jozefowska, J., Mika, M., Rozycki, R., Waligora, G., & Weglarz, J. (2001). Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102(1), 137-155.
Kelley Jr., J. E. (1963). The critical-path method: Resources planning and scheduling. In: Industrial Scheduling. Prentice-Hall, New Jersey, pp. 347-365.
Kolisch, R., & Drexl, A. (1997). Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions, 29(11), 987-999.
Lova, A., Tormos, P., & Barber, F. (2006). Multi-mode resource constrained project scheduling: Scheduling schemes, priority rules and mode selection rules. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 30, 69-86.
Lova, A., Tormos, P., Cervantes, M., & Barber, F. (2009). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2), 302-316.
Mika, M., Waligora, G., & Weglarz, J. (2008). Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. European Journal of Operational Research, 187(3), 1238-1250.
Mori, M., & Tseng, C. C. (1997). A genetic algorithm for multi-mode resource constrained project scheduling problem. European Journal of Operational Research, 100(1), 134-141.
Nonobe, K., & Ibaraki, T. (2001). Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). Technical Report, Kyoto University.
Peteghem, V. V., & Vanhoucke, M. (2010). A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 201(2), 409-418.
Slowinski, R. (1980). Two Approaches to Problems of Resource Allocation among Project Activities - A Comparative Study. Journal of the Operational Research Society, 31(8), 711-723.
Slowinski, R., & Soniewicki, B. (1994). DSS for multiobjective project scheduling. European Journal of Operational Research, 79(2), 220-229.
Sprecher, A., & Drexl, A. (1998). Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm1. European Journal of Operational Research, 107(2), 431-450.
Sprecher, A., Hartmann, S., & Drexl, A. (1997). An exact algorithm for project scheduling with multiple modes. OR Spectrum, 19(3), 195-203.
Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 1197-1210.
Vanhoucke, M., & Coelho, J. (2011). Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. European Journal of Operational Research, 213(1), 73-82.
Zhang, H., Tam, C., & Li, H. (2006). Multimode project scheduling based on particle swarm optimization. Computer Aided Civil and Infrastructure Engineering, 21(2), 93-103.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top