摘要
禁忌搜索算法(Tabu Search Algorithm,TSA)是解决车间调度问题的一种比较有效的算法,高效率搜索邻域解是TSA的关键步骤。在分析关键路径块结构的基础之上,给出了适用于求解最小化最大完成时间车间调度问题的6种块邻域结构方法,并应用于禁忌搜索算法。仿真实验结果表明,块结构邻域TSA算法可以有效提高搜索邻域解的效率,降低算法运行时间,增强算法的鲁棒性。
The tabu search algorithm is one of the most popular methods for job shop scheduling problems. How to find the most suitable solution from a huge number of neighbors is the key step of the TSA. Through analysis of the block structure on the critical path, six methods based on the block structure were presented to solve the job shop scheduling problems with maximum completion time criterion. Computational simulations and comparisons demonstrate that the proposed algorithm can increase the computation efficiency, decrease the computation time and make the computation process more robust.
出处
《机床与液压》
北大核心
2009年第12期173-175,188,共4页
Machine Tool & Hydraulics
基金
国家自然科学基金项目(60874075
70871065)
山东省教育厅科研发展计划(J08LJ20
J09LG29
J08LJ59)
关键词
作业车间调度问题
禁忌搜索
块结构
邻域解
Job shop scheduling problem
Tabu search algorithm
Block structure
Neighboring solution
