Analysis of scheduling problems with typed task systems

In this paper a scheduling problem has been analysed where each task has a type and where only a bounded number of processors of each type is available. It is shown 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 a polynomial algorithm is given if there is an interval order.