An exact algorithm for minimizing resource availability costs in project scheduling. (English) Zbl 1188.90108

Rodrigues, Sávio B.; Yamashita, Denise S.

Eur. J. Oper. Res. 206, No. 3, 562-568 (2010).

Summary: A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

project scheduling; resource availability; exact algorithm

Software:

PSPLIB

References:

[1]	Blazewicz, J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Scheduling subject to resource constraints: classification and complexity, Discrete applied mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[2]	Brucker, P.; Drexl, A.; Mohring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models and methods, European journal of operational research, 112, 3-41, (1999) · Zbl 0937.90030
[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, S., 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 and upper bounds for the resource investment problem, Journal of the operational research society, 52, 340-351, (2001) · Zbl 1131.90378
[6]	Hartmann, S.; Kolisch, R., Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European journal of operational research, 127, 394-407, (2000) · Zbl 0985.90036
[7]	Hartmann, S.; Kolisch, R., Experimental investigation of heuristics for resource-constrained project scheduling: an update, European journal of operational research, 17, 23-37, (2006) · Zbl 1116.90047
[8]	Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: A survey of recent developments, Computers & operations research, 25, 279-302, (1998) · Zbl 1040.90525
[9]	Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management science, 41, 1693-1703, (1995) · Zbl 0870.90070
[10]	Kolisch, R.; Hartmann, S., Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis, (), 147-178
[11]	Möhring, R.F., Minimizing costs of resource requirements in project networks subject to a fixed completion time, Operations research, 32, 89-120, (1984) · Zbl 0531.90049
[12]	Rangaswamy, B., 1998. Multiple Resource Planning and Allocation in Resource-Constrained Project Networks. Ph.D. Thesis, Graduate School of Business, University of Colorado.
[13]	Ranjbar, M.; Kianfar, F.; Shadrokh, S., Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm, Applied mathematics and computation, 196, 879888, (2008) · Zbl 1178.90161
[14]	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
[15]	Tormos, P.; Lova, A., An efficient multi-pass heuristics for project scheduling with constrained resources, International journal of production research, 41, 1071-1086, (2003) · Zbl 1038.90038
[16]	Yamashita, D.S.; Armentano, V.A.; Laguna, M., Scatter search for project scheduling with resource availability cost. special issue on scatter search, European journal of operational research, 169, 623-637, (2006) · Zbl 1079.90066