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 than separately.

Tasks arrive to an "inbox" at times of a Poisson process of rate 1.
Each 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 \cup 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.

For any online algorithm there is a number

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(\cdot )\) and \(c(\cdot )\).

Problem: Is there some explicit algorithm (depending of course on \(S(\cdot )\) and \( c(\cdot ))\) and a constant C such that the W for this algorithm satisfies \( W/W_* < C \) for all \(S(\cdot )\) and \( c(\cdot ))\)?

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 algorithm does.

History. Problem posted March 2009.

Back to Open Problem list