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.

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