Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems

Abstract

In this paper computational results are presented with a very general, yet powerful backtracking procedure for solving the duration minimization and net present value maximization problems in a precedence and resource-constrained network. These networks are generally of the PERT/CPM variety, although it is not required that they be so. Among the advantages cited for our approach are low computer memory (storage) requirements and the ability to obtain improved solutions rapidly (heuristic properties). Since the resource-constrained project scheduling problem subsumes the job shop, flow shop, assembly line balancing, and related scheduling problems, our procedure can be used with little or no modification to solve a wide variety of problem types. Computational experience is reported for both mainframe and personal computer implementations.