Finding optimally balanced words for production planning and maintenance scheduling

Balanced words are useful for scheduling mixed-model, just-in-time assembly lines; planning preventive maintenance; managing inventory; and controlling asynchronous transfer mode networks. This article 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. Two different measures of balance are considered. This article presents a branch-and-bound approach for finding optimally balanced words and presents the results of computational experiments to show how problem characteristics affect the time required to find an optimal solution. The optimal solutions are also used to evaluate the performance of 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. Computational experiments show that using aggregation with the heuristics not only finds more balanced words but also reduces computational effort for larger instances.