Bottleneck Machine Identification for Shop Scheduling Problems

A bottleneck machine identification algorithm is proposed for the job shop scheduling problem to minimize total tardiness. The scheduling policies for bottleneck machines can have significant impact on the final scheduling performance and therefore need to be optimized with more computational effort. In order to describe the characteristic information concerning bottleneck machines, we devise an optimization-based procedure which reasonably alters the scheduling constraints and use it to compute the bottleneck characteristic values. Finally, a genetic algorithm based on hybrid encoding schemes is used to verify the effectiveness of the proposed method, and it is proved that intensifying the local search operations for bottleneck machines will generally result in higher solution quality for the job shop scheduling problem.