A bi-population genetic algorithm with two novel greedy mode selection methods for MRCPSP

Siamak Farshidi, Koorush Ziarati

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


Resource-constrained project scheduling; Multi-mode; Genetic algorithm; Makespan; Initialization

Full Text:

PDF

References


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




Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 cheap nike nfl jerseys Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys