Advances in Computer Science : an International Journal
A bi-population genetic algorithm with two novel greedy mode selection methods for MRCPSP
Abstract
The multimode resource-constrained project scheduling problem (MRCPSP) is an extension of the single-mode resource-constrained project scheduling problem (RCPSP). In this problem, each project contains a number of activities which precedence relationship exist between them besides their amount of resource requirements to renewable and non-renewable resources are limited to the resources availabilities. Moreover, each activity has several execution modes, that each of them has its amount of resource requirements and execution duration. The MRCPSP is NP-hard, in addition, proved that if at least 2 non-renewable resources existed, finding a feasible solution for it is NP-complete. This paper introduces two greedy mode selection methods to assign execution modes of the primary schedules’ activities in order to balance their resource requirements and thus reduce the number of infeasible solutions in the initialization phase of a bi-population genetic algorithm for the problem. To investigate the usage effect of these greedy methods on the quality of the final results, in addition, to evaluating the performance of the proposed algorithm versus the other meta-heuristics, the instances of the PSPLIB standard library have been solved. The computational results show that by the growth of the problem size, the proposed algorithm reports better results in comparison with the other metaheuristics in the problem literature.
Keywords
Full Text:
PDFReferences
Kolisch R, Drexl A (1997) Local search for non-preemptive multi-mode resource constrained project scheduling. IIE Transactions 29:987–999
Spreche A, Drexl A (1998) Multi-mode resource constrained project scheduling by a simple, general and powerful sequencing algorithm. European Journal of Operational Research 107:431–450, DOI 10.1016/S0377 2217(97)00348-2
Boctor F (1993) Heuristics for scheduling projects with resource restrictions and several resource-duration modes. International Journal of Production Research 31:2547–2558, DOI 10.1080/00207549308956882
Ling C (2004) A two-phase hybrid optimization for solving multi-mode resource-constrained project scheduling problems. Specializes in teaching 96:257–270
Jarboui B, Damak N, Siarry P, Rebai A (2008) A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation 195:299–308
Pourghaderi A, Torabi S, Talebi J (2008) Scatter search for multi-mode resource constrained project scheduling problems. In: Industrial Engineering and Engineering Management, IEEM 2008. IEEE International Conference, pp 163–167, DOI 10.1109/IEEM.2008.4737852
Lova A, Tormos P, Cervantes M, Barber F (2008) A hybrid genetic algorithm for the multi-mode resource constrained project scheduling problem. In: Eleventh International Workshop, PMS 2008, pp 189–192
Tseng L, Chen S (2009) Two-phase genetic local search algorithm for the multi-mode resource-constrained project scheduling problem. IEEE Transactions on Evolutionary Computation 13:848–857, DOI 10.1109/TEVC.2008.2011991
Elloumi S, Fortemps P (2010) A hybrid rank-based evolutionary algorithm applied to multi-mode resource constrained project scheduling problem. European Journal of Operational Research 205:31–41
Peteghem V, Vanhoucke M (2010) A genetic algorithm for the preemptive and nonpreemptive multi-mode resource constrained project scheduling problems. European Journal of Operational Research 201:409–418
Peteghem V, Vanhoucke M (2011) Using resource scarceness characteristics to solve the multi-mode resource constrained project scheduling problem. Journal of Heuristics 17:705–728, DOI 10.1007/s10732-010-9152-0
Muller L (2011) An adaptive large neighborhood search algorithm for the multimode rcpsp. DTU Management Engineering 3:25
Wang L, Fang C (2011) An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem. Computers and Operations Research 181:4804–4822, DOI 10.1016/j.ins.2011.06.014
Bilolikar V, Jain K, Sharma M (2012) An annealed genetic algorithm for multi-mode resource constrained project scheduling problem. International Journal of Computer Applications 60(1):36–42
Shen H, Li X (2013) Cooperative discrete particle swarms for multimode resource-constrained projects. In: IEEE 17th International Conference on Computer Supported Cooperative Work in Design, pp 31–36, DOI 10.1109/CSCWD.2013.6580935
Li H, Zhang H (2013) Ant colony optimization-based multi-mode scheduling under renewable and non-renewable resource constraints. Computers and Operations Research 35:431–438
Soliman O, Elgendi E (2014) A hybrid estimation of distribution algorithm with random walk local search for multi-mode resource-constr ined project scheduling problems. International Journal of Computer Trends and Technology 8:57–64
Coelho J, Vanhoucke M (2015) An approach using sat solvers for the rcpsp with logical constraints. European Journal of Operational Research DOI 10.1016/j.ejor.2015.08.044
Debels D, Vanhoucke M (2005) A bi-population based genetic algorithm for the resource-constrained project scheduling problem. Lecture Notes on Computer Science 3483:378–387
Talbot F (1982) Resource-constrained project scheduling with timeresource tradeoffs: The nonpreemptive case. Management Science 28:1197 1210
Holland J (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press
Kelley J (1963) The critical-path method: Resources planning and scheduling. In: Industrial Scheduling. Prentice-Hall, New Jersey, pp 347–365
Li K, Willis R (1992) An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research 56:370–379
Sprecher A, Hartmann S, Drexl A (1977) An exact algorithm for project scheduling with multiple modes. OR Spectrum 19:195–203
Kolisch R, Sprecher A (1997) Psplib - a project scheduling problem library: Or software-orsep operations research software exchange program. European Journal of Operational Research 96:205–216, DOI 10.1016/S0377 2217(96)00170-1
Hartmann S (2001) Project scheduling with multiple modes: a genetic algorithm. Annals of Operations Research 102:111–135
Alcaraz J, Maroto C, Ruiz R (2003) Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of the Operation Research Society 54:614–626
Kolisch R, Hartmann S (2006) Experimental investigation of heuristics for resource constrained project scheduling. European Journal of Operational Research 174:23–37
