Generating Cyclic Fair Sequences using Aggregation and Stride Scheduling

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. Because the problem is known to be NP-hard, we present a heuristic that combines aggregation and parameterized stride scheduling. This novel algorithm combines products with the same demand into groups, creates a sequence for those groups, and then disaggregates the sequence into a sequence for each product.