A tabu search procedure for periodic job shop scheduling

We consider job shops where an identical mixture of items is repetitively produced. We discuss the sequencing problem that finds the processing order at each machine that maximizes the throughput rate of the mixtures or equivalently minimizes the cycle time. We present an effective tabu search procedure for the problem. To do this, we characterize the neighborhood structure that generates feasible solutions by reversing the order of two operations on a critical circuit in the associated graph. We develop an efficient method of approximately evaluating the cycle times of neighborhood solutions. Computational results are reported.