Scheduling Tasks with Nonuniform Deadlines on Two Processors

Abstract

Given a set @@@@ = { T ₁ , T ₂ ,···, T _n } of tasks, with each T _i having execution time 1 and a deadline d _i > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.