Scheduling Algorithms for new Emerging Applications

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

Mixed criterion scheduling

SpeakerEric Torng

Co-authorChad Meiners

We consider a scheduling problem that models a simplified variant of providing different levels of quality of service to different network clients. In our scheduling problem, there are two distinct sets of preemptable jobs: hard-deadline jobs which represent real-time packets in a network and flow jobs which represent other packets in the network. As the names imply, the jobs in these two sets differ by the criteria associated with them. For this problem, the flow jobs are scheduled to minimize the sum of their flow times, and the hard-deadline jobs are scheduled so that no job misses its deadline.

We show that our mixed criterion scheduling problem, which we have named the DeadFlow problem, is NP-Complete. We consider two simplified variants of the DeadFlow problem. We show the first variant in which there is only one hard-deadline job is NP-complete. We present a polynomial time algorithm that solves the second variant where the jobs are of unit size.