基于问题特征知识的迭代贪心算法求解多目标零等待流水车间调度问题  

Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem

作　　者：何轩 潘全科 高亮[3] HE Xuan;PAN Quanke;GAO Liang(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072;School of Logistics Engineering,Shanghai Maritime University,Shanghai 201306;State Key Lab of Intelligent Manufacturing Equipment&Technology in Huazhong University of Science&Technology,Wuhan 430074)

机构地区：[1]上海大学机电工程与自动化学院,上海200072 [2]上海海事大学物流工程学院,上海201306 [3]华中科技大学智能制造装备与技术全国重点实验室,武汉430074

出　　处：《机械工程学报》2025年第4期344-354,共11页Journal of Mechanical Engineering

基　　金：国家自然科学基金(61973203,61873328);国家重点研发计划(2020YFB1708200);国家杰出青年基金(51825502);上海市学术/技术计划(21XD1401000)资助项目。

摘　　要：零等待流水车间调度问题在现实生活中有广泛的应用,研究其求解方法是非常有必要的。现有文献大多仅考虑一个生产调度指标。然而,实际问题往往是多目标的。因此,以同时优化最大完工时间和总流经时间为目标,提出一种问题特征知识指导搜索的迭代贪心调度算法。首先,使用混合整数规划模型中目标转化为约束的方法验证两个目标的冲突性。然后,分析并提取问题特征知识,设计极值搜索过程估计参考点。针对最大完工时间目标,将其转化为非对称旅行商问题,使用动态规划局部优化调度序列。针对总流经时间指标,利用支配准则指导的局部搜索进行确定性的优化。最后,为有效执行具有问题特征指导的局部搜索,使用锥形标量加权方法将两个优化目标转化为一个优化目标。大量仿真试验表明了所提方法的有效性。The no-waiting flowshop scheduling problem(NWFSP)has a wide range of applications in the manufacturing industry.It is very necessary to develop efficient algorithms for solving NWFSP.Most of the existing literature only considers optimizing one production scheduling objective,but multiple objectives in actual production scenarios often need to be optimized simultaneously.Therefore,we focus on optimizing both the makespan and total flow time simultaneously,and propose an iterated greedy algorithm with problem-specific knowledge(KIG).First,the conflict relationship between the two objectives is verified by converting the total flow time objective in the mixed integer programming model into a constraint.Then,the problem-specific knowledge in each objective is analyzed and obtained.For the makepan objective,NWFSP is transformed into an asymmetric traveling salesman problem,and a dynamic programming algorithm is used to locally optimize the search solution.For the total flow time objective,a dominance criterion guided local search is used to deterministically optimize the partial sequence of the search solution.Finally,the conical scalar weighting method transforms the two optimization objectives into one optimization objective to perform local search efficiently.Extensive experimental results demonstrate the effectiveness of the KIG.

关 键 词：零等待流水车间调度 多目标优化 动态规划 支配准则 迭代贪心 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]