【摘要】 利用了混合邻域结构进行搜索来求解JobShop调度问题.算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域.算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值.采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较.实算结果验证了算法的寻优性能.更多还原

【Abstract】 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 based on the frontier-greed method is proposed to generate initial solution. A new concept of neighborhood structure involving the move of operations on the critical path and the method of one-machine scheduling is proposed. The hybrid neighborhood used is not only efficient in local search procedure, but also may help overcome entrapments effectively and carry the search to areas of the feasible set with better prospect. "Single machine scheduling" method and another stochastic strategy used for jumping out of entrapments can help search find improved local optima. The proposed approach is tested on all the 10 jobs and 10 machines problem instances available from the literature, including the notorious problem instance 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 shows that the proposed approach yields better results in several cases than the other approximation procedures discussed in the literature.更多还原