Ant colony optimization in project management

• Autorzy: Skołud, B. , Marcińczyk, B.
• Języki publikacji: EN

Abstrakty

EN

This paper presents an Ant Colony Optimization (ACO) approach to the resource-constrained project scheduling problem (RCPSP). RCPSP as a generalization of the classical job shop scheduling problem belongs to the class of NP-hard optimization problems. Therefore, the use of heuristic solution procedures when solving large problem is well-founded. Most of the heuristic methods used for solving resource-constrained project scheduling problems either belong to the class of priority rule based methods or to the class of metaheuristic based approaches. ACO is a metaheuristic method in which artificial ants build solutions by probabilistic selecting from problem-specific solutions components influenced by a parametrized model of solution, called pheromone model. In ACO several generations of artificial ants search for good solution. Every ant builds a solution step by step going through several probabilistic decisions. If ant find a good solution mark their paths by putting some amount of pheromone (which is guided by some problem specific heuristic) on the edges of the path.

Słowa kluczowe

PL

optymalizacja; zarządzanie

EN

resources constrained scheduling problem; project scheduling; multi-project scheduling; ant colony optimization; swarm intelligence

• Czasopismo: Computer Assisted Mechanics and Engineering Sciences
• Rocznik: 2007
• Tom: Vol. 14, No. 4
• Strony: 745-752
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Skołud, B.

autor

Marcińczyk, B.

• Silesian University of Technology, Institute of Engineering Process Automation and Integrated Manufacturing Systems, ul. Konarskiego 18A, 44-100 Gliwice

Bibliografia

• [1] J. Alcaraz, C. Maroto. A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102: 83-109, 2001.
• [2] F.F. Boctor. An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems. International Journal of Production Research, 34: 2335-2351, 1996.
• [3] K. Bouleimen, H. Lecocq. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149: 268-281, 2003.
• [4] J. Blazewicz, J.K. Lenstra, K.A.H.G. Rinnooy. Scheduling projects to resource constraints: classification and complexity. Discrete Applied Mathematics, 5: 11-24, 1983.
• [5] Ch. Blum. Ant Colony Optimization: Introduction and Recent Trends. Physics of live reviews, 2005.
• [6] J. Brilman. Nowoczesne Koncepcje i Metody Zarzqdzania. PWE, Warszawa, 2002.
• [7] M. Dorigo, V. Maniezzo, A. Colorni. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Systems, Man and Cybernetics, Italy, 1996.
• [8] Ch. Hantak. Comparison of Parallel Hardware Based and Graphics Hardware Based Platforms for Swarm Intelligence Simulations. Integrative Paper, UNC-Chapel Hill, 2003.
• [9] R. Kolisch, S. Hartmann. Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis. In: J. Weglarz, ed., Handbook on Recent Advances in Project Scheduling, pp. 147-178. Kluwer, Dordrecht, 1999.
• [10] A. Kostrubiec. Harmonogramowanie realizacji projektow - przeglqd modeli. www.zie.pg.gda.pl/koipsp/4adamkostrubiec.pdf
• [11] S.R. Lawrence, T.E. Morton. Resource-constrained multi-project scheduling with tardy costs: Comparing myopic bottleneck and resource pricing heuristics. European Journal of Operational Research, 64: 168-187, 1993.
• [12] L.P. Leach. Critical Chain Project Management Artach Mouse, Boston 2000.
• [13] J.K. Lee, Y.D. Kim. Search heuristics for resource-constrained project scheduling. Journal of the Operational Research Society, 47: 678-689, 1996.
• [14] D. Lock. Podstawy zarzqdzania projektami. Polskie Wydawnictwo Ekonomiczne, Warszawa, 2003.
• [15] A. Lova, C. Maroto, P. Tormos. A multicriteria heuristic method to improve resource allocation in multiproject scheduling. European Journal of Operational Research, 127: 408-424, 2000.
• [16] D. Merkle, M. Middendorf, H. Schmeck. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6: 333-346, 2002.
• [17] A. Mingozzi, V. Maniezzo, S. RicciardeUi, L. Bianco. An Exact Algorithm for the Resource Constrained Project Scheduling Problem Based on a New Mathematical Formulation, www.csr.unibo.it/~maniezzo/pspaper.ps, 1995
• [18] J. Montgomery, F. Fayad, S. Petrovic. Solution Representation for Job Shop Scheduling Problems in Ant Colony Optimization, www.asap.cs.nott.ac.uk/publications/pdf/ACO06Final.pdf
• [19] E. Pinson, C. Prins, F. Rullier. Using tabu search for solving the resource-constrained project scheduling problem. Proceedings of the 4th International Workshop on Project Management and Scheduling, Leuven, Belgium, pp. 102-106, 1994.
• [20] A. Pritsker, B. Allan, L.J. Watters, P.M. Wolfe. Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16: 93-108, 1969.
• [21] M. Trocki, B. Grucza, K. Ogonek. Zarządzanie Projektem. Polskie Wydawnictwo Ekonomiczne, Warszawa, 2002.
• [22] S. Tsubakitani, R.F. Deckro. A heuristic for multi-project scheduling with limited resources in the housing industry. European Journal of Operational Research, 49: 80-91, 1990.
• [23] M.B. Wall, A Genetic Algorithm for Resource-Constrained Scheduling, Doctoral Dissertation for Mechanical
• [24] V. D. Wiley, R. F. Deckro, J. A. Jackson. Optimization analysis for design and planning of multi-project prpgrams. European Journal of Operational Research, 107: 492-506, 1998.