基于改进禁忌搜索算法的单机成组作业调度

The Single Machine Scheduling with Job Class Setups Based on an Improved Tabu Algorithm

提出了单机成组作业调度的改进禁忌搜索算法。以总流程时间最短为优化目标的具有作业分类与机器设置时间的单机成组作业调度问题是NP难问题,此问题的多项式求解方法不能保证求取最优解。基于改进禁忌搜索算法,建立了具有提交时间与分类设置时间的单机成组作业调度模型,可搜索到该问题的最优解。仿真实验表明,改进禁忌搜索算法能够搜索到最优解,其性能优于WSPT启发式算法,并且运行时间短,可应用于大规模调度问题。

The improved tabu algorithm of single machine scheduling with job class setups is proposed.The single machine with job class and machine setup-time scheduling problem of minimizing total flow-time is obviously NP-hard problem.Some other problems well-known polynomially solution approaches don't guarantee optimality any longer.The model of single machine scheduling with job class setups and release time is constructed based on an improved tabu algorithm.We find the best solution of this problem.The simulation experiments show that the improved tabu algorithm not only can obtain the best optimal solution but also is better than WSPT heuristic algorithm.Its running time is short,and it can solve the large-scale scheduling problem.