Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/17570
標題: 利用演化式演算法解資源有限專案規劃問題之研究
A Study on Evolutionary Algorithms for the Resource-Constrained Project Scheduling Problem
作者: 陳士傑
Chen, Shih-Chieh
關鍵字: evolutionary algorithms
演化式演算法
metaheuristics
resource-constrained project scheduling problem
genetic algorithms
local search
ant colony optimization
超啟發式演算法
資源有限專案規劃問題
基因演算法
區域搜尋
螞蟻尋路法
出版社: 應用數學系所
引用: [1] J. Alcaraz and C. Maroto, “A genetic algorithm for the resource-constrained project scheduling problem”, in Proc. 6th Inter. Works. Project Management and Scheduling, Boğazici University, 1998, pp. 7-10. [2] J. Alcaraz and C. Maroto, “A robust genetic algorithm for resource allocation in project scheduling”, Ann. Oper. Res., vol. 102, pp. 83-109, 2001. [3] J. Alcaraz, C. Maroto and R. Ruiz, “Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms”, J. Oper. Res. Soc., Vol. 54, pp. 614-626, 2003. [4] C. Artigues, P. Michelon and S. Reusser, “Insertion techniques for static and dynamic resource-constrained project scheduling”, Eur. J. Oper. Res., Vol. 149, pp. 249-267, 2003. [5] T. Baar, P. Brucker and S. Knust, “Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem”, Meta-heuristics: Advances and trends in local search paradigms for optimization, S. Voss, S. Martello, I. Osman and C. Roucairol (Eds.), Kluwer, Boston, 1998, pp. 1-8. [6] F.F. Boctor, “Some efficient multi-heuristic procedures for resource-constrained project scheduling”, Eur. J. Oper. Res., vol. 49 pp. 3-13, 1990. [7] F.F. Boctor, “An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problem”, Int. J. of Prod. Res., Vol. 34, pp. 2335-2351, 1996. [8] F.F. Boctor, “Heuristics for scheduling projects with resource restrictions and several resource-duration modes”, Int. J. of Prod. Res., vol. 31, pp. 2547-2558, 1993. [9] F.F. Boctor, “A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes”, Eur. J. Oper. Res., vol. 90, pp. 349-361, 1996. [10] K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem”, in Proc. 6th Inter. Works. Project Management and Scheduling, Boğazici University, 1998, pp. 19-22. [11] K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version”, Eur. J. Oper. Res., vol. 149, pp. 268-281, 2003. [12] P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch, “Resource-constrained project scheduling: notation, classification, models, and methods”, Eur. J. Oper. Res., vol. 112, pp. 3-41, 1999. [13] P. Brucker, S. Knust, A. Schoo and O. Thiele, “A branch-and-bound algorithm for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., vol. 107, pp. 272-288, 1998. [14] J. H. Cho and Y. D. Kim, “A simulated annealing algorithm for resource constrained project scheduling problems”, J. Oper. Res. Soc., vol. 48, pp. 736-744, 1997. [15] E. Demeulemeester and W. Herroelen, “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem”, Management Science, vol. 12, no. 38, pp. 1803-1818, 1992. [16] E. Demeulemeester and W. Herroelen, “New benchmark results for the multiple resource-constrained project scheduling problem”, Management Science, vol. 11, no. 43, pp. 1485-1492, 1997. [17] M. Dorigo, “Optimization, learning and natural algorithms”, PhD dissertation, Dipartimento di Elettronica, Politecnico di Milano, Italy (1992). [18] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Trans. Evol. Compt., Vol. 1, no. 1 pp. 53-66, 1997. [19] A. Drexl and J. Grünewald, “Nonpreemptive multi-mode resource-constrained project scheduling”, IIE Trans., vol. 25, pp. 74-81, 1993. [20] S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling”, Naval Res. Logist., vol. 45, pp. 733-750, 1998. [21] S. Hartmann, “A self-adapting genetic algorithm for project scheduling under resource constraints”, Naval Res. Logist., vol. 49, pp. 433-448, 2002. [22] S. Hartmann, “Project scheduling with multiple modes: A genetic algorithm”, Ann. Oper. Res., vol. 102, pp. 111-135, 2001. [23] S. Hartmann and A. Drexl, “Project scheduling with multiple modes: A comparison of exact algorithm”, Networks, vol. 32, pp. 733-750, 1998. [24] S. Hartmann and R. Kolisch, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., vol. 127, pp. 394-407, 2000. [25] W. Herroelen, B. De Reyck and E. Demeulemeester, “Resource-constrained project scheduling: a survey of recent developments”, Compu. Oper. Res., vol. 4, no. 25, pp. 279-302, 1998. [26] J. H. Holland, “Genetic algorithms”, Scientific American, July, pp. 44-51, 1992. [27] J. Jozefowska, M. Mika, R. Rozychi, G. Waligora and J. Weglarz, “Simulated annealing for multi-mode resource-constrained project scheduling”, Ann. Oper. Res., vol. 102, pp. 137-155, 2001. [28] Y. Kochetov and A. Stolyar, “Evolutionary local search with variable neighborhood search for the resource-constrained project scheduling problem”, Proc. of the 3rd International Workshop of Computer Science and Information Technologies, Russia, 2003. [29] R. Kolisch, “Efficient priority rules for the resource-constrained project scheduling problem”, J. Oper. Manag., vol. 14, pp. 179-192, 1996. [30] R. Kolisch, “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”, Eur. J. Oper. Res., vol. 90, pp. 320-333, 1996. [31] R. Kolisch and A. Drexl, “Local search for nonpreemptive multi-mode resource-constrained project scheduling”, IIE Trans., vol. 43, pp. 987-999, 1996. [32] R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: an update”, working paper, Technical University of Munich, Germany, Available : http://halfrunt.bwl.uni-kiel.de/bwlinstitute/Prod/mab/hartmann/hartmann.html , 2004. [33] R. Kolisch and R. Padman, “An integrated survey of deterministic project scheduling”, OMEGA, vol. 29, pp. 249-272, 2001. [34] R. Kolisch and A. Sprecher, “PSPLIB - a project scheduling problem library”, Eur. J. Oper. Res., vol. 96, pp. 205-216, 1996. [35] J.-K. Lee, and Y.-D. Kim, “Search heuristics for resource constrained project scheduling”, J. Oper. Res. Soc., vol. 47, pp. 678-689, 1996. [36] K. Y. Li and R. J. Willis, “An iterative scheduling technique for resource-constrained project scheduling”, Eur. J. Oper. Res., vol. 56, pp. 370-379, 1992. [37] D. Merkle, M. Middendorf and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling”, IEEE trans. Evolu. Compu., vol. 4, no. 6, pp. 333-346, 2002. [38] R. Möhring, A. Schulz, F. Stork and M. Uetz, “Solving project scheduling problems by minimum cut computations”, Manag. Sci., vol. 3, no. 49, pp. 330-350, 2003. [39] M. Mori and C.C. Tseng, “A genetic algorithm for multi-mode resource constrained project scheduling problem”, Eur. J. Oper. Res., vol. 100, pp. 134-141, 1997. [40] K. Nonobe and T. Ibaraki, “Formulation and tabu search algorithm for the resource constrained project scheduling problem”, in Essays and surveys in metaheuristics, Ribeiro, CC. and Hansen, P. (Ed.), Kluwer Academic Publishers, pp. 557-588, 2001. [41] L. Özdamar, “A genetic algorithm approach to a general category project scheduling problem”, IEEE Trans. Sys. Man, Cybern. Part C., vol. 29, pp. 44-59, 1999. [42] L. Özdamar and G. Ulusoy, “An iterative local constraint based analysis for solving the resource constrained project scheduling problem”, J. Oper. Manag., vol. 14, pp. 193-208, 1996. [43] L. Özdamar and G. Ulusoy, “A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis”, Eur. J. Oper. Res., vol. 89, pp. 400-407, 1996. [44] M. Palpant, C. Artigues and P. Michelon, “LSSPER: solving the resource-constrained project scheduling problem with larger neighborhood search”, Ann. Oper. Res., vol. 131, pp. 237-257, 2004. [45] R. Slowinski, B. Soniewicki and J. Węglarz, “DSS for multiobjective project scheduling subject to multiple-category resource constraints”, Eur. J. Oper. Res., vol. 79, pp. 220-229, 1994. [46] A. Sprecher and A. Drexl, “Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm”, Eur. J. Oper. Res., vol. 107, pp. 431-450, 1998. [47] A. Sprecher, S. Hartmann and A. Drexl, “An exact algorithm for project scheduling with multiple modes”, OR Spectrum, vol. 19, pp. 195-203, 1997. [48] L. Y. Tseng and S. C. Chen, “A hybrid metaheuristic ANGEL for the resource-constrained project scheduling problem”, Eur. J. Oper. Res., to be published. [49] L. Y. Tseng and S. C. Liang, “A hybrid metaheuristic and its application to the traveling salesman problem”, manuscript revised to IEEE Trans. Evolu. Compu.. [50] G. Ulusoy and L. Özdamar, “Heuristic performance and network/resource characteristics in resource-constrained project scheduling”, J. Oper. Res. Soc., vol. 40, pp. 1145-1152, 1989. [51] G. Ulusoy and L. Özdamar, “A constraint-based perspective in resource constrained project scheduling”, Int. J. of Prod. Res., vol. 32, pp. 693-705, 1994. [52] V. Valls, F. Ballestin and S. Quintanilla, “Justification and RCPSP: a technique that pays”, Eur. J. Oper. Res., vol. 165, pp. 375-386, 2005. [53] V. Valls, F. Ballestin and S. Quintanilla, “A population-based approach to the resource-constrained project scheduling problem”, Ann. Oper. Res., vol. 165, pp. 375-386, 2005. [54] V. Valls, F. Ballestin and S. Quintanilla, “A hybrid genetic algorithm for the RCPSP with the peak crossover operator”, in 8th int. workshop on project management and scheduling, Available : http://www.adeit.uv.es/pms2002/, 2002. [55] V. Valls, M.A. Perez, and M.S. Quintanilla, “Heuristic performance in large resource-constrained projects”, Technical report, Department of Statistics and Operations Research, Universitat de Valencia, Valencia, Spain, 1992. [56] V. Valls, S. Quintanilla and F. Ballestin, “Resource-constrained project scheduling - a critical activity reordering heuristic”, Eur. J. Oper. Res., vol. 149, pp. 282-301, 2003.
摘要: 本論文探討演化式演算法新的設計方法。基於同時考慮搜尋能力之深入性與發散性,我們將一個包含多個優良解之集合,稱之為優解集,坎入在二階段或交替式二階段演化式演算法中有效的來解一些困難的問題。我們加強第一階段演算法之發散性來尋找解空間中最佳解之可能存在區域,在過程中將優良且不同之解存入優解集中,第二階段演算法之起始群體則大都由優解集中最好的解產生,利用交換不同優良解中之好的特性,演算法可以充分深入搜尋這些區域而找到更好的解。 本研究主要將上述方式所設計之演化式演算法應用於一系列資源有限之專案規劃問題上,我們並提出一種有效的區域尋法應用於其中。該區域搜尋法已經過實驗證實為一種利用少量的計算便可大幅提升解品質之方法。在本論文中,我們首先提出一種結合螞蟻尋路法、基因演算法、與區域搜尋法之超啟發式演算法,稱為ANGEL,來解單運作模式之資源有限專案規劃問題;其次提出一種二階段與一種交替式二階段之基因區域搜尋演算法來解多運作模式之資源有限專案規劃問題。經由適度設計的演化機制、區域搜尋、多次重新搜尋、與優解集的運用,演算法搜尋能力之發散性與深入性可以作到適當的調整,使得即使經過長時間的運作之後仍然保有其搜尋的能力。 我們經由一系列的實驗來證實我們所提出的方法之搜尋能力,實驗例子均取自於著名的標準化例子,其中並包含了大小不同的問題。
In this dissertation, new methodologies were proposed to design evolutionary algorithms. More specifically, two-phase and iterated two-phase evolutionary algorithms were proposed in order to arrange properly the strength of intensification and the strength of diversification. In the first phase, diversification is enhanced that aims to search broadly for promising areas. In the second phase, intensification is enhanced that aims to search more thoroughly within each promising area. Two resource-constrained project scheduling problems (RCPSP) was considered to test our new methodologies. We first proposed a metaheuristics named ANGEL which combines the ant colony optimization, the genetic algorithm and the local search method for the single mode RCPSP. The second algorithm proposed is a two-phase and a iterated two-phase genetic local search algorithms for the multi-mode RCPSP. By suitable application of the evolutionary operators, the local search method, the restart of the algorithm and the collection of good solutions in the elite set, the strength of intensification and diversification can be properly adapted and the search ability can be retained even in a very long term. A series of experiments were conducted to assess the capabilities of these evolutionary algorithms. Instances of these problems were taken from well known benchmarks with different problem sizes.
URI: http://hdl.handle.net/11455/17570
其他識別: U0005-2007200623151800
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-2007200623151800
Appears in Collections:應用數學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.