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

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 the present approach are low computer memory (storage) requirements and the ability to obtain improved solutions rapidly (heuristic properties). Since the resource-constrained roject scheduling problem subsumes the job shop, flow shop, assembly line balancing, and related scheduling problems, the 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.