\input zb-basic
\input zb-ioport
\iteman{io-port 05204521}
\itemau{Subramani, K.; Desovski, D.}
\itemti{An empirical analysis of algorithms for partially clairvoyant scheduling.}
\itemso{Int. J. Parallel Emergent Distrib. Syst. 22, No. 5, 331-353 (2007).}
\itemab
Summary: We contrast the performance of three algorithms for the problem of deciding whether a partially clairvoyant real-time system with relative timing constraints, as specified in the E-T-C scheduling framework, has a feasible schedule. In the E-T-C scheduling model, real-time scheduling problems are specified through a specialized class of Constraint Logic Programs (CLPs) called Quantified Linear Programs (QLPs) [{\it K. Subramani}, Lect. Notes Comput. Sci. 2731, 265--277 (2003; Zbl 1038.90052)]; thus algorithms for determining the schedulability of instances are procedures to determine the satisfiability of CLPs. Two of these algorithms, viz., the primal algorithm and the dual algorithm have already been discussed in the literature, while a third algorithm called the randomized dual algorithm has been recently proposed by the authors [Lect. Notes Comput. Sci. 3829, 127--141 (2005; Zbl 1124.68014), J. Symb. Comput. 40, 1383--1396 (2005; Zbl 1125.68142)]. Our experiments demonstrate that the dual-based algorithms (i.e. the dual and the randomized dual) are more effective from an implementational perspective; this is surprising since all three algorithms have the same worst case asymptotic complexity.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1080/17445760601029560}
\end