摘要
针对多目标流水车间调度问题,提出了一种邻域搜索(NS)算法,旨在以加工时间和总延迟时间为优化目标构建调度模型.该方法通过交换调度序列中的工件顺序生成新的解,从而在解空间中高效探索.算法从种群中的初始解开始,不断通过工作顺序的交换产生候选解,并利用适应值对这些解的优劣进行评估.随着迭代优化的进行,算法逐渐逼近全局最优解.此外,基于占优关系函数的方法用于评估解的相对优势,通过参考点计算解在不同目标维度上的距离,并以此衡量解的质量.为了实现解空间的系统性探索,本文采用基于汉明距离的解生成策略.该方法通过构建解之间的最短汉明路径,在保留解的优良特征的同时,有效地探索未知解空间,提升算法寻找全局最优解的能力.通过20个不同规模算例的实验,将NS算法与传统遗传算法(GA)及非支配排序遗传算法(NSGA-II)进行比较,结果显示该方法在多目标优化上表现出色,验证了其有效性和优势.
A neighborhood search(NS)algorithm is proposed for the multi-objective flow shop scheduling problem,aiming to construct a scheduling model that optimizes processing time and total tardiness.This method efficiently explores the solution space by generating new solutions through the swapping of job sequences.Starting from an initial solution in the population,candidate solutions are iteratively generated by altering job sequences and are evaluated using fitness values.As the optimization proceeds,the algorithm gradually converges toward the global optimum.A dominance relationship function is employed to assess the relative superiority of solutions by calculating their distances to reference points across multiple objective dimensions,thus enabling effective quality evaluation.To ensure systematic exploration of the solution space,this study employs a solution generation strategy based on Hamming distance.By constructing the shortest Hamming paths between solutions,this approach preserves desirable characteristics.It also effectively probes unexplored regions of the solution space,thus enhancing the algorithm’s capability to locate the global optimum.Experimental results from 20 test cases of varying scales show that the proposed NS algorithm outperforms the traditional genetic algorithm(GA)and the non-dominated sorting genetic algorithm(NSGA-II)in multi-objective optimization,demonstrating its effectiveness and advantages.
作者
杨兴坤
杨昊
文武
徐虹
YANG Xing-Kun;YANG Hao;WEN Wu;XU Hong(School of Computer Science,Chengdu University of Information Technology,Chengdu 610225,China)
出处
《计算机系统应用》
2025年第7期244-252,共9页
Computer Systems & Applications
基金
四川省科技计划(2023JDZH0034)
四川省科技成果转移转化示范项目(2024ZHCG0026)。
关键词
多目标
邻域搜索
车间调度
汉明距离
multi-object
neighborhood search(NS)
flow shop scheduling
Hamming distance
