An improved shifting bottleneck algorithm for job shop scheduling problem

The shifting bottleneck procedures are mainly based on one-machine scheduling algorithm, so the results of one-machine scheduling algorithm significantly affect the performance of the shifting bottleneck procedures. In this paper, inspired by two facts that the function of the release time and the delivery time of each job is uniform, an efficient algorithm for one-machine scheduling problem is presented. Based on this algorithm, an improved shifting bottleneck procedure is developed. The simulation results to the well-known benchmark problems show that the performance of the improved procedure can compete with that of the shifting bottleneck procedure and the modified ones.