A new improved genetic algorithm approach and a competitive heuristic method for large-scale multiple resource-constrained project-scheduling problems

Khanzadi, M.; Soufipour, R.; Rostami, M.

Abstract: The aim of this paper is to present a new genetic algorithm approach for large scale multiple resource-constrained project-scheduling problems (RCPSP). It also presents a heuristic approach to achieve proper solutions for large scale problems. This research area is very common in industry especially when a set of activities needs to be finished as soon as possible subject to two sets of constraints, precedence constraints and resource constraints. The emphasis in this research is on investigating the complexity of scheduling problems and developing a new GA approach to solve this problem in such a way that the advantages of GA are appropriately utilized by applying a novel method to reduce the complexity of the problem. Computational results are also reported for the most famous classical problems taken from the operational research literature.

How to cite this paper

        APA: Khanzadi, M., Soufipour, R & Rostami, M. (2011). A new improved genetic algorithm approach and a competitive heuristic method for large-scale multiple resource-constrained project-scheduling problems. International Journal of Industrial Engineering Computations, 2(4), 737-748.
    

        Chicago/Turabian: Khanzadi, M., Soufipour, R & Rostami, M. 2011. "A new improved genetic algorithm approach and a competitive heuristic method for large-scale multiple resource-constrained project-scheduling problems." International Journal of Industrial Engineering Computations 2, no. 4 (2011): 737-748.
    

        AMA: Khanzadi, M., Soufipour, R & Rostami, M. A new improved genetic algorithm approach and a competitive heuristic method for large-scale multiple resource-constrained project-scheduling problems. International Journal of Industrial Engineering Computations. 2011;2(4):737-748.
    

References

Akbari, R., Zeighami, V., & Ziarati, K. (2011). Artificial Bee colony for resource constrained project scheduling problem. International Journal of Industrial Engineering Computations, 2(1), 45-60.

Alcaraz, J., Maroto, C., Ruiz, R. (2004). Improving the performance of genetic algorithms for the RCPS problem. In: Proceedings of the ninth international workshop on project management and scheduling, 40–43.

Alcaraz, J., Maroto, C. (2001). A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102, 83–109.

Agarwal, A., Colak, S., & Erenguc, S. (2011). A Neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, 38(1), 44–50.

Christofides, N., Alvarez-Valdes, R., & Tamarit, J.M. (1987). Project scheduling with resource constraints: a branch and bound approach. European Journal of Operational Research, 29, 262-273.

Colak, S., Agarwal, A., & Erenguc, S. S. (2006). Resource-constrained project scheduling problem: a hybrid neural approach. In: Weglarz J, Jozefowska J, editors. Perspectives in modern project scheduling, 297–318.

Conway, R. W., Maxwell, W. L. & Miller, L. W. (1967). Theory of scheduling. Addison-Wesley, Mass.

Daellenbach, H. & George, J. (1979). Operation Research Techniques. Allyn and Bason.

David, E. G. & R. Lingle (1985). Alleles, Loci and the Traveling Salesman Problem, Proceeding of the First International Conference on Genetic Algorithms. Carne-Mellon University, Pittsburg, PA.

Davis, L. (1985). Job shop scheduling with genetic algorithms. Proceeding of the First International Conference on Genetic Algorithms, Carne-Mellon University, Pittsburg, PA.

Debels, D., & Vanhoucke M. (2007). A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Research, 55(3), 457–469.

Debels, D., De Reyck, B., Leus, R., & Vanhoucke, M. (2006). A hybrid scatter search/ electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research, 169(2):638–653.

Dell'Amico, M., & Trobian, M. (1993). Applying tabu search to the job shop scheduling problem. Annals of Operations Research, 41, 231-252.

Fayer, F. B. (1990). Some efficient multi-heuristic procedures for resource-constrained project scheduling. European Journal of Operational Research, 49 (1), 3-13.

Garfinkel, R. S. & Nemhauser, G. L. (1972). Integer Programming, John Wiley, New York.

Gonçalves, J.F. Mendes, J.J., & Resende, M.G.C. (2006) A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research, 189,1171–1190.

Grefenstette, J. J. (1986). Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1),122-128.

Hartmann, S. (2002). A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 49, 433-448.

Jean, Y. P. (1996). Genetic Algorithms for the Traveling Salesman Problem. Annual of Operations Research. 63, 339-370.

Kim, K. W. & Gen, M., & Yamazaki, G. (2003). Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling. Applied Soft Computing 2 (3F), 174-188.

Kochetov, Y., Stolyar, A. (2003). Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. In: Proceedings of the third international workshop of computer science and information technologies, Russia.

Kolisch, R., & Sprecher, A. (1996). PSPLIB – A project scheduling library. European Journal of Operational Research. 96, 205-216.

Kolisch, R., & Padman, R. (2001). An integrated survey of deterministic project scheduling . The International Journal of Management Science (omega), 29, 249-272.

Mahdi Mobini, M.D, Rabbani, M., Amalnik ,M.S., Razmi, J., Rahimi-Vahed, A.R. (2009). Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem. Soft Computing, 13, 597–610.

Merkle, D. M. M.&Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. Evolutionary Computation. IEEE Transactions, 6 (4), 333-346.

Nowicki, E. & Smutnicki, C. (1996). A fast tabu search algorithm for the job shop problem. Management Science, 42(6),797-813.

Oliver, I. M., Smith, D.J., & Holland , J. R. C. (1987). A study of Permutation Crossover Operators on the Travelling Salesman Problem, paper presented to Proceeding of the Second International Conference on Genetic Algorithms. Lawrence Erlbaum Association, Hillsadale, NJ.

Patterson, J. H., & Huber, W. D. (1974). A horizon-varying, zero-one approach to project scheduling. Management Science, 20 (6), 990-998.

Philippe, B., Claude, L. P., & Wim, N. (2001). Constraint-based scheduling; applying constraint programming to problems. Kluwer Academic Publishers, Massachusetts, USA.

Ranjbar, M. (2008). Solving the resource constrained project scheduling problem using filter-and-fan approach. Applied Mathematics and Computations, 201, 313–318.

Ranjbar, M., Reyck, B.D., Kianfar, F. (2009). A hybrid scatter search for the discreet time/resource trade-off problem in project scheduling. European Journal of Operational Research, 193, 35–48.

Tchomte, S.K., Gourgand, M., & Quilliot, A. (2007). Solving resource-constrained project scheduling problem with particle swarm optimization. In: Proceedings of fourth multidisciplinary international scheduling conference, 251–258.

Tormos, P., & Lova, A. (2003). An efficient multi-pass heuristic for project scheduling with constrained resources. International Journal of Production Research, 41(5), 1071–1086.

Tormos, P., & Lova, A. (2001). A competitive heuristic solution technique for resource constrained project scheduling. Annals of Operations Research, 102, 65–81.

Valls, V., Ballestin, F., & Quintanilla, S. (2008). A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 185, 495-508.

Valls, V., Ballestin, F., Quintanilla, M.S. (2005). Justification and RCPSP: a technique that pays. European Journal of Operational Research, 165(2), 375–386.

Wall, M. B. (1996). A Genetic Algorithm for Resource-Constrained Scheduling, Ph.D. thesis, Massachusetts Institute of Technology.