求解车间调度问题的双禁忌表禁忌搜索算法
|
摘要
针对车间调度问题的特点,为解决传统禁忌搜索算法容易陷入局部最优解的问题,提出一种求解车间调度问题改进的禁忌搜索算法—双禁忌表禁忌搜索算法,该算法通过建立双禁忌表避免在搜索最优解时出现循环的现象.通过该算法与TSAB算法进行比较可知,该算法具有较强的寻优能力.
According to the characteristics of the job scheduling problem,in order to solve the problem that the traditional tabu search algorithm is easy to fall into local optimal solution,we have proposed an improved tabu search algorithm for solving job shop scheduling problems—a tabu search algorithm based on double tabu list algorithm.This algorithm avoids the phenomenon of the cycle by establishing the double tabu list when searching the optimal solution.By comparing the algorithm with TSAB algorithm,the algorithm has a strong ability of searching for the best solution.
According to the characteristics of the job scheduling problem,in order to solve the problem that the traditional tabu search algorithm is easy to fall into local optimal solution,we have proposed an improved tabu search algorithm for solving job shop scheduling problems—a tabu search algorithm based on double tabu list algorithm.This algorithm avoids the phenomenon of the cycle by establishing the double tabu list when searching the optimal solution.By comparing the algorithm with TSAB algorithm,the algorithm has a strong ability of searching for the best solution.
引文
[1]GAREY M R,JOHNSON D S.Computer and Intract Ability:a Guide to theory of NP-completeness[M].San Francisco:Freeman,1979.
[2]张淑丽,刘胜辉.相关工件车间调度问题的拓扑算法[J].计算机工程与应用,2013,3(49):251-254.
[3]MEERAN S,MORSHEDMS.Ahybrid Genetic Tabu Search Algorithm for Solving Job Shop Scheduling Problems:a Case Study[J].International Journal of Advanced Manufacturing Technology,2012,23(4):1063-1078.
[4]黄志,黄文奇.一种基于禁忌搜索技术的作业车间调度算法[J].小型微型计算机系统,2005,26(2):223-225.
[5]李海宁,孙树栋,杨宏安.TS/MP混合算法求解作业车间JIT调度问题[J].计算机集成制造系统,2012,18(6):1177
[6]PEZZELLA F.,MERELLI E..A Tabu Search Method Guided by Shifting Bottle Neck for the Job Shop Scheduling Problem[J].European Journal of Operational Research,2000,120(2):297-310.
[7]NOWICKI E,SMUTNICKI C.A Fast Taboo Search Algorithm for the Job Shop Problem[J].Management Science,1996,42(6):797-813.
[8]GLOVER F,Mc Milan C,Novick B.Tabu serch part 1[J].ORSA J.Computing,1989,1(3):190-206.
[9]刘刚,王瑛.基于关键路径求解作业车间调度问题的收敛性分析[J].计算机集成制造系统,2014,20(5):1079-1086.
[10]WANG L,WANG S Y,XU Y,et al.A Bi-population Based Estimation of Distribution Algorithm for the Flexible Job-shop Scheduling Problem[J].Computers&Industrial Engineering,2012,62(4):917-926.
[11]LI J Q,PAN Q K,SUGANTHAN P N,et al.A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2011,52(5-8):683-697.
[12]HMIDA A B,HAOUARI M,HUGUET M,et al.Discrepancy Search for the Flexible Job Shop Scheduling Problem[J].Computers&Operations Research,2010,37(12):2192-2201.
[13]赵诗奎,方水良,顾新建.基于极限调度完工时间最小化的机器选择及FJSP求解[J].计算机集成制造系统,2014,20(4):854-865.
[14]王凌.车间调度及其遗传算法[M].北京清华大学出版社,2003.
[15]王永明,尹红丽,秦开大.作业车间调度理论及其优化方法研究[M].科学出版社,2013.
[2]张淑丽,刘胜辉.相关工件车间调度问题的拓扑算法[J].计算机工程与应用,2013,3(49):251-254.
[3]MEERAN S,MORSHEDMS.Ahybrid Genetic Tabu Search Algorithm for Solving Job Shop Scheduling Problems:a Case Study[J].International Journal of Advanced Manufacturing Technology,2012,23(4):1063-1078.
[4]黄志,黄文奇.一种基于禁忌搜索技术的作业车间调度算法[J].小型微型计算机系统,2005,26(2):223-225.
[5]李海宁,孙树栋,杨宏安.TS/MP混合算法求解作业车间JIT调度问题[J].计算机集成制造系统,2012,18(6):1177
[6]PEZZELLA F.,MERELLI E..A Tabu Search Method Guided by Shifting Bottle Neck for the Job Shop Scheduling Problem[J].European Journal of Operational Research,2000,120(2):297-310.
[7]NOWICKI E,SMUTNICKI C.A Fast Taboo Search Algorithm for the Job Shop Problem[J].Management Science,1996,42(6):797-813.
[8]GLOVER F,Mc Milan C,Novick B.Tabu serch part 1[J].ORSA J.Computing,1989,1(3):190-206.
[9]刘刚,王瑛.基于关键路径求解作业车间调度问题的收敛性分析[J].计算机集成制造系统,2014,20(5):1079-1086.
[10]WANG L,WANG S Y,XU Y,et al.A Bi-population Based Estimation of Distribution Algorithm for the Flexible Job-shop Scheduling Problem[J].Computers&Industrial Engineering,2012,62(4):917-926.
[11]LI J Q,PAN Q K,SUGANTHAN P N,et al.A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2011,52(5-8):683-697.
[12]HMIDA A B,HAOUARI M,HUGUET M,et al.Discrepancy Search for the Flexible Job Shop Scheduling Problem[J].Computers&Operations Research,2010,37(12):2192-2201.
[13]赵诗奎,方水良,顾新建.基于极限调度完工时间最小化的机器选择及FJSP求解[J].计算机集成制造系统,2014,20(4):854-865.
[14]王凌.车间调度及其遗传算法[M].北京清华大学出版社,2003.
[15]王永明,尹红丽,秦开大.作业车间调度理论及其优化方法研究[M].科学出版社,2013.