基于改进的禁忌搜索算法求解车间作业调度问题.docx

基于改进的禁忌搜索算法求解车间作业调度问题
随着制造业不断发展，车间作业调度问题在实际生产中变得越来越重要。现代制造业需要通过合理的作业调度，提高生产效率，降低成本，并最大限度地提高生产线资源利用率。因此，针对车间作业调度问题提出了多种求解方法，其中禁忌搜索算法因其在贪心变异操作中良好的性能和可扩展性而成为一种非常受欢迎的方法。本文将介绍一个基于改进的禁忌搜索算法的求解车间作业调度问题的方法。
一、问题描述
车间作业调度问题（JobShopSchedulingProblem,JSSP）是一个古老但也常见的离散制造问题，是NP完全问题的一个经典例子。该问题发生在多个机器和多个作业之间，每个作业可能需要在多个机器上以不同顺序执行。该问题的主要目标是使得每个作业的预期处理时间最小化，并确保所有作业都在截止时间之前完成。
建议使用流水线工厂来对该问题进行模拟。假设有n个工件和m个机器，每个工件都需要在这些机器上进行一定的工艺才能完成。每个工件具有一个加工序列，一次只能在一个机器上进行加工，每个机器在同一时间最多只能加工一个工件，每个工件的加工序列不一定相同。每个加工序列都包含m个操作，其中每个操作对应于工件在某个机器上的加工。每个工序都具有一个特定的时间。
二、禁忌搜索算法
禁忌搜索算法（TabuSearchAlgorithm）是一种基于贪心算法的局部搜索算法。在禁忌搜索算法中，对于一个给定的优化问题，数据结构表示搜索空间的集合，然后搜索过程通过迭代调整当前解决方案，以寻找最优的解。与基于贪心算法的其他搜索算法一样，禁忌搜索算法的核心是扰动技术，通过扰动当前解来寻找更优的解。然而，禁忌搜索算法通过添加一个记忆性机制，以禁止搜索过程中经常访问的可能死路或不太优秀的解。
禁忌列表（TabuList）是指一个保留禁止回退的记录，以防止掉入局部最优解并死循环在该解中。如果某个解被添加到禁忌列表中，则该解将被禁止在接下来的查找过程中被评估，直到其销毁时间到达或可在该时间到达之前销毁。
三、基于改进的禁忌搜索算法
针对JSSP问题，采用基于改进的禁忌搜索算法求解。基于贪心的改进算法的目标是降低因贪心算法过度优化而导致的局部最优。这种算法在贪心算法中添加随机性，以便在保持当前解的方向上进行跳跃，并查找新解。与标准禁忌搜索算法相比，改进的禁忌搜索算法最大的不同之处在于路径扰动和禁忌搜索过程。
该算法可以归纳如下：
1.随机产生初始解或使用手动（或其他启发式）制定解。并设置最佳解为当前解。
2.根据贪心策略生成一个新解，并将该解与禁忌列表进行比较。如果新解更优，将它设置为当前解。如果新解与其它提前被禁止的解重复，将其存入禁忌列表，并重复步骤2。
3.选择当前解的一部分来进行扰动，然后确定新解并检查禁忌列表中是否存在该解。如果新解没有在禁忌列表中出现，则将其设置为当前解。否则，回到该步骤并进行新的扰动。
4.通过检查最优解和停止准则来确定是否继续搜索。
该算法实现包括改进路径扰动和禁忌列表策略的扰动技术。基于路径的扰动是一种常见的局部搜索技术，它通过更改搜索路径来寻找新的解决方案。在应用该算法时，会对当前解进行扰动，并将其转化为新解。该算法通过定义b位二元数组来执行扰动，并且每次进行扰动时不会重复元素。
禁忌列表策略也是该算法的核心部分，在搜索过程中，禁忌列表至关重要，它在搜索过程中禁止访问并处理未能获得最佳效果的可能死路或不太优秀的解。该算法会使用循环队列来保存禁忌列表，以避免浪费空间。
四、结论
基于改进的禁忌搜索算法是求解JSSP问题的一种较为有效的方法。该算法引入了贪心策略、扰动技术和禁忌列表策略等，可以通过添加随机性和禁忌列表来确保算法可以跳出局部最优解，并在保持当前解方向上进行跳跃，从而大大降低了运行时间。在实际应用中，该算法可以通过修改参数，例如贪心策略、扰动系数等，来进一步提高搜索质量。