ScienceandTechnology&Innovation┃科技与创新2023年第04期·13·文章编号：2095-6835（2023）04-0013-03零空闲流水车间问题中启发式规则的研究与改进＊李杰，李艳武（重庆三峡学院电子与信息工程学院，重庆404100）摘要：在流水车间问题中，通过启发式规则获得初始解的优劣是影响整体算法性能的重要因素。但目前被广泛使用的有效启发式规则（如NEH、FRB5等）都不能在获得初始解的质量和消耗CPU时间上取得平衡，在对这2种启发式规则研究后，改进了获得初始解时的邻域搜索，使改进的启发式规则在获得较好初始解的同时减少了CPU消耗时间，嵌入到迭代贪婪算法后提升了整体算法的性能。关键词：零空闲流水车间；启发式规则；邻域搜索；迭代贪婪算法中图分类号：TP297文献标志码：ADOI：10.15913/j.cnki.kjycx.2023.04.004流水车间排列问题（PermutationFlowshopSchedulingProblem，PFSP）是一个著名的排列优化问题，已经被证明是一个NP难[1]（非确定性多项式）问题。在PFSP问题中，n个工件需要依次在固定顺序的m个机器上加工，n个工件加工顺序一旦确定，所有的机器必须按照相同的工件排列顺序加工，因此，其目的是根据给定的优化准则找到作业的最优排列。当给定约束条件，要求在每台机器上工件处理之间没有空闲时间，机器一旦开启，就要连续加工工件，则PFSP问题就进一步扩展为零空闲流水车间问题（No-idlePermutationFlowshopSchedulingProblem，NIFSP）。在NIFSP问题中，以最小化最大完工时间为目标的排列寻优又被表示为Fm/prmu，no-idle/Cmax。在实际应用中，NIFSP问题在一些使用昂贵生产机器的产业链中更为常见，机器一旦开启便需要持续工作，直到完成所有工件。一些产业的产品特性也需要在加工工件过程中不能中断机器，例如传统行业中的陶瓷熔块生产、玻璃纤维加工等。而在技术不断发展的今天，机器承担了越来越多不同的加工作业，NIFSP问题不得不成为一个机器在生产过程中需要考虑到的重要约束条件。1982年，ADIRI和POHORYLES首次考虑了最小化总完工时间的零空闲流水车间调度问题。同年，VACHAJITPAN首次考虑了以makespan为目标的NIFSP问题，采用混合整数规划（MixedIntegerProgramming，MIP）进行建模，但只能求解较小规模的算例。WOOLLAM首次采用几种启发式规则来求解NIFSP问题。直到2007年，RUBÉN[2]提出的迭代贪婪算法（IterativeGreedy，IG）被认为是解决流水车间问题的有效算法，其中使用的启发式规则就是NEH[3]，2019年SHEN[4]等提出了一...
