摘要
针对作业车间调度问题(job shop scheduling problem,JSP),以最小化最大完工时间为目标,提出一种双向耦合调度解码方法,以及多维度强化搜索的遗传禁忌混合算法。针对同一编码个体,分别进行正向主动调度解码和反向主动调度解码;然后结合机器与工件头尾长度进行双向耦合。双向耦合调度解码方法能够综合工序左移与右移的优势,更好地利用机器上的空闲时间,提高了解码的质量。将该解码方法融入遗传算法与禁忌搜索算法的混合算法进行JSP问题求解,在局部搜索过程中运用多种解码方法对单一个体进行解码;进而得到多个可能具有更优最大完工时间的个体,然后对这些个体进行禁忌搜索,实现了单一个体多维度强化搜索。通过测试JSP问题基准算例,验证了算法有效性。
For the job shop scheduling problem(JSP),a bidirectional coupling scheduling decoding method and a hybrid genetic-tabu algorithm with multi-dimensional enhanced search are proposed with the objective of minimizing the makspan.For the same coded individual,forward and backward active scheduling decoding are performed respectively,and then bidirectional coupling is carried out combining the head-tail lengths of machines and jobs.The proposed method integrate the advantages of left-shift and right-shift operations,enabling more effective utilization of machine idle time and improving decoding quality.This decoding method is integrated into the hybrid algorithm of genetic and tabu search algorithms to solve the JSP.In the process of local search,multiple decoding methods are used to decode a single individual to generate multiple individuals with potentially improved makespan.These individuals are then further optimized through tabu search,achieving multidimensional enhanced search for single individuals.The effectiveness of the algorithm is verified by testing benchmark examples of JSP.
作者
刘子辉
赵诗奎
Liu Zihui;Zhao Shikui(School of Mechanical Engineering,University of Jinan,Jinan 250022,China)
出处
《工业工程》
2026年第1期164-177,共14页
Industrial Engineering Journal
基金
国家自然科学基金资助项目(52275490)
山东省自然科学基金资助项目(ZR2025MS766)。
关键词
作业车间调度问题
解码方法
遗传算法
禁忌搜索
job shop scheduling problem
decoding method
genetic algorithm
Tabu search
