作业车间调度问题的双向耦合调度解码方法及混合算法

摘要

针对作业车间调度问题(job shop scheduling problem,JSP)，以最小化最大完工时间为目标，提出一种双向耦合调度解码方法，以及多维度强化搜索的遗传禁忌混合算法。针对同一编码个体，分别进行正向主动调度解码和反向主动调度解码；然后结合机器与工件头尾长度进行双向耦合。双向耦合调度解码方法能够综合工序左移与右移的优势，更好地利用机器上的空闲时间，提高了解码的质量。将该解码方法融入遗传算法与禁忌搜索算法的混合算法进行JSP问题求解，在局部搜索过程中运用多种解码方法对单一个体进行解码；进而得到多个可能具有更优最大完工时间的个体，然后对这些个体进行禁忌搜索，实现了单一个体多维度强化搜索。通过测试JSP问题基准算例，验证了算法有效性。

关键词

作业车间调度问题 / 解码方法 / 遗传算法 / 禁忌搜索