分布式装配置换流水车间调度问题研究综述

近几十年来,现代制造业发展迅速,一种趋势是在分布式生产工厂进行工件的加工,待完成后到装配工厂集中装配成最终产品。该模式在带来诸多好处的同时,对资源调度提出了新的挑战。针对分布式装配置换流水车间调度问题(distributed assembly permutation flowshop scheduling problem,DAPFSP),介绍了DAPFSP的背景和存在的主要困难,进而对以最小化最大完工时间为优化目标的DAPFSP,从数学模型、编解码策略、全局和局部搜索算法角度进行探讨,分别综述了以最小化总流程时间等为优化目标,具有零等待等约束,以及考虑准备时间等因素的DAPFSP研究成果。最后,对有待进一步开展的研究工作进行展望。

混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题

本文针对一类广泛存在的分布式加工装配和车辆配送集成调度问题(Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery,ISP_DPAVD),以最小化运输和延迟惩罚总成本为优化目标,提出一种混合三维分布估计算法(Hybrid three-Dimensional Estimation of Distribution Algorithm,H3DEDA)进行求解.ISP_DPAVD包含两个耦合的子问题,即加工装配阶段子问题(子问题1)和车辆配送阶段子问题(子问题2).由于每个子问题1的解(部分解1)均会确定1个具体的子问题2,故ISP_DPAVD的解空间非常庞大.根据这一特点,在H3DEDA中,先设计结合邻域变换的启发式规则来快速获取子问题2的优良解,以实现子问题间的部分解耦并明显缩减搜索空间,再设计三维EDA引导的全局搜索和变邻域驱动的局部搜索来获取ISP_DPAVD的高质量解.通过在不同规模测试问题上的仿真实验和算法比较,验证了H3DEDA求解ISP_DPAVD的有效性.

混合交叉熵算法求解模糊分布式装配流水线低碳调度问题

本文针对实际生产过程中普遍存在的不确定性,采用模糊数表示工件的加工时间与产品的装配时间,以同时最小化模糊最大完工时间和模糊总能耗为优化目标,建立模糊分布式装配流水线低碳调度问题(FDAPFLSP)的模型,进而提出一种混合交叉熵算法(HCEA)进行求解.首先,通过分析现有三角模糊数排序准则特点,并考虑生产调度问题的基本约束,设计一种实用的三角模糊数排序修正准则.其次,为增强算法性能,设计一种自适应变邻域局部搜索以实现对解空间不同区域的有效搜索.最后,仿真实验与算法对比验证HCEA可有效求解FDAPFLSP.

改进鲸鱼算法求解分布式装配柔性作业车间生产与配送联合调度问题

针对一类先加工后装配的离散生产模式,研究分布式制造环境下的装配柔性作业车间生产与配送两阶段联合调度问题。结合实际的生产情况,考虑供应链下生产与配送过程所产生的库存成本,以最小化生产和配送的总成本为联合调度优化目标,提出一种改进鲸鱼算法。针对联合调度的多阶段调度过程,设计了一种基于工序、产品、工厂、机器和车辆的五层编码策略;根据各阶段的特点提出了相应的混合种群初始化策略,以提高解的质量;以加强种群中领头鲸鱼个体与普通鲸鱼个体的联系为导向,改进了鲸鱼觅食的搜索操作并提出四种邻域结构,以增强算法的全局探索和局部搜索能力。最后,通过仿真实验,对比相关研究领域的多种算法来验证所提算法在收敛速度和求解质量等方面的优势,并且将联合调度与分阶段调度进行实验对比,验证了联合调度的优越性。

超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(Distributed Permutation Flow-shop and Vehicle Transportation Integrated Scheduling Problem,DPFVTISP),本文建立问题模型,并提出一种超启发式三维分布估计算法(Hyper-Heuristic three-Dimensional Estimation of Distribution Algorithm,HH3DEDA)进行求解.首先,根据DPFVTISP的问题特性,采用贪婪策略设计一种新颖的编解码规则.其次,为实现对DPFVTISP问题解空间中不同区域的深入搜索,设计10种低层启发式操作(即10种有效的邻域操作),并将其所构成的排列作为高层个体;同时在高层采用三维分布估计算法(three-Dimensional Estimation of Distribution Algorithm,3DEDA)学习和积累优质高层个体中块结构及其位置信息,再通过采样3DEDA中的概率模型生成新的高层个体或排列;进而在低层将高层所生成的每个新个体所表征的一系列有序的启发式操作作为一种新的启发式算法,对问题解空间执行较深入的邻域搜索.最后,通过仿真实验与算法对比验证HH3DEDA可有效求解DPFVTISP.

考虑行为特征的分布式流水线调度问题研究

流水线生产调度需要根据生产目标和各项生产约束条件,为每一加工对象规划具体的加工路径、时间、加工机器和具体操作等。生产调度作为中观层面,在管控之间发挥着承上启下的作用。当前大多数的生产调度主要依靠人工排程,在大规模生产作业中无法保证调度序列的最优化,由此使得流水线调度产生了一系列问题。基于此,在考虑行为特征的前提下,对分布式流水线调度问题进行研究,希望能够为企业生产实现资源利用最大化提供一些理论上的启发。

一类分布式零等待流水线自适应EDA调度

随着经济的发展,在各行各业中分布式生产变得越来越普及,故将更多的注意力放在分布式生产模型之上。为求解带有序相关设置时间和到达时间的零等待分布式流水线调度问题(No-wait Distributed Flow Shop with Sequence Dependent Setup Times and Arrival Times,NDPFSP with SDSTs and RDs),提出了一种自适应的分布估计算法(Adaptive Estimation of Distribution Algorithm, AEDA),用于最小化最大完成时间。首先,提出了更加适合于带到达时间问题的最早完成工厂问题的带有到达时间的最早完成工厂(the Earliest Completion Factory with Arrival Time, ECFAT)规则,使得解的生成过程有适当的判断,更加快速地提高当前代生成解的质量。其次,针对不同的问题规模进行局部搜索的深度做出相应的调整,使得在不同的规模下算法都能有很好的局部搜索能力。

低占空比传感网中分布式的环状流水线工作调度研究

低占空比传感网中节点的长时间睡眠会导致数据查询延迟的增加.如何调度节点唤醒时间从而最小化延迟,是一个难解的组合优化问题.提出一个分布式的环状流水线调度算法,不用长时间等待即可进行数据传输.分析表明,算法可获得较低的延迟和更长的网络生命周期.

分布式多柔性装配作业车间调度问题研究

针对分布式柔性装配作业车间环境,综合考虑了调度过程中的机器选择柔性、工人安排柔性和工序顺序柔性,构建了以最小化最大完工时间和最小化总能耗为优化目标的分布式多柔性装配作业车间调度问题(DMFAJSP)的数学模型。为求解DMFAJSP模型,提出了一种以分布估计算法为全局搜索组件、以邻域搜索算子为局部搜索组件的多维模因算法(MDMA)。最后,将所提出的算法与其他算法进行了对比试验,结果表明MDMA算法在求解DMFAJSP模型方面具有显著优势。

求解分布式混合流水线调度问题的改进双层嵌套式遗传算法

针对分布式混合流水线生产的生产调度问题,模拟实际排产中的排产到线和排产到时的排产策略,提出了基于改进双层嵌套式遗传算法的两层优化模型。外层依据流水线分配平衡和准时交货等基本原则总体上解决生产订单在流水线之间的分配问题,内层以最小生产时间为主要目的求解流水线的生产订单生产次序问题。考虑到双层嵌套式遗传算法的时间复杂性,基于模糊逻辑理论设计了一种模糊控制器来动态调整遗传算子,并采用主动检测停止方法,提高算法效率。使用某空调工厂的实际生产数据验证了算法的可行性、计算结果的准确性及排产策略的有效性,为高级计划与排程(Advanced Planning and Scheduling,APS)中大规模复杂供应链调度问题提供了可借鉴的方法。

基于改进生物地理学优化算法的分布式装配置换流水车间调度问题

提出了一种改进的生物地理学优化(MBBO)算法,以最小化最大完工时间为目标,求解分布式装配置换流水车间调度问题。MBBO算法在初始化阶段利用加工时间最短(SPT)规则和NR2规则对生成的可行解进行初步优化;然后在变异阶段采用基于工厂完工时间的工件插入启发式方法调整工件的工厂分配及加工顺序;最后结合模拟退火算法,跳出局部最优解,增强算法的全局搜索能力。对900个小型实例和540个大型实例进行仿真计算,并与现有的12种启发式与元启发式算法以及基本生物地理学优化(BBO)算法进行比较,证明了MBBO算法的优越性,同时更新了70个实例的最新已知最优方案。

求解分布式两阶段装配流水车间调度的帝国竞争-协作算法

针对分布式两阶段装配流水车间调度问题(DTAFSP),提出了一种新型优化方法-帝国竞争-协作算法(ICCA)以最小化总延迟时间.该算法在帝国竞争算法基础上,结合历史进化数据,提出一种基于最强帝国搜索能力与最弱帝国计算资源之间自适应交换的帝国间协作方法,并给出一种新型帝国竞争策略,以提高算法搜索效率.进行了大量计算实验,计算结果验证了ICCA策略的合理性和有效性以及它在求解DTAFSP方面较强的搜索优势.

基于混合迭代贪婪算法的分布式车间调度研究

分布式协同生产已逐渐成为经济全球化和生产国际化背景下的主要生产方式。以总装配时间为优化目标,提出一种混合迭代贪婪(HIG)算法,求解分布式装配阻塞流水车间调度问题(DABFSP)。在HIG算法的初始化阶段,采用问题驱动的构造启发式方法生成初始解。在HIG算法的破坏-重构阶段,采用基于邻域信息的扰动策略更新可行调度序列。在HIG算法的局部搜索阶段,使用基于邻域结构的插入操作进一步更新可行解。以一定概率接收较差调度序列进入下一代,从而避免算法早熟收敛。在试验阶段,选取了以不同工件数、机器数、工厂数和产品数为组合的共计900个问题实例,测试、比较了HIG算法和其他8种先进对比算法的性能。通过统计学分析得出结论:在求解DABFSP时,所提出的HIG算法具有显著的优势。

基于状态树的装配流水线生产在线调度

构建了一种基于装配状态树的具有三层体系结构的在线调度模型,实现"将生产计划和调度直接做到生产线上"。首先,将产品的装配状态变迁过程表达为一棵装配状态树;其次,用状态方程来描述装配流水线生产过程,建立从装配位置空间到装配状态空间的一一映射,在此基础上构造包括决策层、连接层及执行层的三层次在线调度体系结构。通过在制品的位置信息来推算在制品的装配状态,利用状态树计算在制品的调度空间;进而以调度空间为约束,根据决策层的生产任务安排,对连接层的调度方案进行在线调整和实时控制。

自适应混合EDA求解一类三阶段装配流水线调度问题

针对生产过程中广泛存在的一类三阶段装配流水线调度问题,即带序相关设置时间的三阶段装配流水线调度问题,提出一种自适应混合分布估计算法,用于最小化平均完成时间和最大延迟时间的加权和。提出初始种群和初始概率分布模型生成机制,使概率分布模型能适当地积累较多优质解的信息,以提高AHEDA在进化初期的搜索能力。设计了基于信息熵的概率分布模型自适应更新机制和保留优良模式的新种群采样生成方法,增强了算法的全局搜索能力。引入基于Insert的邻域搜索来增强算法的局部搜索能力。最后通过仿真实验和算法比较验证了AHEDA的有效性。

超启发式交叉熵算法求解分布式装配柔性作业车间调度问题

本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP),建立问题模型,以最小化最大完工时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解.首先,设计基于工序序列、工厂分配和产品序列的三维向量编码规则和结合贪婪策略的解码规则,同时提出4种启发式方法以提高初始解的质量.然后,设计高低分层结构的HHCEA,高层为提高对搜索方向的引导性,采用交叉熵算法(CEA)学习和积累优质排列的信息,其中各排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成;低层为增加在解空间中的搜索深度,将高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制,以此作为一种新的启发式方法执行搜索.最后,通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP.

考虑准备时间的两阶段装配流水线订单接受与调度决策

针对两阶段装配流水线订单接受与调度问题,基于有限生产能力考虑生产订单序列相关准备时间约束,构建以订单利润最大化为目标的优化决策模型,提出一种变邻域半置换改进遗传算法进行求解。该改进算法利用整数矩阵编码和启发式规则提升初始种群的质量,设计随机半置换单点交叉、互换变异等改进遗传策略提高解的质量,并提出原基因重插入法确保新种群个体均为可行解,结合变邻域搜索提高算法的局部搜索能力。最后,针对不同规模算例进行求解并与其他算法进行对比,验证算法的可行性和有效性。

求解分布式装配式建筑逆向物流问题的离散人工蜂群算法

给出了一种混合离散的人工蜂群算法(HDABC)用于求解分布式装配式建筑逆向物流问题.为实现ABC算法的离散化,提出了一种基于两级向量链表的十进制编码机制.结合逆向物流特征和ABC算法特点,设计了8种邻域结构.算法通过对两个现实生产实例求解,并与当前文献中的典型算法对比分析,验证了提出的算法无论在算法运行时间还是在求解质量上,都具备良好的性能.

混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.

超启发式交叉熵算法求解模糊分布式流水线绿色调度问题

针对实际生产过程中普遍存在的加工时间不确定性,采用模糊数表示工件的加工时间,以同时最小化模糊最大完工时间和模糊总能耗为优化目标,建立模糊分布式流水线绿色调度问题(green distributed permutation flow-shop scheduling problem with fuzzy processing time,GDPFSPFPT)的模型,进而提出一种超启发式交叉熵算法(hyper-heuristic cross-entropy algorithm,HHCE)进行求解.首先,HHCE采用一种新颖的三角模糊数排序准则合理计算个体的目标函数值,可在算法搜索过程中较准确发现优质解区域;其次,HHCE在高层利用基于贡献率的评价方法确定8种特定邻域操作所构成的各排列的优劣,同时采用交叉熵(cross-entropy,CE)方法学习较优排列的信息并生成新排列,进而在低层把高层生成的每个排列作为一种启发式算法,对低层相应个体执行一系列邻域操作,以实现对问题解空间较多不同区域的搜索;然后,HHCE将基于非关键路径的节能策略用于对低层每代种群中的较优个体执行局部搜索,从而进一步提高算法获取低能耗非劣个体或解的能力;最后,仿真实验与算法对比表明,HHCE可有效求解GDPFSPFPT.