Analysis of scheduling problems with typed task systems (Q1331888)

This paper deals with the analysis of a scheduling problem where each task has a type and where only a bounded number of processes 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 disjoint union of chains.