Bacon and eggs: task scheduling into batches
The time to cook bacon and eggs is less than
the time to cook bacon plus the time to cook eggs.
This suggest the following abstract model for tasks which are better done in batches
For any online
algorithm there is a number
- Tasks arrive to an "inbox" at times of a Poisson process of rate 1.
task is of a random "type", uniform on type-space [0,1].
- The (non-random) time needed to process a set B of tasks is a given function S(B).
- The function S(B) is assumed to be monotone and subadditive: for disjoint sets
A and B,
0 < S(A) < S(A B) < S(A) + S(B) .
- After a batch completes processing, the scheduler looks at the current set A of
items in the inbox and uses an algorithm to choose a subset B \subseteq A to process
as the next batch.
- An item of type a incurs cost c(a) per unit time, from its arrival time until
the time at which the batch containing it is finished.
W = long-run average cost per unit time
arising from the waiting time costs.
Let W* be the minimum, over all online algorithms, of W, and assume W* is finite.
The value of W* and the optimal algorithm depend in some complicated way on the
functions S( ) and c( ).
Problem: Is there some explicit algorithm (depending of course on S( ) and c(
)) and a constant C such that the W for this algorithm
$W/W* < C$ for all S( ) and c( )?
Conceptually, I guess that at both ends (light traffic or heavy traffic) some simple
algorithm would work; the issue in the intermediate case. This
paper shows that in the c = 1 context, the greedy algorithm (put everything in
one batch) has finite W whenever any