Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419835 | Discrete Applied Mathematics | 2008 | 9 Pages |
Abstract
We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alain Quilliot,