Aggregating Alphabets to Construct Balanced Words

Loading...
Thumbnail Image

Files

Balanced_2009.4.pdf (416.86 KB)
No. of downloads: 649

Publication or External Link

Date

2009-09

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.

Notes

Rights