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

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