Solving resource-constrained project scheduling problems with bi-criteria heuristic search techniques

Abstract

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm for solving multiple resource-constrained project scheduling problems. The heuristic solves problems in two phases. In the pre-processing phase, the algorithm estimates distance between a state and the goal state and measures complexity of problem instances. In the search phase, the algorithm uses estimates of the pre-processing phase to further estimate distances to the goal state. The search continues in a stepwise generation of a series of intermediate states through search path evaluation process with backtracking. Developments of intermediate states are exclusively based on a bi-criteria new state selection technique where we consider resource utilization and duration estimate to the goal state. We also propose a variable weighting technique based on initial problem complexity measures. Introducing this technique allows the algorithm to efficiently solve complex project scheduling problems. A numerical example illustrates the algorithm and performance is evaluated by extensive experimentation with various problem parameters. Computational results indicate significance of the algorithm in terms of solution quality and computational performance.

Keywords

Resource-constrained project scheduling / search algorithm / heuristics / state-space representation

References

[1] Ahsan, M.K., Tsao, D., “A heuristic search algorithm for solving resource-constrained project scheduling problems”, Asia-Pacific Journal of Operational Research, Vol. 20, No.2, 2003 (In press).

[2] Alvarez-Valdés R., Tamarit J.M.. Slowiński R., Węglarz J.. Heuristic algorithm for resource-constrained project scheduling: a review and an empirical analysis. Advances in Project Scheduling, 1989, Amsterdam: Elsevier 113-134.

[3] Bell C.E., Han J.. A new heuristic solution method in resource-constrained project scheduling. Naval Research Logistics, 1991, 38: 315-331.

[4] Bell C.E., Park K.. Solving resource-constrained project scheduling problems by A* search. Naval Research Logistics, 1990, 37: 61-84.

[5] Brucker P., Knust S., Schoo A., Thiele O.. A branch and bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 1998, 107: 272-288.

[6] Cho J.H., Kim Y.D.. A simulated annealing algorithm for resource-constrained project scheduling problems. Journal of the Operational Research Society, 1997, 48: 736-744.

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

[8] Demeulemeester E., Herroelen W.. A branch-and-bound procedure for the multiple resource-constrained projects scheduling problem. Management Science, 1992, 38: 1803-1818.

[9] Hartmann S., Kolisch R.. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 2000, 127: 394-407.

[10] Hartmann S.. A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics, 1998, 45: 733-750.

[11] Hartmann S.. A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 2002, 49: 433-448.

[12] Klein R.. Bidirectional planning: improving priority rule-based heuristics for scheduling resource constrained projecrts. European Journal of Operational Research, 2000, 127: 619-638.

[13] Kolisch R., Sprecher A., Drexl A.. Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, 1995, 41: 1693-1703.

[14] Kolisch R., Sprecher A.. PSPLIB-A project scheduling problem library. European Journal of Operational Research, 1996, 96: 205-216.

[15] Kolisch R.. Serial and parallel resource-constrined project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 1996, 90: 320-333.

[16] Kolisch R.. Efficient priority rule for the resource-constrained project-scheduling problem. Journal of Operations Management, 1996, 14: 179-92.

[17] Kolisch R., Drexl A.. Adaptive search for solving hard project scheduling problems. Naval Research Logistics, 1996, 43: 23-40.

[18] Korf R.. Real time heuristic search. Journal of Artificial Intelligence, 1990, 42: 189-211.

[19] Lee J.K., Kim Y.D.. Search heuristics for resource constrained project scheduling. Journal of the Operational Research Society, 1996, 47: 678-689.

[20] Leon V., Ramamoorthy B.. Strength and adaptability of problem space based neighborhoods for resource-constrained scheduling. OR Spektrum, 1995, 17: 173-182.

[21] Patterson J. H.. A comparison of exact approaches for solving the multiple constrained resource, Project Scheduling Problem. Management Science, 1984, 30: 854-867.

[22] Pollack-Johnson B.. Hybrid structures and improving forecasting and scheduling in project management. Journal of Operations Management, 1995, 12: 101-117.

[23] Sprecher A.. Scheduling resource-constrained projects competitively at modest memory requirements. Management Science, 2000, 46: 710-723.

[24] Zamani R., Shue L.-Y.. Solving project-scheduling problems with a heuristic learning algorithm. Journal of the Operational Research Society, 1998, 49: 709-716.