Fast scheduling of periodic tasks on multiple resources

Abstract

Given n periodic tasks, each characterized by an execution requirement and a period, and m identical copies of a resource, the periodic scheduling problem is concerned with generating a schedule for the n tasks on the m resources. We present an algorithm that schedules every feasible instance of the periodic scheduling problem, and runs in O(min{mlgn,n}) time per slot scheduled.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>