基于双线性链表编码的并行机大规模调度遗传算法

面向并行机大规模调度问题,提出了一种以工件聚类作为初始染色体种群构成基础的遗传算法。算法首先采用改进的模糊C-均值聚类算法,按影响调度的工件重要特性指标,将工件进行聚类;然后采用基于双线性链表结构的编码方式,表示工件聚类在并行机上的生产次序及任务数量,并据此设计了相应的交叉和变异算子;最后进行了实验分析及实例应用,该算法可以在合理的计算时间内获得满意的优化质量。     

调度策略在并行机调度仿真的应用

等同并行机调度对提高生产率有着重要意义,针对动态随机环境,运用调度策略建立仿真模型,等同并行机调度以最大化吞吐率和最小化延迟工件量为多目标函数,仿真模型用于一个7台等同并行机的装配车间,模型参数和实验数据来自于某大型装备制造企业当前车间,现行调度主要采取先入先出(FIFO)策略。通过最小化加工时间优先(SPT)和最早订单完成时间优先(EDD)等策略用于仿真模型并与现行策略对比,仿真结果显示,将调度策略用于动态随机系统对企业提高生产效率有显著优越性。     

改进遗传算法求解同类并行机优化调度问题

研究在给定n个可拆分加工的作业和m台同类不同速加工机器的条件下,考虑同时优化拖期成本和生产能耗的生产调度问题。采用理想点法构建目标函数,建立了考虑拖期成本与能耗的同类并行机排产调度模型。在传统遗传算法基础上,引入多种群、自适应和局部搜索策略以提高搜索效率,并提出个体差异度以改进交叉效果。分别用不同规模的问题进行算例实验,对比改进遗传算法和传统遗传算法性能,求解排产方案。实验结果表明改进算法计算效果优于标准遗传算法,能够求解不同规模该类问题,且具有良好的稳健性。     

基于免疫算法的并行机间歇过程模糊生产调度

研究了一类具有顺序无关模糊产品切换时间和成本以及模糊单位加工时间和成本的并行机间歇过程调度问题,目的是确定每种产品在每个设备上处理的批次数目、批量以及批次顺序,优化目标为最小化总完成时间和最小化总生产成本。根据任意设备上同种产品的所有批次均顺序处理的性质,建立了问题的模糊运输模型。利用加权和方法将多目标函数转化为单目标函数,并使用基于积分值的方法对模糊数进行排序。提出了基于排列边集编码的免疫算法,通过求解不同规模的问题实例证明,免疫算法不仅能获得比遗传算法和免疫遗传算法更好的解,而且比免疫遗传算法更高效,同时具有良好的动态性能。     

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

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

基于轮盘赌编码和粒子群算法的并行机调度优化

将粒子群算法用于优化并行机调度问题,将遗传算法选择策略方法中的轮盘赌方法引入到编码方法中,提出了一种基于轮盘赌的粒子编码方法,用于表示并行机调度问题的解。通过对两个并行机算例的计算说明,基于轮盘赌编码方法的粒子群算法都能有效地对并行机调度问题进行优化。     

基于混合差分进化算法的并行机批处理调度问题研究

考虑到实际生产中产品多、批量小的特点,建立了一种带工艺约束的并行机批处理调度优化模型。为解决调度中的分批问题,提出了一种新的基于产品需求量的批量划分方案及批量染色体编码方式,采用两级差分进化算法来解决批量划分和批次调度问题;针对标准差分进化算法收敛速度慢、易出现早熟现象等问题,引入动态随机搜索和随机变异的局部搜索策略,以增强标准差分进化算法的局部搜索能力。测试算例及调度实例的仿真结果表明,该算法能有效地提高算法收敛速度,平衡其全局搜索和局部探索能力。     

并行机作业车间等量分批多目标优化调度

为降低并行机作业车间等量分批多目标优化调度问题的复杂度,提高优化效率,提出了一种基于仿真技术和改进非支配排序遗传算法的分步优化方法.建立了一类以完工时间最短和总制造成本最低为优化目标的并行机作业车间等量分批多目标优化调度模型;将各产品进行等量分批,以Witness为仿真平台建立并行机作业车间等量分批生产仿真模型,通过组合仿真优化得到产品理想的等量分批方案,从而将原问题转化为并行机作业车间多目标优化调度问题;设计了一种改进的非支配排序遗传算法,对并行机作业车间多目标优化调度进行求解.通过算例分析验证了该方法的有效性.     

调整时间与顺序相关的等同并行机调度

调整时间与顺序相关的等同并行机调度在生产服务业与制造业中有着十分广泛的应用背景,具有计算复杂性的主要特点。调整时间与顺序相关的等同并行机调度是将被加工工件集的各工件分配给等同并行机资源,并安排工件的加工次序。它是决策的一种形式,其目的是优化一个或多个目标。研究以最小化被加工工件最大完工时间为目标的调整时间与顺序相关的等同并行机调度,建立该问题的数学规划模型,根据问题的结构特点开发基于两段式染色体表达的遗传算法以获得该问题的近似最优解;在所建立数学规划模型的基础上,引入所求解问题的下界对近似最优解的质量进行评价。对具有不同规模的问题实例进行计算试验,计算结果表明所设计的遗传算法能够在可接受的计算时间内获得合理的解。     

基于两阶段蚁群算法的带非等效并行机的作业车间调度

针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。     

一种求解变速机调度问题的混合蚁群优化算法

针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法.引人单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解.通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析.结果表明,在相同迭代次数下,混合算法优于对比算法.     

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

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

模具电火花加工车间的非同等并联机混合遗传算法

针对模具企业电火花加工车间的生产调度特点,提出了一种非同等并联机的调度数学模型.与此同时,建立了一种遗传与模拟退火的混合算法,并应用于模具企业电火花加工车间,实际算例说明了该数学模型和求解方法的可靠性和有效性.     

一类并行机调度问题的动态调度算法

针对不确定制造环境中配件数量约束条件发生变化后的并行机动态调度问题,提出了一种基于操作属性模式的并行机动态调度算法.该算法针对总拖期时间性能指标的优化,根据配件负载的裕量和相邻操作的属性模式,对原调度方案的操作次序和操作上机时间进行了调整.在不同操作和设备规模下,以及不同配件数量变化幅度下进行了数值计算.数值计算结果和实际应用结果表明,该算法是有效的,具有计算复杂度低、实时性好、对原调度算法不敏感的特点.     

求解一类异构并行机调度问题的分布估计算法

针对流程工业中广泛存在的一类复杂异构并行机调度问题,即带工件加工约束和序相关设置时间的异构并行机调度问题,提出一种分布估计算法,用于最小化最早完工时间.首先,合理借鉴了蜜蜂养殖中“双王分区春繁法”的思想,提出一种新的概率模型更新方式,并通过子种群概率模型的交叉融合构造采样概率模型,进而引导种群进化方向,用于提高算法全局搜索的深度;其次,设计了一种基于插入法的变异操作,用于保持分布估计算法的种群多样性水平,进而提高算法全局搜索的宽度;最后,引入基于插入法和首次改进跳出原则的局部搜索方法来增强算法的局部开发能力.仿真实验和算法比较验证了所提算法的有效性和鲁棒性.     

禁忌-并行遗传算法在作业车间调度中的应用

根据并行遗传算法与禁忌搜索算法的优点,提出了一种禁忌一并行遗传算法。该算法能够避免早熟,不仅保证了算法的全局收敛,而且提高了算法收敛速度和解的质量,特别是在求解大规模问题上具有优势。仿真结果证明了该算法的有效性。     

具有随机加工时间和机器故障的流水车间调度

不同的流水车间往往具有不同的生产方式,为提高调度方案对不同生产方式下随机因素的处理能力,重点考虑了2种生产方式下3种不同情况的随机调度。针对这3种情况,以最小化最大完工时间为目标,研究了具有随机加工时间和随机机器故障的置换流水车间调度问题,提出了处理不同生产方式下随机因素的3种计算方法,通过预测机器的期望故障时刻来计算每个任务的完工时间。采用启发式规则和遗传算法相结合的方法,确定出最佳调度方案,并进行了实验分析和比较。     

基于遗传算法的作业车间调度研究与应用

提高大功率船舶柴油机的生产能力和水平,对提高我国造船行业的国际竞争力有着重要的意义。介绍作业车间调度问题,提出一种改进的遗传算法,同时将此算法应用于船舶柴油机的作业车间调度,该算法采用基于工序的编码方式,考虑了机床与工艺路线的约束,求解以关键设备的利用率最高和产品的加工周期最短为目标的静态调度问题,并通过具体的实例仿真分析其有效性。     

基于动态机器故障率的并联加工系统资源多目标调度

针对并联加工系统,为处理生产过程中因机器故障导致的加工资源动态调度问题,考虑系统资源负荷和故障率存在的动态相互制约关系,依据子周期划分的不同策略,对调度后的加工总时间、预防维修时间和系统可靠度进行量化研究,构建多目标动态调度模型。采用基于Pareto熵的多目标粒子群算法对模型进行求解,通过改进个体最优解选择策略,提升最优解选取的多样性;通过差熵来估计种群所处进化状态,改进算法的搜索能力。以某企业的加工系统为实例,利用该模型进行加工资源调度方案设计,通过模糊决策得到的多目标权重,选取最优调度方案,并进行多个参数对比,验证在加工资源调度过程中,集成考虑动态机器故障率和基于机器最大役龄约束划分子周期的可行性,不仅可以完成订单准时交付,还可以使企业有更好的柔性去应对可能到来的紧急订单。