Generalized pre-scheduler

A preschedule is a list of "executives" generated offline for a set of time-driven jobs. If in addition there exists event-driven workload competing for resources, sufficient slacks must be embedded in a valid preschedule. A prescheduler was defined in Wang et al. (2003) with the following assumptions: the competing workload is modeled as sporadic tasks and the time-driven jobs to be prescheduled are independent. In this paper, the prescheduling problem is generalized. First, the event-driven workload is no longer limited to sporadic tasks or any specific task model. Instead, a concept called "prescheduling space" is introduced so that the time-driven jobs to be prescheduled are inside the space, the competing event-driven workload is outside the space, and resource competition is abstracted to the space bounded by a supply function and a supply contract. Second, precedence constraints between the time-driven jobs to be prescheduled are allowed. The generalized prescheduler presented in this paper produces a valid preschedule if and only if one exists under the constraints of execution time bounds, valid scopes, precedence requirements and supply contract; otherwise, it returns a notice of failure. The generalized prescheduler runs in time polynomial to the number of time-driven jobs.