A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

详细信息    查看全文

• 作者：ChaoYong Zhang ; PeiGen Li ; ZaiLin Guan ; YunQing Rao
• 关键词：Job shop scheduling problem ; Makespan ; Heuristic ; Tabu search
• 刊名：Computers and Operations Research
• 出版年：2007
• 出版时间：November 2007
• 年：2007
• 卷：34
• 期：11
• 页码：3229-3242
• 全文大小：222 K

文摘

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.