A Local Search Method with Hybrid Neighborhood for the Job Shop Scheduling Problem
一种求解车间作业调度问题的混合邻域结构搜索算法

Job shop scheduling problem is well known to be a difficult, strongly NP-complete problem, the objective of this is minimizing the completion time of all the jobs, called the make span, subject to the constraints of this kind of problem. A local search method with hybrid neighborhood is presented for job shop scheduling problem. The key problems for local search method, such as neighborhood structure and off-trap strategy, the solutions are made to de- crease the makespan of the schedule. Our approach is tested on a total of 43 standard problem instances, 39 instances are found optimal solutions, including the notorious instances FT10. Our approach yields better solutions than a par- ticularly efficient algorithms discussed in the literature.