An algorithm for coalescing operations with precedence constraints in real-time systems (Q1261486)

In many applications, real-time systems are modeled as object-oriented systems, in which an object can make scheduling decisions in order to maximize the system performance. For instance, when a certain object is able to handle several distinct requests at the same time, the system performance may be sometimes improved by coalescing some of these requests into a single request. In most applications, the coalesced operations are defined by the programmer, and the decision regarding whether or not a coalescence should be performed is taken by the object scheduler based on using a reward table. Usually, the reward associated to a certain coalesced operation is a measure of the computational time saving corresponding to that coalescence. In the paper under review, the problem of finding a feasible coalescence schedule that produces the maximum total reward, is considered. It is assumed that only two primitive operations can be coalesced at a time, and an order \(O(n^ 2)\) time algorithm for scheduling two period jobs is developed. This algorithm is also extended for handling \(k\) periodic jobs with a time complexity \(O(k^ 2n^ 2)\). The algorithm described in the paper under review is an improvement of the algorithm proposed by \textit{M. I. Chen}, \textit{J. Y. Chung} and \textit{K. J. Lin} [``Scheduling algorithm for coalesced operations in real-time systems'', in: Proc. COMPSAC 89, Orlando, FL, 143-150 (1989)], which is of order \(O(n^ 6)\) time.