基于并行分层的工作流调度优化算法

针对给定截止时间约束下用有向无环图描述的工作流时间费用优化问题,逆向分层算法未考虑工作流中各个任务在实际执行过程中的并行性而带来相对较多的时间碎片,提出一种基于并行分层的工作流调度算法——并发级别工作流调度算法。该算法将工作流在实际执行过程中的某个任务和其他一个(或具有依赖关系的相邻多个)并行执行的任务尽量划分到同一层,并根据各层的并行度分配冗余时间,对每层中存在具有依赖关系的多个相邻任务采用Markov决策过程算法进行时间费用优化。对平衡结构和非平衡结构的有向无环图所描述的工作流进行大量模拟实验,对比最小临界路径算法、逆向分层算法和期限顶级算法,实验结果表明所提算法具有较显著的优势。     

具有交货期和工装数量约束的平行机调度

提出了一类具有工件交货期和工装数量约束的平行机调度问题.以降低部件拖期惩罚总费用为目标,建立了该问题的数学模型.提出一种遗传与模拟退火相混合的算法来求解该类问题,即GASA算法.算法在初始种群的生成上,采取了随机生成和按启发式规则生成相结合的方法;并引入模拟退火算法作为变异算子,以提高种群的多样性.最后,通过实例仿真,验证了GASA算法的有效性,并与GA算法进行了对比,对比结果表明GASA更优越.     

基于交货期和设备能力约束的作业车间调度方法研究

以往对作业车间调度问题的研究中,不少学者尝试添加新的约束条件使之更符合实际的生产情况。但对设备能力约束的考虑不够细致,往往简单地将设备能力视为常数或连续的能力空间。针对这种情况,本文建立了以交货期为指标并带有设备能力约束的作业车间调度模型,采用双向调度方法力求工件的完工时间和交货期尽量靠近,从而使惩罚成本最低。设计了利用时间坐标映射求解工序开／完工时间的方法,该方法消除了因设备能力不等造成的工作时间段间隔,最终通过遗传算法求得优化的调度方案。     

具有工件约束的模具制造优化调度算法研究

为解决具有工件约束的模具制造优化调度问题,提出了一种利用蚁群算法和优先分配启发式调度算法相结合的调度算法。该算法能够方便地描述问题的约束条件的特点。首先,由蚁群算法确定模具零件各工序所用的加工机床,用节点模式下的有向图描述问题的解空间,用蚂蚁种子信息素踪迹更新策略对信息素进行更新,以获得问题的解;然后,利用优先分配启发式调度算法确定在同一台机床上加工的各零件的先后顺序。实验结果验证了算法的有效性。     

带特殊工艺约束的双目标并行多机调度问题研究

港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题.采用基于进化策略的混合算法,设计了基于工件的编码方式,对次序杂交算子进行了扩展,设计了一种扩展“倒位”变异算子,并采用相邻不同基因多次交换的局部搜索方法.算法的设计自动满足了工艺约束,保证了种群的多样性.设计了最大完工时间和生产加工成本双目标评价函数,最后通过计算对混合算法进行了验证.     

基于粒子群算法的并行多机调度问题研究

将港口拖轮作业调度问题描述为一类带特殊工艺约束的并行多机调度问题,采用粒子群算法求解该类调度问题,提出了一种2维粒子表示方法,通过对粒子位置向量进行排序生成有效调度,并采用粒子位置向量多次交换的局部搜索方法来提高算法的搜索效率。最后,通过计算验证了混合粒子群算法的有效性。     

基于交货期窗口约束的多级供应链批量调度问题研究

为解决三级供应网络中供应商和制造商的加工任务顺序优化和合理性问题,建立了交货期窗口约束下供应商与制造商协同决策的批量调度模型.以最小化供应链的物流和交付总成本为目标,综合考虑了供应商与制造商的库存成本、运输成本和未按期交付的惩罚成本.提出了采用两级遗传算法和两级编码的模型求解算法.通过一个仿真算例,验证了调度模型和求解策略的可行性.     

参数化设计中表示约束关系的方法

介绍了一种新的参数化设计中约束关系的描述方法，并根据这些约束数据形式提出了基于有向无环图的数据结构表示思想。这种数据结构集工程图所有的约束关系于一体，具有结构单一、操作简便、信息完备且无冗余等优点，已在工程图理解系统中得到成功的应用。     

考虑加工时间和交货期模糊的批调度问题研究

针对实际生产中存在的时间参数不确定性问题,对单机环境下同时考虑模糊加工时间和模糊交货期的成批调度问题进行研究。分别用三角模糊数和梯形模糊数表示模糊加工时间与交货期,分析了最小化总延迟的情况下工件的模糊交货期和模糊加工时间的隶属度函数与决策者对该工件的完工时间满意度的函数关系,以满意度为优化目标,建立模糊数学优化模型。设计BFEDD(Best Fit Earliest Due Date)启发式算法,以及改进的殖民地同化策略（殖民地移动）,建立改进的帝国主义竞争算法（IICA,Improved Imperialist Competitive Algorithm）对所研究问题进行求解,最后设计仿真实验验证了算法的有效性。     

基于有向约束图的装配序列并行化方法研究

并行装配与串行装配相比可以缩短装配时间,提高装配效率。为了实现产品的并行装配,提出了基于有向约束图的装配序列并行化方法。定义了装配约束矩阵和零件约束度的数学模型来描述装配体在装配过程中各零件的干涉状态,建立了装配体的有向约束图描述零件间的约束关系,给出了基于关联解除的有向约束图分解方法生成装配序列,采用装配序列并行化策略产生了基于多叉树结构的并行装配序列。通过机用虎钳装配实例验证结果表明了该方法的可行性。     

同型机在线调度问题研究进展

为了阐明在线调度的概念及其与在线算法的关系,为相关研究提供支持,对同型机在线调度问题的研究现状进行综述。描述了同型机在线调度问题的概念,以加工约束和目标函数为标准,对同型机在线调度问题进行分类。从基本模型、允许拒绝工件以及考虑机器适用约束等角度对逐个调度工件类在线调度问题进行回顾,从极小化最大完工时间、极小化加权完工时间和以及极大化加权按期完工工件数等角度对工件随时问到达类在线调度问题进行总结,指出了现有研究的不足,并探讨了同型机在线调度问题的未来研究方向。     

以JIT为目标的多阶段非等同并行机调度问题研究

针对多阶段非等同并行机模式下的准时化(Just-in-TimeJ,IT)调度问题,采用由遗传算法和禁忌搜索算法混合的禁忌遗传递阶算法进行求解。禁忌遗传递阶算法用禁忌搜索算法对工件最佳加工次序进行搜索,而相应评价值由遗传算法计算得出。遗传算法采用基于阶段机器号的二维矩阵编码,可有效地避免不可行解的产生,同时采用自适应改进提高遗传算法跳出局部最优的能力。实际算例说明禁忌遗传递阶算法计算结果稳定可靠,适合于解决多阶段非等同并行机的JIT调度问题。     

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

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

基于剩余率求解非标准作业车间调度问题逆序算法

为了克服现有效率算法、遗传算法和逆序算法等求解非标准作业车间调度问题时存在的不足 ,提出了一种新的逆序算法。将非标准作业车间调度问题进行数学描述 ,给出目标函数 ,针对非标准作业车间调度问题的复杂性 ,构造了一种基于剩余率函数的逆序调度算法 ,以确定出最佳的开工日期。与其他算法相比 ,该算法的复杂性更小 ,调度结果更优     

可变机器约束的模糊作业车间调度问题研究

在车间实际加工中,工件的加工时间和交货期是一个模糊数,而且工件的某道工序有多台机器可供选择。针对这类作业的车间调度,提出了以极大化最小客户满意度为指标的可变机器约束的模糊作业车间调度模型,并给出了算法设计。应用遗传算法在适应度函数处理中引入模糊数处理方法,解决作业车间模糊调度问题,实现调度优化。仿真实验结果表明了该调度方法的有效性,为可变机器约束的模糊作业车间调度提供了一种实现途径。     

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

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

基于增强学习的平行机调度研究

尝试运用增强学习方法来研究平行机调度问题,通过定义系统状态、行为和报酬函数,把调度问题转化为平均报酬型半马尔可夫决策过程,并使用结合函数泛化器的R-Learning算法来解决.提出排名算法,并利用它和两种常用的调度规则(最短期望加工时间规则和先进先出规则)来定义增强学习的行为.实验结果表明,R-Learning算法通过仿真实验学习较优的调度策略,在不同的决策状态下选择最优或次优的行为,对每个测试问题的效果都优于以上任何一条调度规则.     

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

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