一种求解车间作业调度问题的混合邻域结构搜索算法

车间作业调度问题是优化组合中一个著名的难题，问题的目标是在满足约束条件的前提下，使调度的加工周期尽可能小。文章中提出了利用新的混合邻域结构进行搜索来求解车间作业调度问题。对于算法关键的邻域构造问题以及跳坑策略给出了提高算法优度的解决方案。采用43个不同规模和难度的国际标准算例做为本算法的测试实验集，39个算例找到了最优解，其中包括著名的难例FT10。与当前国外学者提出的一种先进算法进行了比较，算法的优度高于被比较的先进算法。

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.