设备故障下的零空闲多设备工作中心调度

设备故障是车间调度中最为常见的动态事件,易对原生产调度计划造成影响。为保证加工生产在遇到设备故障后能够快速地对原调度方案做出调整,降低设备故障所带来的负面影响,对设备故障下的零空闲多设备工作中心调度问题进行研究。建立了设备故障下考虑调整时间和搬运时间的零空闲多设备工作中心调度模型,优化目标为最小化最大完工时间、搬运次数和系统稳定性;设计NSGA-Ⅱ-V算法用于原调度和重调度的求解;基于NSGA-Ⅱ-V获得的静态调度结果与部分重调度策略的思想,进行设备故障算例测试。测试结果表明,所提模型和算法可较好地处理动态事件为设备故障的零空闲多设备工作中心调度问题。

零空闲置换流水车间总延误最小迭代贪婪算法

研究以总延误时间为目标且具有释放时间约束的零空闲置换流水车间调度问题。基于贪婪选择和作业对交换,设计基本迭代贪婪算法IGA;结合先到先服务FCFS排产规则对初始解的构建进行改进,并提出作业对多次循环交换对邻域搜索进行优化,递进设计了3种迭代贪婪算法FIGA、MIGA、FMIGA。通过不同规模的数据实验和与对比算法的比较分析,验证了FMIGA算法的有效性。结果显示该算法不仅能提高解的质量,而且具有良好的稳定性,为求解具有释放时间的零空闲置换流水车间总延误问题提出了一种新方法。

零空闲流水车间问题中启发式规则的研究与改进

在流水车间问题中,通过启发式规则获得初始解的优劣是影响整体算法性能的重要因素。但目前被广泛使用的有效启发式规则(如NEH、FRB5等)都不能在获得初始解的质量和消耗CPU时间上取得平衡,在对这2种启发式规则研究后,改进了获得初始解时的邻域搜索,使改进的启发式规则在获得较好初始解的同时减少了CPU消耗时间,嵌入到迭代贪婪算法后提升了整体算法的性能。

求解零空闲流水线调度问题的和声搜索算法

针对以总流经时间和最大完工时间为目标的零空闲流水线调度问题,提出了和声搜索调度算法。该算法利用和声搜索算法的优化机理,采用基于浮点数的编码方式和新设计的和声产生方法,扩展了传统和声搜索算法的求解模型,并结合快速插入邻域局部搜索算法,给出了三种混合求解策略。仿真试验表明,该算法具有高效性和优越性。

解决零空闲流水线调度问题的离散粒子群算法

研究了以最大完工时间为目标的零空闲流水线调度问题.提出一种复杂度为O(nm)的最大完工时间算法和一种快速插入邻域搜索算法;提出了解决该问题的离散粒子群调度算法,并结合简化邻域搜索算法给出了提高调度算法性能的措施.仿真实验表明了所得算法的有效性.

基于蛙跳算法的零空闲流水线调度问题优化

针对零空闲流水线调度问题,以E/T指标最优为优化测度,提出了一种蛙跳求解算法。首先,该算法采用新的个体产生方法,扩展传统蛙跳算法的求解模型。其次,使用带有启发式策略的种群初始化方法优化初始解性能。再次,借助基于种群多样性的方法进行排序和分组,并通过部分随机初始化策略保持种群多样性。最后,结合一种简单而有效的邻域搜索算法,达到局部探索和全局搜索之间的平衡,进而提高收敛速度。在若干benchmark问题上的仿真实验表明了所提算法的有效性。

基于离散蛙跳算法的零空闲流水线调度问题求解

针对零空闲流水线调度问题,提出了一种新的离散化蛙跳求解算法.该算法借助蛙跳算法优化机理,采用基于工件序列的编码方式和新的个体产生方法扩展了传统蛙跳算法的求解模型,并结合简化邻域搜索算法给出了3种改进策略.仿真实验表明了所提算法及策略的有效性.

求解零空闲流水线调度问题的和声退火算法

针对以最大完工时间为目标的零空闲流水线调度问题提出了和声退火算法。首先引入了基于ROV规则的编码方式,使和声搜索应用于离散问题,从初始化方法、参数调整、候选解的产生、和声记忆库的更新方法等四个方面对基本和声搜索算法进行了改进,基于此提出了改进的和声搜索算法;其次,结合和声搜索和模拟退火算法的优点,分别对和声搜索过程中的最优解、和声记忆库中的随机选中的解及一个新解分别进行模拟退火,提出了三种不同的和声退火算法。仿真实验表明所提算法的有效性和优越性。

求解零空闲置换流水车间调度问题的离散萤火虫算法

针对最小化最大完工时间的零空闲置换流水车间调度问题,提出了一种离散型萤火虫优化算法。基于萤火虫算法优化机理,采用基于工件序列的个体编码方式,重新定义了个体间距离的概念和位置更新公式,并结合交换、插入和逆序操作的局部搜索策略来提高算法性能。通过典型算例对算法进行了仿真测试和对比,结果表明了所提算法的可行性和有效性,扩展了传统萤火虫算法的求解范围,是解决流水线生产调度问题的一种有效方法。

禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型。新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能。利用动态方式更新禁忌表长,提高了新算法的鲁棒性。为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法。仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值。

求解零空闲流水线调度问题的改进蚁群算法

针对零空闲流水线调度问题的最大完工时间,提出一种改进蚁群算法。该算法改进了信息素密度的初始化方法和更新规则,采用新的状态转移策略构建新解,结合快速插入邻域局部搜索算法,解决蚁群算法易陷入局部收敛的缺点,从而提高算法的搜索效率。基于典型算例的仿真实验,表明了改进算法具有高效性和优越性。

新混合鸟群算法求解零空闲流水车间调度问题

针对零空闲流水车间调度问题(NFSP),提出了一种新混合鸟群算法(NHBSA)以最小化最大完工时间.首先,对一种FRB(Farahmand-Ruiz-Boroojerdian)启发式算法进行了改进,在初始化阶段结合改进的FRB算法和混沌映射来改善种群的质量和多样性.其次,采用SPV(Smallest-Position-Value)规则在连续的位置和离散的工件排序之间进行转换,使算法适用于求解离散的调度问题.最后,借鉴变邻域搜索和迭代贪婪算法的思想针对种群最佳工件排序提出了一种局部搜索方法,以提升算法收敛的精度和跳出局部最优的能力.基于广泛使用的Taillard标准测试集进行了仿真测试,并与多种针对NFSP的元启发式算法相比较,结果显示,所提出的算法在保证良好稳定性的前提下,得到的平均百分比相对偏差(APRD)和性能提升百分比(PIP)较对比算法分别改善了71.017%和4.653%.

一种求解混合零空闲置换流水车间调度禁忌分布估计算法

结合混合零空闲置换流水车间调度问题MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性,运用基于概率模型的分布估计算法解决该问题。算法将启发式算法融入分布估计算法中提高了初始解的质量。为了避免算法陷入局部最优,将禁忌算法融入分布估计算法中,提出一种禁忌分布估计算法求解混合零空闲置换流水车间问题。为了提高种群的多样性,加入了三种邻域搜索。实例测试结果显示,该算法求解混合零空闲置换流水车间问题具有很好的优势。

改进果蝇算法求解零空闲流水车间调度问题

针对传统果蝇算法在求解零空闲流水车间调度问题时,存在精度及稳定性较差的问题,提出了一种改进果蝇优化算法用以求解该类问题。该方法以最大完工时间最小化为优化目标,在传统果蝇算法的基础上,建立了多种群中心搜索模式,改进嗅觉搜索方式,引入破坏重建、插入领域局部搜索;并将免疫算法激励度引入果蝇视觉觅食阶段;最后通过测试案例,验证了该改进算法的有效性。结果显示该算法不仅能有效提高全局寻优效果,而且具有较好的稳定性,为求解零空闲流水车间问题提出了一种新方法。

改进布谷鸟搜索算法求解零空闲流水线调度问题

本文针对零空闲流水线调度问题,提出了一种基于自适应步长和发现概率的改进布谷鸟搜索算法,建立了以工件的最大完工时间为目标的算法模型。最后在若干Taillard Benchmark问题上的仿真实验表明了改进布谷鸟搜索算法解决零空闲流水线调度问题的有效性。

改进细菌觅食算法解决零空闲流水线调度问题

针对零空闲流水线调度问题,建立以最大完成时间为目标的数学模型,并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上,引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率,以加速算法的收敛过程,并有效抑制精英个体的逃逸,防止解发生退化。采用路径编码方式,通过MATLAB算例试验,表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性;同时,运用两种方式产生初始解:随机方式和NEH方法,进一步验证算法的鲁棒性。

基于引力搜索算法的混合零空闲置换流水车间调度

针对以最小化总流水时间为目标的混合零空闲流水车间调度问题,提出一种有效的贪婪引力搜索算法(GGSA)进行求解。引入了基于升序排列(ROV)规则的编码方式,使引力搜索算法(GSA)能够应用于离散优化问题;其次,对GSA进行了改进:在初始化中加入NEH(Nawaz-Enscore-Ham)启发式规则构造高质量的初始解,以提高搜索效率;引入可变迭代贪婪(vIG)算法,利用其较强的局部开发能力,提高算法精度;同时,在vIG算法中加入参照插入方案(RIS)和模拟退火收敛判据,前者可以加强局部搜索能力、加快收敛速度,后者可以帮助算法在一定程度上跳出局部最优。最后,通过对典型测试算例进行仿真,验证了所提出算法的有效性。

求解零空闲流水车间调度问题的离散正弦优化算法

针对以最小化最大完工时间(makespan)为目标的零空闲流水车间调度问题(NIFSP),提出一种离散正弦优化算法(DSOA)进行求解.受正弦波形的启发,原始的正弦优化算法(SOA)是一种利用正弦函数对个体位置进行更新的全局优化算法.首先,重新定义了适应组合优化问题的位置更新策略,采用一种去除工件数大小可变的迭代贪婪算法来对个体位置进行更新,以提高算法的探索能力.其次,采用了交叉操作和保留精英解的选择策略,避免算法陷入局部最优.最后,为了提高局部搜索的开发能力和算法精度,引入了一种基于插入的局部搜索方法,以便于在当前最优解的周围寻找更好的解.此外,基于Taillard基准,给出了算法性能比较的仿真结果,实验结果验证了所提出的DSOA算法求解NIFSP的有效性.

基于多目标离散正弦优化算法的混合零空闲置换流水车间调度

针对以最小化最大完工时间(makespan)和最小化最大拖期(maximum tardiness)为目标的多目标混合零空闲置换流水车间调度问题(Mixed No-idle Permutation Flow Shop Scheduling Problem,MNPFSP),提出了一种多目标离散正弦优化算法(Multi-objective Discrete Sine Optimization Algorithm,MDSOA)。首先,建立外部档案集(AS)存储Pareto解,并在每次迭代后对AS进行更新;其次,在正弦优化算法(Sine Optimization Algorithm,SOA)的基础上,引入迭代贪婪(IG)算法的破坏重构机制,重新定义了一种适用于离散调度问题的位置更新策略;最后,引入快速非支配排序和拥挤距离对种群进行筛选,在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验,并将仿真结果与NSGA-Ⅱ和NSGA-Ⅲ算法进行比较,验证了MDSOA求解MNPFSP的有效性。

变量块内部迭代算法求解零空闲流水车间问题

零空闲流水车间问题(NIFSP)是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。