A New Local Search Algorithm for the Job Shop Scheduling Problem

A new local search algorithm with hybrid neighborhood for solving the minimum make span problem of job shop scheduling is presented. A new dispatching rule base d on the frontier-greed method is proposed to generate initial solution. A new c oncept of neighborhood structure involving the move of operations on the critica l path and the method of one-machine scheduling is proposed. The hybrid neighbor hood used is not only efficient in local search procedure, but also may help ove rcome entrapments effectively and carry the search to areas of the feasible set with better prospect. “Single machine scheduling” method and another stochasti c strategy used for jumping out of entrapments can help search find improved loc al optima. The proposed approach is tested on all the 10 jobs and 10 machines pr oblem instances available from the literature, including the notorious problem i nstance ft10, and some hard problem instances among those generated by Lawrence. The approach finds the optimum solutions of all these 10×10 problem instances except la 4 in a reasonable amount of computer time. Performance comparison show s that the proposed approach yields better results in several cases than the oth er approximation procedures discussed in the literature.