一类加工需要额外资源的平行机调度问题的算法设计

给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件,除需要机器资源外,还需要一个单位额外资源的问题,考虑额外资源的种类和数量有限,以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载,在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法;给出了一种有效的分支策略以避免重复分支,设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验,验证了算法的正确性和在不同参数配置下的有效性。

考虑外包的平行机调度问题的多目标遗传算法

研究了一类考虑外包的平行机调度问题,目标是使作业外包总成本与最大完工时间同时最小化。通过对该类问题进行形式化描述与分析,设计了一种数字串形式的解的表示方法,其中每位数字表示固定作业对应的机器编号,该方法能够有效缩小解空间,从而提高搜索效率。进而构建了一种带精英策略的非支配遗传算法PD-NSGA-Ⅱ,为该类多目标调度问题提供Pareto最优解集。大量数据实验结果表明,所构造的PD-NSGA-Ⅱ算法能够在合理的时间内有效求解该类调度问题,其解的质量与计算效率均优于SPEA算法。

最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.

具有凸资源消耗函数的最小化Makespan的平行机调度问题

研究了一类资源受限的平行机调度问题,其中假定作业的处理时间是其消耗资源量的凸减函数,调度的目标是在限定资源总量的情况下最小化Makespan(最大完工时间)。给出了此类NP-hard问题的形式化描述。定义了关键机器与非关键机器,给出了非最优解必定存在非关键机器的论断。尽快缩短非关键机器与关键机器之间工作量的差距能够有效逼近最优解,从而构造了快速的模拟退火算法。设计了一个下界用于衡量解的精度,并用于构造模拟退火算法迭代结束条件。算法性能通过20000组随机数值算例进行了测试,实验结果表明所构造的模拟退火算法能够在0.1秒之内有效求解1000个作业的问题并将相对误差控制在0.01%以内。该算法体现出很高的精度和计算效率。

具有周期维护最小化时间表长的两台平行机调度问题(英文)

本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.

安装时间具有退化效应的MapReduce模型下的平行机调度

考虑了平行机环境下安装时间具有退化效应且加工时间具有分步恶化效应的MapReduce模型调度优化问题。在MapReduce模型中,每个工件包含Map和Reduce两道工序。其中,Map工序可以分割成若干个子任务并在多台平行机上同时加工,而Reduce工序只有在该工件Map工序的所有子任务完成后才能启动加工,而且只能在一台机器上连续加工。研究Reduce工序的启动安装时间具有线性恶化效应、两个工序的加工时间具有分步恶化效应的平行机调度问题,构建了以最小化最大完成时间为优化目标的混合整数规划模型。给出了问题解的一个下界;同时,设计了采用单纯形差分扰动机制的改进灰狼算法以及贪婪算法进行模型求解。最后,利用数值仿真实验,将灰狼优化算法、贪婪算法、遗传算法的解与问题的下界进行对比,验证了模型与所设计算法的有效性。

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。

考虑系统时变效应与预防性维护的平行机调度

实施预防性维护(PM)能改善晶圆制造厂离子注入工序中设备状态从而改善晶圆卡(lot)加工时间延长的问题,基于此,研究考虑系统时变效应与预防性维护的平行机调度问题.以最小化最大完工时间为优化目标,建立包括设备可靠性以及工件实际加工时间约束的数学非线性规划模型.设计求解该模型的学习型遗传算法(LGA),针对问题特性引入最优支配规则改进变异操作,构建预防性维护知识库指导进化后期预防性维护决策,以提升算法质量.算例实验结果表明,改进的学习型遗传算法能有效应对系统时变效应对生产调度的影响,减少最大完工时间,具有实用价值.通过灵敏度分析实验研究晶圆卡对设备状态衰退的敏感程度和预防性维护对调度决策的影响,为实际车间调度提供决策支持.

考虑维护和可中断工件的混合型平行机调度问题研究

考虑部分机器需要周期维护,其余机器无需维护的混合型平行机调度问题。一组给定的可中断且加工时长均相等的工件需要加工,工件数不超过机器数。目标是将所有工件安排到机器上加工,使得时间表长最小。首先分析一些特殊情况;然后对于一般情况通过建立注水模型给出最优时间表长的一个下界;接着对水位的2种情况分别给出目标值等于下界的多项式时间算法;最后给出了求解该调度问题的一个多项式时间最优算法。

具有周期维护的最小化工件完成时刻之和的平行机调度问题

考虑具有周期维护的m台平行机调度问题,一组给定的工件在这些机器上加工,目标是给出工件完成时刻和最小的调度方案。基于经典的SPT(最短加工时间优先)算法,提出了名为MSPT的启发式算法,并证明了该算法优于SPT算法。

含换模时间的平行机调度问题研究

在工厂实际生产中,模具的换模时间在生产调度中不可忽略。为了更合理地研究平行机车间调度问题,本文将存在序依赖的换模时间考虑进调度模型之中,同时以最小完工时间和最小拖期时间为目标,在经典遗传算法的基础上,对算法选择算子以及交叉变异概率进行改进,避免早熟现象的发生。通过计算结果的比较,证明本文中调度模型更符合实际生产情况,改进后的算法能够得出更高质量的解,且求解效率更高。

平行机调度问题的列生成方法研究

探讨求解平行机调度问题的列生成算法的基本原理,然后结合动态规划和分支定界技巧,对平行机调度问题提出求解最优解的列生成方法。

部分机器需要周期维护的混合型平行机调度问题的数学规划模型

对于部分机器需要周期维护,其余机器在所考虑的时间范围内一直可用的混合型平行机调度问题,分别采用基于机器拆分的建模思想和基于机器拼接的建模思想构建该调度问题的数学规划模型。

具有周期维护的最小化加权总完工时间的平行机调度研究

针对具有周期维护的最小化加权总完工时间的平行机调度问题,首先证明了该调度问题是NP-难问题,并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法,其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析,结果显示:WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长pmax呈倒U型;工件个数n越大,WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。

具有负载依赖型维护时长的平行机调度问题

本文考虑具有工具更换的平行机调度问题,机器的维护时长依赖于维护前的负载,目标为最小化时间表长.首先,基于维护时长函数为单调不减函数得到最优调度方案应有的两个性质——单台机器加工的工件个数最多相差一个;每台机器在最后一个维护间隔应尽可能多地加工工件.其次,对维护时长函数为凹函数、凸函数和线性函数的情况分别给出算法MNJF, SJF和SLE.最后,证明算法MNJF, SJF以及SLE均为对应情况的最优算法,且算法MNJF对于维护时长函数为线性函数的情况也是一种最优算法.

综合考虑服务水平和资源占用的平行机调度问题

[目的]对综合考虑服务水平和资源占用的平行机调度问题进行研究,建立以最小化总延误和机器使用数量之和为优化目标的优化模型。[方法]针对该问题的特点,设计了一种改进的模拟退火算法进行求解。采用不同规模的数值实验测试算法的性能,并对问题参数展开灵敏度分析。[结果]改进的模拟退火算法具有良好的求解效率和求解质量。[结论]灵敏度分析表明,增加资源储备可以使企业更好地平衡服务水平和资源占用。模型能够对企业实现资源节约型制造提供指导和决策支持。

加工时间依赖于资源消耗量的平行机调度问题

研究了一类平行机调度问题,其中假定作业加工时间是资源消耗量的线性减函数,调度的目标是在限定最大完工时间时最小化资源消耗总量.分析了对应单机问题的最优算法和下界构造方法,进而提出了两个优化策略用于构造模拟退火算法和禁忌搜索算法.考虑了多种最大完工时间限制情形,构造了大量随机实验数据,对算法解的精确度及计算效率进行了测试.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.

基于MapReduce模型带准备时间的平行机调度优化

研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.

基于MapReduce模型带任务分割的平行机调度优化

研究一类基于MapReduce模型的两阶段平行机调度问题。该模型中的每个工件包含Map和Reduce两道工序,前一工序的任务可以划分并同步加工,而后一工序不可划分,结合工件的到达时间、交货时间等约束,以最大完工时间和总延迟时间的加权和作为优化目标构建混合整数规划模型,设计采用差分变异策略和逐维角度扰动机制的改进鲸鱼优化算法求解模型。数值仿真实验结果表明,所设计的算法相对于经典的鲸鱼优化算法、粒子群算法的求解效果有显著的提升,验证了模型和所设计算法的有效性。