求解带组换装时间单机调度问题的禁忌搜索算法

Tabu Search Algorithm for the Single Machine Scheduling Problem with Family Setup Times

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.

To solve the real-life scheduling problem in a steel wire factory in Baotou, China, the single machine scheduling problem with family setup times is studied. As the NP-hardness of the problem, a kind of tabu search algorithms are proposed to solve the problem： To improve the optimization performance and reduce the running time, problem properties are introduced into the proposed tabu search algorithms. The proposed algorithms were tested both on the randomly generated problems and on the real-life problems. Computational results show that the proposed algorithms can get near optimal solutions for the real-life problems within 10 seconds.