Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling monotone sub-chain orders on typed task systems

SpeakerBenoît Dupont de Dinechin

A sub-chain order graph is a special case of interval order graph, that consists in the transitive closure of a chain plus independent tasks. We consider the machine model of typed task systems, where each operation has a type, and there is a given number of processors of each type. Typed task systems generalize parallel machines. We consider the feasibility of scheduling a UET typed task systems with release dates, deadlines, sub-chain order precedences, and precedence delays that are monotonic. We show this problem can be solved in polynomial time by extending the algorithm of Leung-Palem-Pnueli.