In: Theoretical Computer Science, Volume 270, Issue 1-2, pages 525-560. January 2002.
Abstract: In a heap model, solid blocks, or pieces, pile up according to the Tetris game mechanism. An optimal schedule is an infinite sequence of pieces minimizing the asymptotic growth rate of the heap. In a heap model with two pieces, we prove that there always exists an optimal schedule which is balanced, either periodic or Sturmian. We also consider the model where the successive pieces are chosen at random, independently and with some given probabilities. We study the expected growth rate of the heap. For a model with two pieces, the rate is either computed explicitly or given as an infinite series. We show an application for a system of two processes sharing a resource, and we prove that a greedy schedule is not always optimal.
Keywords: Optimal scheduling; Timed Petri net; Heap of pieces; Tetris game; (max,+) semiring; Automaton with multiplicities, Sturmian word.