Totally Clairvoyant Scheduling with Relative Timing Constraints

摘要

Traditional scheduling models assume that the execution time of a job in a periodic job-set is constant in every instance of it execution. This assumption does not hold in real-time systems wherein job execution time is known to vary. A second feature of traditional models is their lack of expressiveness, in that constraints more complex than precedence constraints (for instance, relative timing constraints) cannot be modeled. Thirdly, the schedulability of a real-time system depends upon the degree of clairvoyance afforded to the dispatcher. In this paper, we shall discuss Totally Clairvoyant Scheduling, as modeled within the E-T-C scheduling framework. We show that instantiation of the scheduling framework captures the central issues in a real- time flow-shop scheduling problem and design a polynomial time sequential algorithm for the same. We also introduce an error-minimizing performance metric called Violation Degree and establish that optimizing this metric in a Totally Clairvoyant Scheduling System in NP-Hard.