一种改进的作业车间调度转换瓶颈算法

In this paper, the job shop scheduling problem with the objective to minimize the makespan is discussed. The theorem, which guarantees the shifting bottleneck procedure (SB) with Schrage one-machine sequencing algorithm always obtains the feasible solution for any instance, is concisely proven. A counterexample is given to show that SB with Carlier’s one-machine sequencing algorithm could get the infeasible solution. By the way, we also point out a mistake made in the Carlier’s theorem which Carlier’s algorithm is based on, and complete it by some modifications. In order to overcome the infeasibility weakness of SB and expect better performance, a modified shifting bottleneck procedure (MSB) for job shop scheduling is proposed. The theorem, which ensures MSB get the feasible solution for any instance of the problem, is testified. MSB is tested on a group of benchmark instances. The computational experiment shows that MSB get better solutions than SB.