基于MapReduce模型带准备时间的平行机调度优化 被引量：9

1

作者 黄基诞 郑斐峰 +1 位作者 徐寅峰 刘明 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2019年第1期174-182,共9页

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

关键词 平行机调度 MAPREDUCE 准备时间 正弦余弦算法(SCA)

原文传递

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

2

作者 史烨 李凯 左春荣 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2012年第7期1485-1493,共9页

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

关键词 平行机调度 资源分配 模拟退火 禁忌搜索

原文传递

考虑外包的平行机调度问题的多目标遗传算法 被引量：6

3

作者 孙超平 杨平 李凯 《中国机械工程》 EI CAS CSCD 北大核心 2014年第23期3174-3179,共6页

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

关键词 平行机调度 外包 PARETO最优 非支配遗传算法

下载PDF 职称材料

考虑共享机器租借费用的在线订单加工策略及竞争分析

4

作者 徐寅峰 智荣腾 +1 位作者 郑斐峰 刘明 《中国管理科学》 CSCD 北大核心 2023年第4期142-150,共9页

探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素,运用在线理论与竞争分析方法构建了平行机调度over-list在线模型,其最小化目标是工件总完工时间与机器租赁... 探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素,运用在线理论与竞争分析方法构建了平行机调度over-list在线模型,其最小化目标是工件总完工时间与机器租赁总成本之和。针对工件均为单位长度的情形,分析了问题离线最优方案,进而证明了竞争比下界为1+6a-3√12a-3+/18a+(6b+3)√12a-3+6b^(2)+6b-1,其中,a为固定租赁成本系数,b(0≤b<a)为可变租赁成本系数。当a→+∞,b/a→0+时,该下界趋于4/3;同时,设计给出了在线策略TS,并证明当a=2时该策略竞争比为4/3;当a≥3时,其竞争比为1.89。 展开更多

关键词 共享制造 在线调度 平行机调度 竞争比 总完工时间

原文传递

考虑设备时变效应的晶圆加工序列决策调度方法 被引量：3

5

作者 杨雯惠 陈璐 张昕莹 《哈尔滨工业大学学报》 EI CAS CSCD 北大核心 2022年第7期29-36,共8页

为改善半导体生产过程中设备状态不确定引起的时变效应可能造成生产计划难以推进、生产效率下降等问题,使用考虑设备时变效应的晶圆加工序列决策调度方法制定调度方案。采集过往加工工时数据,挖掘设备状态变化的特征参数与晶圆的加工工... 为改善半导体生产过程中设备状态不确定引起的时变效应可能造成生产计划难以推进、生产效率下降等问题,使用考虑设备时变效应的晶圆加工序列决策调度方法制定调度方案。采集过往加工工时数据,挖掘设备状态变化的特征参数与晶圆的加工工时时变效应的关联关系,从而建立考虑时变效应的平行机调度模型,实现最大完工时间的最小化。设计集成调度优化知识的混合搜索算法(HSAOSK),利用单机调度最优规则与多机调度优化知识库减少搜索空间,提高算法的计算效率。实际算例的分析结果表明:HSAOSK算法求解小规模算例的最优解与精确算法(BRA)相同,求解大规模算法时与其他优化算法相比,最大完工时间可减少6.17%,且计算时间非常短,HASOSK算法的优越性能满足构建半导体调度决策方案的需求。调度决策方法不仅能为具有时变效应的半导体生产系统提供有效的加工序列决策,还能针对设备状态提供不同的维护决策以保证生产效率。 展开更多

关键词 设备状态 时变效应 平行机调度 决策方法 混合搜索算法

下载PDF 职称材料

最小化时间表长的平行机调度近似算法研究 被引量：4

6

作者 程贞敏 李洪兴 谷敏强 《北京师范大学学报（自然科学版）》 CAS CSCD 北大核心 2012年第1期11-15,共5页

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

关键词 平行机调度 周期维护 时间表长 近似算法 最坏误差界

下载PDF 职称材料

考虑平行机环境下紧急任务最大等待时间的优化调度

7

作者 隋杨 郑斐峰 徐寅峰 《工业工程与管理》 CSCD 北大核心 2023年第5期119-129,共11页

以快速响应无预知到达的紧急任务为研究背景,考虑两台平行机环境下紧急任务等待时间的优化调度问题。给定机器最大完工时间上界,考虑机器在加工过程中可空闲情形,在不中断常规任务的条件下,以最小化紧急任务的最大等待时间为研究目标,... 以快速响应无预知到达的紧急任务为研究背景,考虑两台平行机环境下紧急任务等待时间的优化调度问题。给定机器最大完工时间上界,考虑机器在加工过程中可空闲情形,在不中断常规任务的条件下,以最小化紧急任务的最大等待时间为研究目标,构建了混合整数规划模型,并对问题的某一类最优方案进行分析,证明了该类最优解满足两台机器无同时空闲以及最大完工时间达到上界的性质。基于该性质,设计了一种启发式算法以及随机键编码的遗传算法对该问题进行求解。仿真实验结果表明:遗传算法在小规模工件求解时略优,但计算时间较长;启发式算法在大规模工件求解时其求解质量与求解时间均有明显优势。本研究可为实际中对限定机器工作负荷的场景如何安排机器的空闲时间以快速响应紧急任务提供决策建议。 展开更多

关键词 平行机调度 紧急任务 最大等待时间 启发式算法

原文传递

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

8

作者 冯鑫 陈旎珊 秦岚 《重庆师范大学学报（自然科学版）》 CAS 北大核心 2023年第2期1-7,共7页

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

关键词 平行机调度 生产排序 资源占用 模拟退火算法

原文传递

基于MapReduce模型带任务分割的平行机调度优化 被引量：3

9

作者 黄基诞 郑斐峰 +1 位作者 徐寅峰 刘明 《控制与决策》 EI CSCD 北大核心 2019年第7期1514-1520,共7页

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

关键词 平行机调度 MAPREDUCE 鲸鱼优化算法 并行处理 混合整数规划 任务分割

原文传递

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

10

作者 李凯 史烨 马英 《管理工程学报》 CSSCI 北大核心 2013年第1期56-62,共7页

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

关键词 平行机调度 MAKESPAN 资源分配 可控处理时间

下载PDF 职称材料

不同交货期时间窗下的平行机生产问题研究 被引量：3

11

作者 杨婉琳 朱伏平 《机械设计与制造》 北大核心 2020年第4期233-235,239,共4页

在工业4.0环境下,满足定制生产需求并能够准时交货的智能工厂成为发展趋势。研究在JIT原则下,考虑订单交货期、到达时间和设备产能资源等约束条件下的平行机生产排序问题,以订单任务提前生产的总时间最小化作为目标,基于历史订单构建虚... 在工业4.0环境下,满足定制生产需求并能够准时交货的智能工厂成为发展趋势。研究在JIT原则下,考虑订单交货期、到达时间和设备产能资源等约束条件下的平行机生产排序问题,以订单任务提前生产的总时间最小化作为目标,基于历史订单构建虚拟订单进行产品组合,建立交货期约束系统求解模型,使用"最小提前生产时间的启发式算法"进行求解,解决不同交货期约束下平行机生产排序过程中的资源冲突、工期延误、设备浪费等问题,以保证准时交货。最后,使用仿真案例实验验证该方法的可行性,为进一步研究不同交货期时间窗下较大规模的复杂平行机排序问题提供可借鉴的方法。 展开更多

关键词 平行机调度 不同交货期约束 虚拟订单 最小提前生产算法

下载PDF 职称材料

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

12

作者 程贞敏 张喜娟 李洪兴 《应用数学》 CSCD 北大核心 2010年第1期1-6,共6页

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

关键词 平行机调度 周期维护 时间表长 LPT算法

下载PDF 职称材料

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

13

作者 张昕莹 陈璐 杨雯惠 《浙江大学学报（工学版）》 EI CAS CSCD 北大核心 2022年第2期408-418,共11页

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

关键词 平行机调度 可靠性 时变效应 预防性维护 学习型遗传算法

下载PDF 职称材料

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

14

作者 程贞敏 张喜娟 李洪兴 《北京师范大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第4期350-354,共5页

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

关键词 平行机调度 中断 准备时间 总完工时间 最坏情况误差界

下载PDF 职称材料

考虑最小化最大完工时间间隔的三台平行机调度 被引量：2

15

作者 郑斐峰 隋杨 徐寅峰 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2021年第4期1025-1036,共12页

针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进... 针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进而给出最优方案的基本性质;其次,基于最优解的性质证明了目标值的一个下界并设计了O(n^(2))时间的算法来求解该下界值;最后运用预留尽可能多的空闲时间(RMST)在一台机器上的思想,设计了改进的RMST算法(IRMST)来求解该问题.通过利用数值仿真实验与RMST算法,遗传算法等其它算法及下界进行对比,验证了该算法的有效性. 展开更多

关键词 平行机调度 完工时间间隔 启发式算法

原文传递

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

16

作者 曹雁卿 《江西科学》 2012年第4期434-437,共4页

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

关键词 平行机调度 周期维护 完成时刻之和 启发式算法

下载PDF 职称材料

应用于生产调度问题中的约束规划计算技术 被引量：1

17

作者 尹兆涛 樊少明 《计算机应用与软件》 CSCD 2011年第5期226-228,271,共4页

从问题建模和求解技术两个方面介绍了应用于生产调度问题中的新兴技术——约束规划,同时将该技术与数学规划技术作了比较,并应用平行机调度问题进行实例验证。

关键词 生产调度问题 约束规划 数学规划 平行机调度

下载PDF 职称材料

一类带平行机的两阶段柔性流水调度近似算法 被引量：1

18

作者 张明会 韩鑫 《应用数学学报》 CSCD 北大核心 2018年第3期420-432,共13页

本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型，模型中第1阶段有1台机器，第2阶段有m台同构并行机，每个任务在第2阶段需要size／台机器同时并行执行．目标是所有任务都完成的完工时间最小化．该模型已被证明出是... 本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型，模型中第1阶段有1台机器，第2阶段有m台同构并行机，每个任务在第2阶段需要size／台机器同时并行执行．目标是所有任务都完成的完工时间最小化．该模型已被证明出是强NP难的，并给出了在某种特定情况下近似比为3的近似算法．本文首先详细分析了前人近似算法基本过程，给出该算法近似比分析的局限性；接着给出了一个近似比为3的算法，摒弃了前人给出的近似比为3时的约束条件；最后研究了当第2阶段机器数为2和3时的两种特定情况，采用列表调度思想，给出了近似比为25和2．67的近似算法． 展开更多

关键词 柔性流水调度 平行机调度 近似算法 近似比

原文传递

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

19

作者 周菊 程贞敏 《数学理论与应用》 2022年第4期105-114,共10页

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

关键词 工具更换 平行机调度 负载依赖 时间表长

下载PDF 职称材料

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

20

作者 王天坤 《装备制造技术》 2014年第5期102-103,106,共3页

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

关键词 列生成 平行机调度 分支定界

下载PDF 职称材料