The affine hull of the schedule polytope for servicing identical requests by parallel devices

Under consideration are some polyhedral properties of the set of schedules for servicing identical requests by parallel devices. The requests satisfy some precedence conditions. Any service interruptions are prohibited. We propose some formalization of the set of schedules as a family of subsets of a finite set, define the polytope of schedules, and find the affine hull and dimension of this polytope. We also obtain the conditions under which the inequalities determining its polyhedral relaxation are the support inequalities. Tab. 1, illustr. 2, bibliogr. 20.