An improved shifting bottleneck procedure for the job shop scheduling problem

In this paper, the job shop scheduling problem with the objective to minimize the makespan is discussed. A theorem on the shifting bottleneck procedure (SB) for solving this problem is proven, which guarantees an application of the procedure slightly modified from SB to obtain feasible solution of the problem. Based on this theorem, an improved shifting bottleneck procedure (ISB) for the job shop scheduling problem has been proposed. Besides ISB is implemented straightly, a refined version that combines ISB with the strategy of back tracking is presented. These two procedures have been tested on many benchmarks with various sizes and hardness levels. The computational experiment shows that ISB is more efficient and effective than SB. Also, some encouraging results about the refined version are obtained.