Aggregating Alphabets to Construct Balanced Words

Abstract

Balanced words are useful for scheduling mixed-model, just-in-time assembly lines, planning preventive maintenance, managing inventory, and controlling asynchronous transfer mode (ATM) networks. This paper considers the challenging problem of finding a balanced word (a periodic sequence) for a finite set of letters, when the desired densities of the letters in the alphabet are given. We present an aggregation approach that combines letters with the same density, constructs a word for the aggregated alphabet, and then disaggregates this word into a feasible word for the original alphabet. We consider two different measures for evaluating solutions and use the aggregation approach with different heuristics. Computational experiments show that using aggregation not only finds more balanced words but also reduces computational effort.