Packet scheduling in networks with quality of service constraints has been extensively studied as a single criterion scheduling
problem. The assumption underlying single criterion packet scheduling is that the value of all packets can be normalized to
a single scale, even in cases when packets have different requirements. We demonstrate that this approach can lead to inefficient
utilization of network resources.
To improve network efficiency, we model packet scheduling as a mixed criteria scheduling problem where there are two distinct sets of jobs: 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 deadline
jobs are scheduled to maximize the value of jobs that complete by their deadlines.
We demonstrate that even when there is only a single deadline job, this mixed criteria scheduling problem is NP-Complete.
We give a polynomial time optimal algorithm Slacker for the variant where all jobs have unit size and the value of deadline
jobs processed by the deadline must be maximized. Given this constraint Slacker minimizes the total flow time. Furthermore,
we show that online Slacker is optimal for flow time while being 2-competitive with respect to the deadline jobs when compared
to an optimal algorithm like Slacker that maximizes the value of deadline jobs.