Aggregating Alphabets to Construct Balanced Words
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
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.