PROJECT SCHEDULING WITH RESOURCE CONSTRAINTS.
Abstract
Critical path and network flow techniques can solve project scheduling problems of a realistic size when there are no resource constraints; the introduction of the latter, however, changes the problem into one in which the number of variables and constraints depends on the number of time periods, and which existing methods can solve only for a very small size. The purpose of this paper is to reformulate the scheduling problem with resource constraints in a way that should eliminate the dependence of problem size on the number of time periods and should make this problem amenable to critical path - and network flow techniques. Thus, scheduling with resource constraints is shown to be equivalent to the problem of finding an optimal selection of arcs in a disjunctive graph with stability conditions. 'Simple' machine sequencing and machine sequencing with sets of identical machines are shown to be special cases of this model. The scheduling problem with resource constraints can thus be solved by generating a sequence of PERT networks which satisfy certain stability conditions. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1968
- Accession Number
- AD0679621
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University