On Certifying Instances of Zero-Clairvoyant Scheduling.

In this paper, we discuss certifying algorithms for zero-clairvoyant scheduling (ZCS) problems. ZCS problems are a class of real-time scheduling problems defined in the E-T-C scheduling framework [Subramani, K. (2005) A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. Comput. J., 48, 259–272]. In ZCS, the dispatcher has no knowledge of the execution time of a given job, even after the job has finished executing. A polynomial-time algorithm for ZCS was proposed in previous work of the first author [Subramani, K. (2007) A polynomial time algorithm for zero-clairvoyant scheduling. J. Appl. Logic, 5, 667–680]. However, the algorithm proposed therein is not certifying. The algorithm that we propose in this paper is certifying, in that it provides a structure that certifies the ‘yes’-instances and another structure that certifies the ‘no’-instances of ZCS problems. These structures make the discovery of implementation errors straightforward and greatly simplify the software development cycle. Moreover, the certifying algorithm has the same running time (asymptotically) as its non-certifying counterpart. We also show that the proposed certifying technique can be used to certify a class of mathematical programs called E-Quantified Polyhedral programs (E-QPPs). However, for E-QPPs, the proposed certifying algorithm has a higher asymptotic running time than its non-certifying counterpart. [ABSTRACT FROM AUTHOR]