Duality in the parametric polytope and its applications to a scheduling problem

Abstract

This thesis focuses on the twin goals of proposing scheduling models that are apposite for Real-Time Systems and designing efficient algorithms for queries of interest in these models. Our models find applications in diverse areas ranging from real-time process scheduling and database management to robotics and machine control. The unique feature of our scheduling models is the explicit accommodation of process parameter variability; in particular, we analyze the effect of non-constant execution times on schedulability queries. Our investigations commence with the study of relatively straightforward, but inflexible, Static Schedulability predicates, proceed through extremely flexible, though computationally “hard” Co-Static Schedulability queries and culminate in the analysis of Parametric Schedulability specifications. We establish that the scheduling flexibility afforded by Co-Static and Parametric specifications comes at a price; such specifications can be decided efficiently only for restricted constraint classes. Although our models were developed primarily for periodic job-sets with intra-period constraints, we show that there is a natural extension to accommodate job sets with inter-period constraints as well. We use fixed-point theorems to develop a simple algorithm for static scheduling in job-sets with inter-period constraints.