A simulation-based approach to job shop scheduling with bottlenecks

A bottleneck machine identification algorithm is proposed for the job shop scheduling problem in which either the makespan or the total tardiness should be minimized. The scheduling policies on 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, a statistics-based algorithm to compute the bottleneck characteristic values is devised. The algorithm first constructs a simulation data set which consists of a number of different solutions in the form of scheduling rules, and then statistically analyzes the correlation between various scheduling policies on each machine and the overall scheduling objective value. Two genetic algorithms based on different encoding schemes are designed 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.