×

Scheduling project networks with resource constraints and time windows. (English) Zbl 0693.90047

Multi-attribute decision making via O.R.-based expert systems, Proc. Int. Conf., Passau/FRG 1986, Ann. Oper. Res. 16, No. 1-4, 201-240 (1988).
Summary: [For the entire collection see Zbl 0689.00017.]
Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.
We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.
The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [see E. Balas, in: Appl. of Math. Programming, ed. E. M. L. Beale, The English Univ. Press, London 1971, 187-200] and the order theoretic methods for precedence constrained scheduling [see R. H. Möhring, Oper. Res. 32, 89-120 (1984; Zbl 0531.90049), F. J. Radermacher, “Kapazitätsoptimierung in Netzplänen” (1978; Zbl 0397.90060), and F. J. Radermacher, Ann. Oper. Res. 4, No.1-4, 227- 252 (1985; Zbl 0693.90046)]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch- and-bound algorithms. Computational experience with this algorithm is reported.

MSC:

90B35 Deterministic scheduling theory in operations research
90B10 Deterministic network models in operations research