ANALYSIS OF SCHEDULING PROBLEMS WITH TYPED TASK SYSTEMS

In this paper we have analysed a scheduling problem where each task has a type and where only a bounded number of processors of each type is available. We show that the typed scheduling problem remains NP-complete for a disjoint set of chains, two types and one processor of each type. If the deadline is a constant number, this problem, given k processors, remains NP-complete for out-trees, in-trees and a disjoint union of chains. In contrast we give a polynomial algorithm if we have an interval order.