While the Dedicated policy may be preferable to the M/G/k/FCFS and Shortest-Queue policies for highly variable job sizes, it is clearly not optimal. One problem is that Dedicated leads to situations where the servers are not fully utilized: five consecutive short jobs may arrive, with no long job, resulting in an idle long host. This is especially likely in common computer workloads, where there are many short jobs and just a few very long jobs, resulting in longer idle periods between the arrivals of long jobs.
Ideally we would like a policy which combines the variance reducing benefit of the Dedicated policy with the high utilization property of M/G/k/FCFS and Shortest-Queue. Hereby, we would segregate jobs by size to provide isolation for short jobs, but when the long job host is free, we would steal the long host's idle cycles to serve excess short jobs. This would both decrease the mean response time of the short jobs, and enlarge the stability region of the overall system. Specifically, for systems where the short host is much more heavily loaded, granting the short jobs limited access to the long partition may be the difference between an overloaded system and a well behaved one. We grant the short jobs access to the long host only when the long host is free, so we don't starve the long jobs, causing them undue delay. Nonetheless, because jobs are not preemptive, there will still be a penalty to a long job which arrives to find a short job serving at the long host.
Specifically, we propose the following two size-based task assignment policies with cycle stealing.