Work in Progress: The ILP-Tractability of Schedulability Analysis Problems
Sanjoy Baruah · 2020
Algorithms used for the pre-runtime analysis of safety-critical systems have traditionally been required to have running times no worse than pseudo-polynomial in the size of their inputs. Some recent work, however, has been motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers and a concurrent widespread and inexpensive availability of increasing computing capabilities, to consider the use of ILP solvers as acceptably efficient for the purposes of such analysis. In this paper, the concept of ILP-tractability is proposed as a formal characterization of the class of scheduling problems that can be solved efficiently under this newer interpretation of efficiency. Techniques are presented for showing a problem to be ILP-tractable, as well as for showing a problem to be ILP-intractable - i.e., it cannot be solved efficiently using ILP solvers.