A Developmental Genetic Approach to the cost/time trade-off in Resource Constrained Project Scheduling

• Autorzy: Grzegorz Pawiński , Krzysztof Sapiecha
• Języki publikacji: EN

Abstrakty

EN

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)

Słowa kluczowe

EN

Genetic algorithms; Genetic programming; Project planning

PL

Algorytmy genetyczne; Programowanie genetyczne; Planowanie projektu

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 171--179

Twórcy

autor

Grzegorz Pawiński

• Kielce University of Technology, Kielce, Poland

autor

Krzysztof Sapiecha

• Cracow University of Technology, Poland

Bibliografia

• 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
• 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
• 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.
• 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
• 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
• 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
• 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
• Demeulemeester, E. L. and Herroelen, W. S. (2002). Project scheduling - A research handbook. International Series in Operations Research, Management Science, Boston, MA, USA.
• Deniziak, S. (2004). Cost-efficient synthesis of multiprocessor heterogeneous systems. Control and Cybernetics, 33:341-355.
• 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.
• 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
• 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
• 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.
• Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co. and Inc., Boston, MA, USA.
• 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
• 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
• 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
• 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.
• 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
• Kolish, R. and Sprecher, A. (1996). Psplib - a project scheduling library. European journal of operational research, 96:205-216.
• 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.
• Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
• 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
• Koza, J. R. and Poli, R. (2005). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer, New York, NY, USA.
• 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.
• 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
• [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
• Pinedo, M. and Chao, X. (1999). Operations Scheduling with applications in Manufacturing. Irwin/McGraw-Hill, Boston, New York, NY, USA, 2nd edition.
• 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.
• 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.
• 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