约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。

考虑模具约束和开机成本的并行机调度问题研究

受企业实际的注塑排产问题启发,本文研究了一类考虑模具约束和开机成本的相同并行机调度问题,目标是最小化加权延迟成本、换模成本和开机成本之和。构建了混合整数规划模型,证明了问题必定存在无机器空闲的最优解,提出了新的工作分配规则以确保产生的解都无机器空闲。在此基础上,设计了修改的ATCS算法(ATCS-MOD)和基于列表调度的遗传算法(GA-LS)两种算法。大规模数值实验证明GA-LS求解效果优于CPLEX和ATCS-MOD,更显著优于传统ATCS算法,同时也证明了新工作分配规则相比传统ATCS规则的优越性。

带准备时间的异构并行机调度规则自动设计方法

以大规模定制化的家电行业生产为背景,将家电总装产线的投产排序决策抽象成为一类带准备时间的异构并行机动态调度问题。针对人工调度规则解决动态调度问题简单高效,但场景适应性弱的特点,引入了基于遗传规划(genetic programming,GP)的规则自动设计框架。首先,通过分析家电总装产线生产特征以及优化需求,以最小化平均拖期为优化目标,建立异构并行机调度模型;随后,针对问题特征,构建线体指派-工单排序规则对协同进化的改进型GP算法,并提取线体、工单的特征属性输入GP算法框架以自动设计调度规则。最后,基于某家电企业实际案例数据设计大量算例测试集,通过对比GP算法与人工设计规则在差异化工况场景的实验结果,验证GP算法有效性,并进一步分析了GP算法构造规则受不同生产环境参数的影响。

自适应多种群Jaya算法求解绿色并行机调度问题

考虑到同一机器加工不同工件时存在序列相关准备时间的情况,研究了具有设置时间的绿色并行机调度问题。针对问题采用二维实数编码方案来有效映射解空间,并设计一种可以求解多目标的自适应多种群Jaya算法。该算法以Pareto最优解及拥挤度计算的机制进行寻优,在Jaya算法的基础上,设计了位置向量排序机制实现连续型解与绿色并行机调度问题离散型解的有效结合;将随机规则与工作均衡规则相结合提升初始种群质量并设计了自适应变化的多种群提升算法的搜索多样性与收敛速度。通过与其他4种算法的算例测试分析,结果表明自适应多种群Jaya算法在求解具有设置时间的绿色并行机调度问题上具有优越性。

用遗传算法解决在并行机上带有不同交货期窗口的Job-Shop调度问题

本文讨论了不同交货期窗口下的提前／拖期并行机调度问题，提出了染色 体用工件编号进行编码的编码规则，给出了用稳步遗传算法求解上述问 题的方法。仿真实验表明了算法及编码规则的可行性和有效性。

基于仿真的双目标并行机开放车间自适应动态调度

针对工件到达时间与加工时间不确定,且存在紧急工件的并行机开放车间调度问题,以TWC(total weighted completion time)与TWT(total weighted tardiness)为优化目标,设计了一种集成FlexSim仿真模型与NSGA-Ⅱ算法的自适应动态调度方法。该方法以FlexSim模型仿真工件的生成和加工为基础,根据车间实时负荷确定动态调度周期,对紧急工件进行右移重调度,利用NSGA-Ⅱ算法生成双目标优化的调度方案。某晶粒拣选车间生产数据的实验结果表明,相较于利用规则的实时动态调度与固定周期重调度,提出的方法能够在最小化调度偏离度的同时获得满意解。

交换突变策略改进萤火虫算法的异构并行机调度

序列相关设置时间的异构并行机调度问题是个NP(non-deterministic polynomial)问题,在高纬度情况下难以求解。选取任务完工时间为优化目标建立数学模型,提出一种基于交换突变策略改进的萤火虫算法,并应用该算法进行求解,以期在可接受的时间内提供近似最优解的可行方案。实验结果表明,所提出的算法在处理异构并行机调度问题时具有较突出的全局搜索优势,收敛速度较快,搜索精度高,测算了36个算例,其中的28个取得最优平均解,并且较萤火虫算法、模拟退火算法和遗传算法分别减少了11.12%、7.36%和1.43%的平均任务完工时间。

考虑附加资源和学习效应的不相关并行机调度

针对考虑附加资源和学习效应的不相关并行机调度问题(unrelated parallel machine scheduling problem,UPMSP),提出一种动态人工蜂群算法(dynamical artificial bee colony,DABC),实现最小化最大完成时间。给出一种新的编码方法和解码过程,并构建2个初始蜂群;提出一种蜂群评估策略,以动态确定雇佣蜂群和跟随蜂群;在雇佣蜂阶段和跟随蜂阶段采用不同搜索策略,以增强算法的探索能力。实验结果表明:DABC的新策略合理有效,且该算法在求解UPMSP时收敛性、平均值和稳定性更强,显示出较强的搜索性能。

虚拟单元内外运输能力受限的异质并行机调度研究

针对以往虚拟单元调度相关研究忽略了单元内外运输能力的限制、空载运输时间,以及对并行机的异质性考虑不够充分等问题,本研究以最大完工时间最小和总运输时间最短为目标,构建了虚拟单元运输组织与异质并行机调度联合决策模型,并提出了改进的NSGA-Ⅱ算法对模型进行求解。所提算法将粒子群算法与NSGA-Ⅱ的交叉、变异过程相融合,提高了算法的收敛速度。并将模拟退火算法的进化机制应用于NSGA-Ⅱ的变异过程,避免了NSGA-Ⅱ容易陷入局部最优的问题。通过小、中、大规模算例的仿真实验发现,所提算法与标准的NSGA-Ⅱ相比,算法的鲁棒性、收敛性和解集的质量、多样性等方面表现出较高的优势。

带恶化和学习效应的不相关并行机调度优化

研究了以同时最小化makespan和总加权拖期为目标的具有恶化和学习效应的不相关并行机调度问题。针对此类NP-hard问题,设计了基于两段式编码的改进模拟退火算法,结合随机程序和均匀分配策略分别产生第一段的工件加工序列编码和第二段的机器加工信息编码,以获取问题初始调度解,进而提出了分段式交换和变异扰动操作以得到更新后的新解。通过仿真实验测试改进模拟退火算法,将其与一些启发式算法对比,结果表明,所提算法可获得更好的近优解。

基于约束规划的资源受限并行机调度研究

针对多品种小批量生产调度等具有多层决策变量、多维度约束特点的资源受限并行机调度问题,结合问题特性与Cplex中的CP Optimizer优化引擎对于复杂约束的强大表达能力,建立了基于数量约束关联多层决策变量的CP模型与基于映射关系关联多层决策变量的CP模型。两者的主要区别是,前者使用的决策变量较少但两组决策变量之间具有一定的独立性,可能会牺牲一定的求解效率但能够更灵活地搜索解空间;后者使用的决策变量较多但本质上两类变量通过映射关系一一对应,可以更高效地利用约束规划中的约束传播技术。通过对家电企业发泡车间的实际订单数据进行求解,实验结果表明两种模型在不同特征的输入数据下,各有优劣,并分析了输入数据特征与模型选择的规律,验证了两种模型求解此类问题的可行性与有效性。

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

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

带工艺约束并行机调度问题的一种新的遗传算法

以最小化拖期任务数为目标 ,研究了解决一类带工艺约束并行机调度问题的新的遗传算法 .基于向量组的染色体编码方法简单、译码快速 ,并能自动满足工艺约束 ;扩展的顺序交叉算子EOX能自动满足工艺约束并尽量保留父代遗传信息 ,在较大程度上优于传统的交叉算子 ;位变异和交换变异相结合的变异方法有利于更好保持种群的多样性 .大量模拟数据与生产线应用实例表明本文所提的基于向量组编码的遗传算法是相当有效的 .

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

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

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

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

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

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

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

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

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

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

提高可扩展并行机群并行I/O效率的一个方法

随着CPU性能的高速提升，系统I／O能力的不足越来越明显地成为提高NOW系统整体性能的瓶颈．在分析现有基于NOW系统的并行I／O算法的基础上，通过理论推导，给出了一种寻求计算进程与计算结点之间最佳映射的方法．该方法可以在数据重分配时，使各计算结点间的通信量最小，从而达到提高系统并行I／O效率的目的．

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题,提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段,基于影响并行机调度性能的重要调度特征量,采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类;在工件排序阶段,采用基于规则编码的遗传算法,优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明,所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。