ON SCHEDULING A NETWORK OF ACTIVITIES UNDER RESOURCE RESTRAINTS OVER TIME,
Abstract
A project is taken as a finite set of activities satisfying given precedence relations, with each activity having a known duration time. A common resource, say manpower, is shared by the individual activities, and a profile of amount required is specified for each over its duration interval. Also given is an overall profile of resource available to P. The scheduling of P is formulated in discrete terms; an optimal schedule is one that minimizes the lifetime of P relative to all feasible schedules. One question considered relates to enumeration of schedules to find an optimal one. We define a certain subclass of feasible schedules, generated by left-packing of activities in any linear order consistent with the precedence relations. It is proven that the subclass contains an optimal schedule if all activity profiles are nonincreasing. The result fails if monotonicity is dropped. Another question is that of assigning individual workers to activities in a feasible schedule so as to realize 'maximal continuity of assignment.' It is shown that this property is not realizable in general, but that it is under the assumption that profiles of all activities are 'single-peaked' (this includes monotonic profiles). Results apply to several resources as well as to a single one. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 15, 1966
- Accession Number
- AD0648749
Entities
People
- W. Karush
Organizations
- System Development Corporation