A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine

The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.

结合遗传算子的并行萤火虫算法及在车间调度中的应用

论文提出了一种结合遗传算子的并行萤火虫算法,该算法借鉴了萤火虫闪烁移动的思想,对两个种群进行同步并行迭代求解,以提升算法的求解速度和质量;在其中一个种群中引入多尺度协同变异算子,利用不同大小方差的自适应高斯变异机制使整个种群以尽量分散的变异尺度来对解空间进行更详尽的探索,从而使整个种群进行有效变异。函数优化结果表明了该算法的有效性,该算法用于求解以最小化最大完工时间为优化目标的流水车间调度问题,实验结果表明,较传统的单一算法而言,结合遗传算子的并行萤火虫算法在求解车间调度问题方面具有更好的性能。

考虑运输时间的混合流水车间绿色生产调度

针对运输时间对混合流水车间绿色生产调度的影响这一问题,以最大完工时间、生产能耗及生产成本为优化目标,提出一种改进的多目标麻雀搜索算法(Improved Multi-Objective Sparrow Search Algorithm,IMOSSA)进行求解,参考非支配排序将种群适应度值进行划分、引入正余弦策略提高解集质量、加入多项式变异算子和Levy飞行,提高解集的收敛速度和全局搜索能力,避免陷入局部最优。而后设计16种测试算例,将IMOSSA与其他多目标优化算法进行对比,验证了IMOSSA求解的优越性。最后,以某实际生产车间为例,将其生产调度划分为4种模式,证明算法求解的实用性。

含不相关机的多目标混合流水车间调度

考虑不相关机和传送等因素的多阶段混合流水车间问题,以最小化最大完工时间和总能耗为优化目标建立整数规划模型。针对该问题,提出一种多目标离散灰狼优化算法来求解。设计基于机器分配码和速度选择码的编码方式和基于最短处理时间原则的解码方案;采用反向学习策略改进初始灰狼种群质量;将基于多点变异的自走模式和基于均匀两点交叉与多点交叉的跟随模式结合构成搜索模式以协调开发和搜索能力;引入精英保留策略确保优良个体不丢失。通过一系列的仿真实验验证了该算法的有效性。

聚类和NSGA-Ⅱ联合算法在混合流水车间的应用研究

为了改善某高端装备制造企业总装车间混流生产调度困难、批处理阶段产品组批困难的问题,以及实现车间多个目标的同步联合优化,研究了含批处理机的混合流水车间多目标优化问题。首先根据车间运行情况建立了多目标优化模型,之后提出了基于K-means聚类算法和非支配排序遗传算法(NSGA-Ⅱ)的联合方法,设计了能够对不相容产品进行分组的聚类流程,以及基于产品组编号和组内产品编号的双层编码方式,为批处理工序设计了完整的组批流程。最后,使用车间生产案例进行测试,并将测试结果同仅使用NSGA-Ⅱ得到的结果进行对比,验证了所提方法的有效性。

采用改进两点交叉算子的改进自适应遗传算法求解不相关并行机混合流水车间调度问题

针对不相关并行机的混合流水车间调度问题,提出了改进两点交叉算子(ITPX)的自适应遗传算法。首先,利用精确取点方式提高两点交叉算子的求解性能;其次,论证了基于激素调节的自适应选择概率引导种群的收敛趋势;然后,建立优质染色体池和记忆因子来记录种群迭代的优质解,并实现两种不同区域的交叉。实验结果表明,ITPX可节省优化时间,提高求解性能;自适应概率可增强收敛性;改进两点交叉算子的改进自适应遗传算法(ITPX-IAGA)可缩短40%以上的求解时间,并提高求解性能。

基于改进免疫遗传算法的混合车间调度研究

建立了以最大总完成时间最小为目标的混合车间调度模型。该模型包括作业车间和并行流水装配车间两部分调度问题。为降低问题求解难度,采用分解的策略对调度问题分阶段求解,并引入多Agent协商机制和模拟退火算法与免疫遗传算法相结合,提出了基于分解策略的免疫遗传算法,并通过在某汽车减振器企业的实施验证了模型和算法的有效性。

混合流水车间调度问题的果蝇优化算法求解

针对不相关并行机混合流水车间调度问题,根据果蝇优化算法种群更新方式的特点,采用基于权重的编码方式进行编码操作,通过增加权重系数来提高算法的随机搜索能力。对算法参数的设置进行了分析,得到了最优参数组合。采用标杆实例进行仿真验证并与经典算法进行对比,验证了果蝇优化算法的有效性。

并行流程车间调度问题及其概率学习进化算法

并行Flowshop调度问题兼有并行机器和流程车间调度问题的特点,是一类新型的调度问题.针对最小化最大完工时间目标函数,建立了一般并行Flowshop调度问题的整数规划模型.鉴于问题的求解复杂性,设计了基于概率学习的求解算法.对随机生成的测试问题进行求解,实验结果显示出该算法求解并行Flowshop调度问题的良好潜能.

基于遗传算法的混合流水车间构建方法

在混合流水车间的构建过程中,每个阶段配置几台平行机最为合理是一个有待确定的问题.以设备空闲时间和工件平均流程时间加权均值最小化为目标函数对该问题进行了研究,采用遗传算法求解该NP-hard问题,染色体编码采用一种新的整数与实数相结合的方法,可实现对问题空间的全局随机寻优.算例研究显示,对任一算例,10次随机计算的目标函数平均值与最优值的差别率均小于1.3%,计算重复性好;计算花费时间均在20～30s,计算效率较高.

求解不相关并行机混合流水线调度问题的人工蜂群算法

针对不相关并行机混合流水线调度问题的特点,设计了一种基于排列的编码和解码方法,提出了一种有效的人工蜂群算法.在引领蜂和跟随蜂搜索阶段采用3种有效的邻域搜索方法,以丰富搜索行为;在侦察蜂搜索阶段通过随机搜索对种群进行更新,以增强种群多样性.同时,通过试验设计方法对算法的参数设置进行了分析,给出指导性参数组合.通过基于典型实例的数值仿真以及与已有代表性算法的比较,验证了所提算法的有效性和鲁棒性.

用MC-QPSO算法求解并行流水车间调度问题

针对并行流水车间调度问题的特点,提出了一种基于多种群协同进化的改进量子粒子群算法(MC-QPSO)进行求解。首先将整个量子粒子种群分解为多个子种群,然后各个子种群独立地演化,并通过周期性共享搜索信息,以获得对自身信息的更新。最后,通过具体仿真实例进行了求解验证,结果表明,在求解并行流水车间调度问题时,基于多种群协同的量子粒子群算法,在收敛速度、寻优性能等方面,都要优于遗传算法。

并行传送带式摩托车流水线调度模型与求解

针对一类摩托车制造柔性流水线中的调度问题,提出一种考虑工位差异的并行传送带式流水线调度模型。考虑不同在制品在生产线上不同工位的不同最大加工速度对传送带速度的影响因素,引入射频识别技术实时采集线上在制品的信息,通过及时调整传送带速度提高生产效率;根据生产实际需求,在生产线上不同种类在制品之间插入调整间隔,为更换车型提供准备时间。在此基础上,考虑模型以最小化最大完工时间为目标,采用基于极坐标编码的改进人工鱼群算法进行求解,说明了求解过程中的编码方法、母体迭代方式、人工鱼个体距离等关键技术。通过某摩托车生产企业的实际生产数据验证了该模型的有效性。

求解相同并行机混合流水线车间调度问题的分布估计算法

针对相同并行机混合流水车间调度问题,提出了一种有效的分布估计算法。针对基于排列的编码方式,设计了改进的启发式解码规则,进而提出了一种评价个体优劣的混合解码方式。建立了描述问题解空间分布的概率模型,通过对概率模型采样产生新个体,并基于优势种群更新概率模型的参数。通过基于标准测试集的数值仿真以及与已有算法的比较,验证了所提算法的有效性。

面向并行可重构计算的集装箱码头生产调度建模与仿真

将集装箱码头物流系统(container terminal logistics systems,CTLS)视为一个大规模并行处理系统,融合计算机体系结构中的并行计算和可重构计算的思想方法,抽象出基于属性的有阻塞动态可重构混合流水车间调度(dynamic reconfigurable hybrid flow shops with blocking based on attributes,DR-HFS-BA)模型对CTLS控制决策进行描述,得出面向DR-HFS-BA的CTLS多层双向作业体系。该生产调度模型能够精确描述CTLS的复杂结构和作业行为,帮助港口建立敏捷鲁棒的生产调度和性能评估决策支持平台。最后,一个集装箱码头生产实例被仿真和分析,验证了上述建模思想的可行性和可信性,从而为CTLS的任务调度和资源分配提出了新的解决思路。

具有学习效应的排序问题的某些新进展

Biskup首先将学习效应的的概念引入到排序问题中,并且在2008年给出具有学习效应的排序问题的全面综述。从此以后,具有学习效应的排序问题持续引起研究者的兴趣。除了Biskup综述所提到的模型外,文献中还有其他学习效应模型,对近年来文献中出现的具有学习效应的排序模型做一简要介绍。主要考虑3类模型:工件的实际加工时间依赖于具体的位置函数的模型,工件的实际加工时间依赖于抽象的位置函数的模型,工件的实际加工时间依赖于截断式学习函数的模型。

一种新型逻辑智能推理方法在混流生产线排产优化中的应用

针对有多个工作站、同一工作站中有不同效率并行机、各工作站之间有缓冲区、允许工件有等待条件下的混流生产线排产优化问题,提出了一种逻辑智能推理方法与遗传算法相结合的问题求解思路,解决了针对该典型问题求解排序长度时存在的数学建模及计算较为复杂的问题。

基于网络流的多并行机可中断开放车间调度算法

为提高开放车间的生产效率,研究了多并行机可中断开放车间调度问题,提出了基于网络流的调度算法。针对车间的特点,建立了以制造期最短为目标的整数规划模型,提出了工件有就绪时间约束时制造期下界的计算方法。采用网络流理论表示机器与工件间的分配关系和时间约束,建立了开放车间的网络流模型,将调度问题转换为最大流问题。引入最小负载优先和最大工作量优先两条启发式规则,设计了基于预流推进的最大流算法,并针对最大流算法中存在的局部优化问题,提出了最大流优化方法,得到机器资源的分配结果。在此基础上,建立了加工时间矩阵及减量集合,求得各机器上工件的加工顺序。使用两组随机数据对算法进行了实验,通过与制造期下界的对比,验证了算法的正确性。

灰熵并行分析法多目标次序敏感性研究

针对多目标优化算法对目标次序表现敏感这一特点,提出对灰熵并行分析法的目标次序敏感性进行分析.以多目标流水车间调度问题为对象,建立不同目标次序的多目标流水车间调度模型,以基于灰熵并行分析的GA优化不同次序的多目标模型.定义敏感系数,绘制敏感系数曲线图.实验结果表明,灰熵并行分析法对目标次序敏感,按目标值大小排列的升序和降序并不是最好的次序,震荡次序敏感系数最小.表明多目标优化时要选择合理目标次序以获得更好的优化结果.算法适应度值同样对目标次序敏感,对算法搜索效果影响明显.

基于灰熵并行分析优化算法的多目标流水车间调度

在供应链环境下构建一个多目标Flow Shop调度优化模型,采用灰熵并行分析(GEPA)法优化该多目标模型。在表征序列间相似程度的灰关联分析法基础上引入信息熵理论建立GEPA法,推导出的灰熵并行关联度衡量多目标Pareto解与理想解的相似程度,并将其作为适应度值引导算法进化,避免多目标优化问题中直接对目标权重赋值。在此基础上建立基于灰熵并行分析的遗传算法。实验结果表明,该算法可有效解决供应链环境下高维多目标Flow Shop调度问题,在多目标最优解、性能评价指标等方面均优于基于随机权重的遗传算法。