Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. (English) Zbl 1178.90161

Summary: This paper considers a project scheduling problem with the objective of minimizing resource availability costs required to execute the activities in a project by a given project deadline. The project contains activities interrelated by finish-start-type precedence relations with a time lag of zero, which require a set of renewable resources. Two metaheuristics, path relinking and genetic algorithm, are developed to tackle this problem in which a schedule is created with a precedence feasible priority list given to the schedule generation scheme. In these procedures, each new generation of solutions are created using the combination of current solutions. Comparative computational results reveal that path relinking is a very effective metaheuristic and dominates genetic algorithm.


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming


Tabu search
Full Text: DOI


[1] Herroelen, W.; Demeulemeester, E.; De Reyck, B., A classification scheme for project scheduling problems, (), 1-26, Chapter 1
[2] Möhring, R.H., Minimizing costs of resource requirements in project networks subject to a fix completion time, Operations research, 32, 89-120, (1984) · Zbl 0531.90049
[3] Demeulemeester, E., Minimizing resource availability costs in time limited project networks, Management science, 41, 1590-1598, (1995) · Zbl 0861.90071
[4] Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management science, 38, 1803-1818, (1992) · Zbl 0761.90059
[5] Drexl, A.; Kimms, A., Optimization guided lower & upper bounds for the resource investment problem, Journal of operational research society, 52, 340-351, (2001) · Zbl 1131.90378
[6] Yamashita, D.S.; Armentano, V.A.; Laguna, M., Scatter search for project scheduling with resource availability cost, European journal of operational research, 169, 623-637, (2006) · Zbl 1079.90066
[7] Tormos, P.; Lova, A., An efficient multi-pass heuristic for project scheduling with constrained resources, International journal of production research, 41, 1071-1086, (2003) · Zbl 1038.90038
[8] Shadrokh, S.; Kianfar, F., A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty, European journal of operational research, 181, 86-101, (2007) · Zbl 1121.90062
[9] Kolisch, R.; Hartmann, S., Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis, (), 147-178
[10] Burgess, A.R.; Killebrew, J.B., ;variation in activity level on a cyclic arrow diagram, Industrial engineering, 76-83, (1962), March-April
[11] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston · Zbl 0930.90083
[12] Debels, D.; De Reyck, B.; Leus, R.; Vanhoucke, M., A hybrid scatter search/electromagnetism meta-heuristic for project scheduling, European journal of operational research, 169, 638-653, (2006) · Zbl 1079.90051
[13] Holland, H.J., Adaptation in natural and artificial systems, (1975), The University of Michigan Press Ann Arbor
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.