Preemptive scheduling and antichain polyhedra |
| |
Authors: | Alain Quilliot |
| |
Affiliation: | Université BLAISE PASCAL and CNRS, LIMOS Laboratory, LIMOS, UMR CNRS 6158, Bat ISIMA, Campus des Cézeaux BP 10125, 63173 Aubière, France |
| |
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. |
| |
Keywords: | Partially ordered sets Hypergraphs Linear programming Multiprocessor scheduling |
本文献已被 ScienceDirect 等数据库收录! |
|