Constructing Perfect Aggregations to Eliminate Response Time Variability in Cyclic Fair Sequences

Abstract

Fair sequences are useful in a variety of manufacturing and computer systems. This paper considers the generation of cyclic fair sequences for a given set of products, each of which must be produced multiple times in each cycle. The objective is to create a sequence so that, for each product, the variability of the time between consecutive completions is minimized. Previous work introduced an aggregation approach that can reduce response time variability (RTV) dramatically. However, in some cases, aggregating more carefully can generate sequences with zero RTV. We call this a perfect aggregation. This paper discusses properties of instances that have perfect aggregations. Moreover, we present techniques that can find a perfect aggregation if one exists.