Tabu search algorithms for cyclic machine scheduling problems

Tabu search algorithms are developed for solving a large class of cyclic machine scheduling problems with the objective to minimize the cycle time. Neighborhoods are derived which generalize the block-approach based neighborhoods which have been successfully applied to noncyclic job-shop problems. For a variant of this neighborhood opt-connectivity is proved. The tabu-search procedure is applied to cyclic job-shop scheduling problems. Computational results are presented.