BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Pawiński Grzegorz (Kielce University of Technology, Kielce, Poland), Sapiecha Krzysztof (Cracow University of Technology, Poland)
Title
A Developmental Genetic Approach to the cost/time trade-off in Resource Constrained Project Scheduling
Source
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 171 - 179, rys., tab., bibliogr. 31 poz.
Keyword
Algorytmy genetyczne, Programowanie genetyczne, Planowanie projektu
Genetic algorithms, Genetic programming, Project planning
Note
summ.
Abstract
In this paper, the use of Developmental Genetic Programming (DGP) for solving a new extension of the Resource- Constrained Project Scheduling Problem (RCPSP) is investigated. We consider a variant of the problem when resources are only partially available and a deadline is given but it is the cost of the project that should be minimized. RCPSP is a well-known NP-hard problem but in its original formulation it does not take into consideration initial resource workload and it minimises the makespan. Unlike other genetic approaches, where genotypes represent solutions, a genotype in DGP is a procedure that constructs a solution to the problem. Genotypes (the search space) and phenotypes (the solution space) are distinguished and a genotype-to-phenotype mapping (GPM) is used. Thus, genotypes are evolved without any restrictions and the whole search space is explored. The goal of the evolution is to find a procedure constructing the best solution of the problem for which the cost of the project is minimal. The paper presents genetic operators as well as GPM specified for the DGP. Experimental results showed that our approach gives significantly better results compared with methods presented in the literature.(original abstract)
Full text
Show
Bibliography
Show
  1. Ahn, T. and Erenguc, S. (1998). The resource constrained project scheduling problem with multiple crashable modes: A heuristic procedure. European Journal of Operational Research, 107(2):250-259. DOI: 10.1016/S0377-2217(97)00331-7
  2. Alcaraz, J. and Maroto, C. (2001). A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102:83-109. DOI: 10.1023/A:1010949931021
  3. Blazewicz, J., Lenstra, J. K., and Kan, A. H. G. R. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5:11-24.
  4. Bouleimen, K. and 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. DOI: 10.1016/S0377-2217(02)00761-0
  5. Brucker, P., Knust, S., Schoo, A., and Thiele, O. (1998). A branch-and-bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 107:272-288. DOI: 10.1016/S0377-2217(97)00335-4
  6. Deiranlou, M. and Jolai, F. (2009). A new efficient genetic algorithm for project scheduling under resource constrains. World Applied Sciences Journal, 7(8):987-997. DOI: 10.1002/nav.10029
  7. Demeulemeester, E. L. and Herroelen, W. S. (1997). New benchmark results for the resource-constrained project scheduling problem. Management Science, 43:1485-1492. DOI: 10.1287/mnsc.43.11.1485
  8. Demeulemeester, E. L. and Herroelen, W. S. (2002). Project scheduling - A research handbook. International Series in Operations Research, Management Science, Boston, MA, USA.
  9. Deniziak, S. (2004). Cost-efficient synthesis of multiprocessor heterogeneous systems. Control and Cybernetics, 33:341-355.
  10. Deniziak, S. and Górski, A. (2008). Kosynteza systemów soc metoda rozwojowego programowania genetycznego. Wydawnictwo Politechniki Krakowskiej, in polish, 105(1-I):19-32.
  11. Deniziak, S. and Wieczorek, K. (2012). Evolutionary optimization of decomposition strategies for logical functions. In Proceedings of 11th International Conference on Artificial Intelligence and Soft Computing, volume 7269, page 182-189. Lecture Notes in Computer Science. DOI: 10.1007/978-3-642-29353-521
  12. Drexl, A., Patterson, J. H., and Salewski, F. (2000). Pro-Gen/px An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research, 125:59-72. DOI: 10.1016/S0377-2217(99)00205-2
  13. Frankola, T., Golub, M., and Jakobovic, D. (2008). Evolutionary algorithms for the resource constrained scheduling problem. In Proceedings of 30th International Conference on Information Technology Interfaces, volume 7269, page 715-722. Information Technology Interfaces.
  14. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co. and Inc., Boston, MA, USA.
  15. Hartmann, S. (1998). A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics, 45:733-750. DOI: 10.1002/(SICI)1520-6750(199810)45:7¡733::AID-NAV5¿3.0.CO;2-C
  16. Hartmann, S. and Briskorn, D. (2010). Survey of variants and extensions of the resource-constrained project scheduling problem. European journal of operational research, 207:1-15. DOI: 10.1016/j.ejor.2009.11.005
  17. Jedrzejowicz, P. and Ratajczak-Ropel, E. (2014). Reinforcement Learning Strategy for Solving the Resource-Constrained Project Scheduling Problem by a Team of A-Teams. Intelligent Information and Database Systems, page 197-206. DOI 10.1007/978-3-642-40495-546
  18. Keller, R. E. and Banzhaf, W. (1999). The evolution of genetic code in genetic programing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), page 1077-1082. Information Technology Interfaces.
  19. Kolisch, R. and Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European journal of operational research, 174:23-37. DOI: 10.1016/j.ejor.2005.01.065
  20. Kolish, R. and Sprecher, A. (1996). Psplib - a project scheduling library. European journal of operational research, 96:205-216.
  21. Koza, J., Keane, M. A., Streeter, M. J., Mydlowec, W., Yu, J., and Lanza, G. (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers.
  22. Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
  23. Koza, J. R. (2010). Human-competitive results produced by genetic programming. Genetic Programming and Evolvable Machines, 11:251-284. DOI 10.1007/s10710-010-9112-3
  24. Koza, J. R. and Poli, R. (2005). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer, New York, NY, USA.
  25. Mingozzi, A., Maniezzo, V., Ricciardelli, S., and Bianco, L. (1998). An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Management Science, 44:714-729.
  26. M̈ohring, R. H., Shulz, A. S., Stork, F., and Utez, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49(3):330-350. DOI: 10.1287/mnsc.49.3.330.12737
  27. [Pawiński and Sapiecha, 2013] Pawiński, G. and Sapiecha, K. (2013). Cost-efficient project management based on distributed processing model. In Proceedings of the 21th International Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2013), page 157-163. IEEE Computer Society. DOI: 10.1109/PDP.2013.30
  28. Pinedo, M. and Chao, X. (1999). Operations Scheduling with applications in Manufacturing. Irwin/McGraw-Hill, Boston, New York, NY, USA, 2nd edition.
  29. Skowronski, M. E., Myszkowski, P., Adamski, M. and Kwiatek, P. (2013) Tabu search approach for Multi-Skill Resource-Constrained Project Scheduling Problem. In Federated Conference on Computer Science and Information Systems (FedCSIS 2013), page 153-158. IEEE Computer Society.
  30. Watson, J. D., Hopkins, N. H., Roberts, J. W., Steitz, J. A., and Weiner, A. M. (1992). Molecular Biology of the Gene. Benjamin Cummings, Menlo Park, CA.
  31. Zamani, R. (2013). Integrating iterative crossover capability in orthogonal neighborhoods for scheduling resource-constrained projects. Evolutionary Computation, 21(2):341-360. DOI: i:10.1162/EVCOa00085
Cited by
Show
ISSN
2300-5963
Language
eng
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu