基于禁忌搜索算法求解流水作业最小误工调度问题

Tabu Search Algorithm to Solve the Problem of Minimal Delay Scheduling in a Flowshop System

针对流水作业环境最小化误工损失调度问题,提出一个禁忌搜索算法对其进行求解。利用多个启发式规则生成可行调度,从中选出最好解作为算法的初始解;同时,基于随机交换策略,权衡求解质量与运行时间之间的关系定义邻域搜索机制;采用双禁忌表结构防止算法陷于局部最优;最后,定义算法停止规则。数值实验表明,与传统禁忌搜索算法相比,新算法在求解质量和处理速度上进一步优化,且该优势随着问题规模的增大而更加明显。

In this paper,we propose a tabu search algorithm to solve the problem of minimal delay scheduling in a flowshop system.Several heuristic rules are considered to generate feasible schedules,and the best one among them is chosen to be the initial solution to tabu search.The neighborhood searching mechanism is designed based on the random exchanging approach,and two kinds of tabu lists are used to prevent local optimum.Moreover,several termination rules are defined to stop the iterations and output the best-found solution.Computational experiments show that the proposed algorithm beats the classical one,both from the viewpoints of solution quality and running time,and the advantage becomes more obvious as the problems increase.