最小化多MapReduce任务总完工时间的分析模型及其应用

1

作者 田文洪 陈瑜 +2 位作者 王心阳 薛瑞尼 赵勇 《计算机工程与科学》 CSCD 北大核心 2014年第4期571-578,共8页

随着大规模的MapReduce集群广泛地用于大数据处理,特别是当有多个任务需要使用同一个Hadoop集群时,一个关键问题是如何最大限度地减少集群的工作时间,提高MapReduce作业的服务效率。可将多个MapReduce作业当做一个调度任务建模,观察发... 随着大规模的MapReduce集群广泛地用于大数据处理,特别是当有多个任务需要使用同一个Hadoop集群时,一个关键问题是如何最大限度地减少集群的工作时间,提高MapReduce作业的服务效率。可将多个MapReduce作业当做一个调度任务建模,观察发现多个任务的总完工时间和任务的执行顺序有密切关系。研究目标是设计作业调度系统分析模型,最小化一批MapReduce作业的总完工时间。提出一个更好的调度策略和实现方法,使整个调度系统符合经典Johnson算法的条件,从而可使用经典Johnson算法在线性时间内获取总完工时间的最优解。同时,针对需要使用两个或多个资源池进行平衡的问题,提出了一种线性时间解决方案,优于已知的近似模拟方案。该理论模型可应用于提高系统响应速度、节能和负载均衡等方面,对应的应用实例提供了证实。 展开更多

关键词 HADOOP MAPREDUCE 批量作业 调度优化 最小化总完工时间

下载PDF 职称材料

求解考虑机器调整时间的并行机分批优化调度问题 被引量：2

2

作者 孙思汉 陶翼飞 +2 位作者 董圆圆 张源 王加冕 《软件》 2020年第4期20-27,共8页

基于目前车间调度问题是以单个或整批进行生产加工的并行机调度模型已不再符合实际工况下的车间生产。提出以最小化最大完工时间为优化目标,对遗传差分进化混合算法,灰狼差分进化混合算法进行了比较。为提高加工工件进行分批及分批之后... 基于目前车间调度问题是以单个或整批进行生产加工的并行机调度模型已不再符合实际工况下的车间生产。提出以最小化最大完工时间为优化目标,对遗传差分进化混合算法,灰狼差分进化混合算法进行了比较。为提高加工工件进行分批及分批之后子批的分配与排序效率,该问题是对不同规模的经典并行机调度问题进行求解并展示两种算法的求解,证明了灰狼差分进化混合算法在寻优性能上优于遗传差分进化混合算法,不仅具有更好的解的稳定性,而且具有更高的寻优精度。 展开更多

关键词 机器调整时间 灰狼差分进化混合算法 并行机调度 最小化最大完工时间

下载PDF 职称材料

舰载机模块化弹药调度方案优化设计 被引量：4

3

作者 吕晓峰 杨东泽 马羚 《系统工程与电子技术》 EI CSCD 北大核心 2023年第2期465-471,共7页

舰载机模块化弹药存储和调度是未来发展的主要趋势之一。模块化弹药调度与整弹调度相比,调度对象的数量成倍增加并且多了一个弹药装配环节,使调度工作的难度呈指数级增长。针对模块化弹药调度问题,建立以任务完成时间最小化和各舱室与... 舰载机模块化弹药存储和调度是未来发展的主要趋势之一。模块化弹药调度与整弹调度相比,调度对象的数量成倍增加并且多了一个弹药装配环节,使调度工作的难度呈指数级增长。针对模块化弹药调度问题,建立以任务完成时间最小化和各舱室与升降机平均工作时间最小化为优化目标,以各模块调度次序、机器选择和调度起始时间为约束条件的舰载机模块化弹药调度模型,设计递推法计算任务完成时间,并使用改进的遗传算法对模型进行求解,结合模块化弹药特点优化多层编码方式,使染色体更加完整地表达弹药在各个阶段的信息。通过仿真验证,所提的舰载机模块化弹药调度方法生成的调度方案具有可行性。 展开更多

关键词 模块化 多层编码遗传算法 舰载机弹药调度 最小化最大完工时间 柔性车间调度问题

下载PDF 职称材料

求解柔性作业调度问题的协同进化粒子群算法 被引量：7

4

作者 宋存利 《计算机工程与应用》 CSCD 2013年第21期15-18,共4页

柔性作业车间调度问题是典型的NP难题。柔性作业车间调度问题涉及到设备分配和作业分配两个问题,并且两问题之间具有较强的耦合性,提出了基于协同进化的粒子群算法。该算法将设备选择和工件调度分别作为两个寻优变量,利用PSO算法分别进... 柔性作业车间调度问题是典型的NP难题。柔性作业车间调度问题涉及到设备分配和作业分配两个问题,并且两问题之间具有较强的耦合性,提出了基于协同进化的粒子群算法。该算法将设备选择和工件调度分别作为两个寻优变量,利用PSO算法分别进行寻优,根据两个变量的内容进行互相评价。实验表明该算法对FJSP问题的有效性。 展开更多

关键词 粒子群算法 柔性车间作业调度问题 最小化完工时间 邻域搜索

下载PDF 职称材料

含不相关机的多目标混合流水车间调度

5

作者 轩华 关潇风 王薛苑 《计算机工程与设计》 北大核心 2024年第1期315-320,F0003,共7页

考虑不相关机和传送等因素的多阶段混合流水车间问题,以最小化最大完工时间和总能耗为优化目标建立整数规划模型。针对该问题,提出一种多目标离散灰狼优化算法来求解。设计基于机器分配码和速度选择码的编码方式和基于最短处理时间原则... 考虑不相关机和传送等因素的多阶段混合流水车间问题,以最小化最大完工时间和总能耗为优化目标建立整数规划模型。针对该问题,提出一种多目标离散灰狼优化算法来求解。设计基于机器分配码和速度选择码的编码方式和基于最短处理时间原则的解码方案;采用反向学习策略改进初始灰狼种群质量;将基于多点变异的自走模式和基于均匀两点交叉与多点交叉的跟随模式结合构成搜索模式以协调开发和搜索能力;引入精英保留策略确保优良个体不丢失。通过一系列的仿真实验验证了该算法的有效性。 展开更多

关键词 多阶段混合流水车间 离散灰狼优化算法 不相关机 多目标优化 绿色调度 最小化最大完工时间 传送时间

下载PDF 职称材料

求解柔性作业车间调度问题的离散食肉植物算法

6

作者 宋存利 李金泰 《大连交通大学学报》 CAS 2024年第4期113-120,共8页

针对传统群智能优化算法求解柔性作业车间调度问题时易陷入局部最优且寻优能力不足的困境,以最小化最大完工时间为目标提出一种离散的食肉植物算法。首先,为提高初始种群的多样性,提出了3种初始化种群策略;其次,为提高算法各时期的搜索... 针对传统群智能优化算法求解柔性作业车间调度问题时易陷入局部最优且寻优能力不足的困境,以最小化最大完工时间为目标提出一种离散的食肉植物算法。首先,为提高初始种群的多样性,提出了3种初始化种群策略;其次,为提高算法各时期的搜索能力,为生长因子设计了一种自适应策略,并对植物执行了交叉以及基于4种邻域结构的贪婪变异操作;最后,通过对Brandimarte基准问题进行仿真并与其他文献算法进行对比,证明了所提算法在收敛速度和求解质量方面都具有较好的性能。 展开更多

关键词 柔性作业车间调度 最小化最大完工时间 食肉植物算法 自适应生长因子 混合算法

下载PDF 职称材料

求解作业车间调度问题的改进混合灰狼优化算法 被引量：34

7

作者 姚远远 叶春明 《计算机应用研究》 CSCD 北大核心 2018年第5期1310-1314,共5页

灰狼优化算法(GWO)是目前一种比较新颖的群智能优化算法,具有收敛速度快、寻优能力强等优点。将灰狼优化算法用于求解复杂的作业车间调度问题,与布谷鸟搜索算法进行比较研究,验证了标准GWO算法求解经典作业车间调度问题的可行性和有效... 灰狼优化算法(GWO)是目前一种比较新颖的群智能优化算法,具有收敛速度快、寻优能力强等优点。将灰狼优化算法用于求解复杂的作业车间调度问题,与布谷鸟搜索算法进行比较研究,验证了标准GWO算法求解经典作业车间调度问题的可行性和有效性。在此基础上,针对复杂作业车间调度问题难以求解的特点,对标准GWO算法进行改进,通过进化种群动态、反向学习初始化种群以及最优个体变异三个方面的改进操作,测试结果表明,改进后的混合灰狼优化算法能够有效跳出局部最优值,找到更好的解,并且结果鲁棒性更强。 展开更多

关键词 灰狼优化算法 作业车间调度 最小化最大完工时间 混合算法

下载PDF 职称材料

基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题 被引量：11

8

作者 张其亮 俞祚明 《计算机集成制造系统》 EI CSCD 北大核心 2017年第3期609-615,共7页

针对以最小化最大完工时间为目标的无等待流水车间调度问题,提出一种基于优势种群的离散果蝇算法进行求解。算法基于排列形式进行编码,以PF_NEH(Profile Fitting&Nawaz-Enscore-Ham)算法为基础构造优势种群;在果蝇优化算法的嗅觉搜... 针对以最小化最大完工时间为目标的无等待流水车间调度问题,提出一种基于优势种群的离散果蝇算法进行求解。算法基于排列形式进行编码,以PF_NEH(Profile Fitting&Nawaz-Enscore-Ham)算法为基础构造优势种群;在果蝇优化算法的嗅觉搜索阶段,提出分段破坏迭代贪婪算法和成组插入法进行邻域搜索;在视觉搜索阶段,设计部分交叉策略对较差个体与优势个体进行信息交换,从而引导较差个体向种群中心位置移动,同时提出多种变异机制对优势个体进行变异,以提高种群的多样性。通过标准实例测试,验证了所提算法的有效性。 展开更多

关键词 离散果蝇优化算法 无等待流水车间调度 最小化最大完工时间

下载PDF 职称材料

基于种群的多层次迭代贪婪算法优化阻塞流水车间调度问题 被引量：6

9

作者 张其亮 俞祚明 《计算机集成制造系统》 EI CSCD 北大核心 2016年第10期2315-2322,共8页

针对以最小化最大完工时间为目标的阻塞流水车间调度问题,提出一种有效的基于种群的多层次迭代贪婪算法进行求解。算法基于排列形式进行编码,提出NEH_PF(Nawaz-Enscore-Ham&profile fitting)算法构造初始种群,以提高初始解的质量;... 针对以最小化最大完工时间为目标的阻塞流水车间调度问题,提出一种有效的基于种群的多层次迭代贪婪算法进行求解。算法基于排列形式进行编码,提出NEH_PF(Nawaz-Enscore-Ham&profile fitting)算法构造初始种群,以提高初始解的质量;设计了多层次迭代贪婪算法,并基于插入、交换策略对个体进行变异,基于Path-Relinking算法对个体进行交叉,以提高个体局部搜索能力,并提出部分交叉策略来更新种群。通过标准实例测试,验证了所提算法的有效性。 展开更多

关键词 种群 迭代贪婪算法 阻塞流水车间调度 最小化最大完工时间

下载PDF 职称材料

TFT-LCD模块组装调度问题的改进灰狼优化算法 被引量：5

10

作者 姚远远 叶春明 杨枫 《小型微型计算机系统》 CSCD 北大核心 2018年第10期2146-2153,共8页

随着半导体产业的快速发展产生了很多重要的生产计划问题,其中,TFT-LCD(薄膜晶体管液晶显示器)属于资金和技术密集型产业,面对激烈的市场竞争亟需提高生产力.提出一种改进灰狼优化算法求解以最小化最大完工时间为优化目标的TFT-LCD模块... 随着半导体产业的快速发展产生了很多重要的生产计划问题,其中,TFT-LCD(薄膜晶体管液晶显示器)属于资金和技术密集型产业,面对激烈的市场竞争亟需提高生产力.提出一种改进灰狼优化算法求解以最小化最大完工时间为优化目标的TFT-LCD模块组装调度问题,针对该问题特点对基本灰狼优化算法进行了一系列改进,包括工序插入式方法解码,机器选择部分采用一种全局搜索、局部搜索和随机产生相结合的初始化方法,基于搜索的方法进行工序排序部分初始化,以及均匀交叉操作和进化种群动态操作.同时,对所设计的改进灰狼优化算法的计算复杂度和收敛性进行了分析.由于该问题与柔性作业车间调度问题(FJSP)比较相似,通过对FJSP问题的不同规模基准算例的仿真实验,验证了算法有效性.另外,通过对实际生产活动中的一个TFT-LCD模块组装调度问题的测试,进一步表明本文提出的算法解决真实TFT-LCD模块组装调度问题的实用性和有效性. 展开更多

关键词 改进灰狼优化算法 TFT-LCD模块组装调度 柔性作业车间调度 最小化最大完工时间 收敛性分析

下载PDF 职称材料

基于改进离散人工蜂群算法的同类机调度优化 被引量：7

11

作者 张架鹏 倪志伟 +2 位作者 倪丽萍 朱旭辉 伍章俊 《计算机应用》 CSCD 北大核心 2020年第3期689-697,共9页

针对一类最小化最大完工时间的同类机调度问题,考虑到机器的加工效率和产品的交付时间,引入同类机调度问题的数学模型,提出一种改进的离散型人工蜂群算法(IDABC)求解该问题。首先,引入种群初始化策略,得到均匀分布的种群,并获得待优参... 针对一类最小化最大完工时间的同类机调度问题,考虑到机器的加工效率和产品的交付时间,引入同类机调度问题的数学模型,提出一种改进的离散型人工蜂群算法(IDABC)求解该问题。首先,引入种群初始化策略,得到均匀分布的种群,并获得待优参数的生成策略,加快种群的收敛;其次,借鉴差分进化算法的变异算子和模拟退火算法的思想,改进雇佣蜂和跟随蜂的局部搜索策略,并利用最优解的优质信息改进侦察蜂,增加种群多样性、防止算法陷入局部最优;最后,分析算法的性能和参数,并将改进的算法应用于同类机调度问题,在15个算例上的实验结果表明,与混合离散人工蜂群(HDABC)算法相比,IDABC的求解精度和稳定性分别平均提高了4.1%和26.9%,且具有更好的收敛性,表明在实际场景中IDABC可以有效求解同类机调度问题。 展开更多

关键词 同类机调度 最小化最大完工时间 变异算子 人工蜂群算法 优化

下载PDF 职称材料

自动化仪表检测中的车间调度问题优化与仿真 被引量：1

12

作者 武子科 潘攀 +3 位作者 彭诚 吕秀莎 梁子涵 张洪光 《计算机工程与设计》 北大核心 2022年第3期814-820,共7页

为解决自动化仪表检测工作中的作业车间调度问题以提高其工作效率,提出一种基于生命力选择的精英鲸鱼优化算法。利用生命力选择方法替换表现较差的个体,克服鲸鱼优化算法在调节搜索范围方面的不足,避免种群陷入局部最优,加快种群向全局... 为解决自动化仪表检测工作中的作业车间调度问题以提高其工作效率,提出一种基于生命力选择的精英鲸鱼优化算法。利用生命力选择方法替换表现较差的个体,克服鲸鱼优化算法在调节搜索范围方面的不足,避免种群陷入局部最优,加快种群向全局最优解收敛的速度。结合标准实例和北京东方计量测试研究所的自动化仪表检测实例,对算法进行仿真分析,验证了精英鲸鱼优化算法在求解作业车间调度问题的有效性和稳定性,其可以满足自动化仪表检测工作中的日常检测任务调度需求。 展开更多

关键词 作业车间调度 自动化仪表检测 鲸鱼优化算法 最小化最大完工时间 调度效率

下载PDF 职称材料

基于综合模糊评价法优化绿色柔性流水车间调度问题 被引量：1

13

作者 卫少鹏 王婷 周彤 《物流科技》 2021年第3期28-32,52,共6页

针对柔性流水车间生产能耗高和噪音大的问题,建立了最大完工时间调度模型,设计了遗传算法,将求解过程分成两步,第一步以最小化最大完工时间为主要目标,求解出多个最小化最大完工时间相同的最优方案;第二步把能耗、噪音和设备利用率指标... 针对柔性流水车间生产能耗高和噪音大的问题,建立了最大完工时间调度模型,设计了遗传算法,将求解过程分成两步,第一步以最小化最大完工时间为主要目标,求解出多个最小化最大完工时间相同的最优方案;第二步把能耗、噪音和设备利用率指标作为绿色约束和评价依据,基于综合模糊评价法筛选出最优方案。研究结果表明:(1)不同方案的差异较大,选择针对性的调度方案会较大提高生产效益;(2)通过求解生产实例验证了模型和算法的有效性,有利于指导制造企业推行可持续发展战略。 展开更多

关键词 柔性流水车间调度 最小化最大完工时间 综合模糊评价法 遗传算法

下载PDF 职称材料

求解作业车间调度问题的改进飞蛾扑火优化算法 被引量：1

14

作者 耿凯峰 叶春明 王怡 《南阳理工学院学报》 2019年第2期18-24,共7页

针对作业车间调度问题,为了克服早熟收敛和容易陷入局部最优等不足,提出一种基于Lévy飞行的改进飞蛾扑火优化模型(LMFO)。首先,采用MFO算法求解作业车间调度问题,并与粒子群算法(PSO)、遗传算法(GA)进行对比研究,证明了MFO算法求... 针对作业车间调度问题,为了克服早熟收敛和容易陷入局部最优等不足,提出一种基于Lévy飞行的改进飞蛾扑火优化模型(LMFO)。首先,采用MFO算法求解作业车间调度问题,并与粒子群算法(PSO)、遗传算法(GA)进行对比研究,证明了MFO算法求解此类问题的有效性;然后,采用改进的随机键编码,引入Lévy飞行对MFO算法进行改进;最后,仿真实验表明,LMFO算法在求解作业车间调度问题时优于MFO、PSO和GA算法,能够跳出局部最优找到更好的解,且具有一定的鲁棒性。 展开更多

关键词 作业车间调度 飞蛾扑火算法 Lévy飞行 最小化最大完工时间

下载PDF 职称材料

机器带有循环时间窗口的排序问题

15

作者 曹庭锴 刘敏 张同全 《应用数学进展》 2021年第2期367-370,共6页

给定一个在有限数量机器上加工的作业集合,如何合理地安排作业在机器上加工以达到最优解就称之为排序问题,排序问题是经典的组合优化问题之一。机器带有循环时间窗口的排序问题是在我们已知的经典排序问题基础上,给定机器上的循环时间窗... 给定一个在有限数量机器上加工的作业集合,如何合理地安排作业在机器上加工以达到最优解就称之为排序问题,排序问题是经典的组合优化问题之一。机器带有循环时间窗口的排序问题是在我们已知的经典排序问题基础上,给定机器上的循环时间窗口,目标是求解机器带有循环时间窗口的排序问题的最小化最大完工时间所用的天数。本文分析了问题的NP困难性,给出了一种求解机器带有循环时间窗口的排序问题的近似算法,最后证明了当k】m时,算法的最坏情况近似比为3/2,当k≤m时,算法具有一个最优平凡解。 展开更多

关键词 NP困难性 最小化最大完工时间 近似算法 循环时间窗口 排序问题

下载PDF 职称材料

基于离散Jaya算法的线缆生产调度方法 被引量：1

16

作者 林剑 李扬远 +2 位作者 陈蒙蒙 干梦清 王凌武 《计算机集成制造系统》 EI CSCD 北大核心 2023年第12期4206-4214,共9页

线缆生产调度优化问题广泛存在于电线电缆行业的生产实际中,本质上属于带安装时间和复杂资源约束的柔性作业车间调度问题。针对线缆生产调度优化问题,建立了以最小化最大完工时间为目标的问题数学模型,提出一种离散Jaya算法解决该问题。... 线缆生产调度优化问题广泛存在于电线电缆行业的生产实际中,本质上属于带安装时间和复杂资源约束的柔性作业车间调度问题。针对线缆生产调度优化问题,建立了以最小化最大完工时间为目标的问题数学模型,提出一种离散Jaya算法解决该问题。在Jaya算法框架下,基于单列编码方式和左移解码策略,融入优先工序交叉算子和反向学习搜索策略,引导算法更有效地搜索问题空间,以提升算法性能,从而实现最大完工时间最小化。基于企业生产实际生成的实例集,通过仿真实验与对比分析,表明了所提算法在求解线缆生产调度问题中具备较高的有效性和稳定性。 展开更多

关键词 线缆生产 Jaya算法 调度优化 最小化最大完工时间

下载PDF 职称材料

一种求解IPPS问题的混合遗传迭代邻域搜索优化算法

17

作者 何佳炜 王皓 +4 位作者 段旭洋 王卓识 陈智超 汪敏 韩子熹 《机械设计与研究》 CSCD 北大核心 2024年第3期30-35,45,共7页

针对最小化最大完工时间的工艺规划与调度集成问题,设计并研究一种混合遗传-迭代邻域搜索优化算法。首先考虑到兼具工序柔性、序列柔性和加工柔性的问题特质,采用三层染色体编码方式,同时考虑到可行解集过大,运用结合启发式规则分配法... 针对最小化最大完工时间的工艺规划与调度集成问题,设计并研究一种混合遗传-迭代邻域搜索优化算法。首先考虑到兼具工序柔性、序列柔性和加工柔性的问题特质,采用三层染色体编码方式,同时考虑到可行解集过大,运用结合启发式规则分配法的种群初始化方式;其次,考虑遗传算法更侧重于全局优化,引入迭代邻域搜索对遗传算法较优解进行局部搜索,并通过多次迭代后最优解仍保持不变时引入新种群进行竞争的策略,避免陷入局部最优陷阱;最后通过与已有算法对已知案例的求解结果进行比较分析,发现本算法得出最优结果优于绝大多数的优良算法,随后采用某飞机制造公司某工位为背景构建的实际案例进行验证,说明了该算法的有效性。 展开更多

关键词 工艺规划与调度集成问题(IPPS) 混合遗传-迭代邻域搜索 最小化完工时间

原文传递

基于交叉选择的变邻域蜂群算法求解置换流水车间调度问题 被引量：1

18

作者 亓祥波 王宏伟 马志强 《制造技术与机床》 北大核心 2023年第5期179-187,共9页

针对置换流水车间调度问题的特性,设计了一种基于交叉选择的变邻域蜂群算法。首先,算法在初始化种群阶段加入了NEH启发式算法,进而提高初始解的质量。在算法迭代的初期引入了差分进化算子进行交叉与选择,从而提高解的多样性。在算法的... 针对置换流水车间调度问题的特性,设计了一种基于交叉选择的变邻域蜂群算法。首先,算法在初始化种群阶段加入了NEH启发式算法,进而提高初始解的质量。在算法迭代的初期引入了差分进化算子进行交叉与选择,从而提高解的多样性。在算法的局部搜索阶段对50%最优个体加入了交换与逆序两种变邻域操作,增强了算法的搜索能力。通过正交实验选择合适的参数,在Car、Rec以及Taillard标准测试集上进行仿真实验,结果表明所提算法优于与之对比的其他群智能算法。最后,以最小化最大完工时间为寻优目标对某公司轮胎产品生产线上的作业排产问题进行求解,求解结果优于对比的算法,进一步验证所提算法在求解PFSP上的有效性。 展开更多

关键词 置换流水车间调度 蜂群算法 局部搜索 基准问题 最小化最大完工时间

下载PDF 职称材料

混合流水作业的排序问题

19

作者 廖礼琴 陈雪 张同全 《云南民族大学学报（自然科学版）》 CAS 2023年第3期334-339,共6页

研究了一类混合流水作业的排序问题,设置了2个处理中心,第1个处理中心含1台机器,第2个处理中心含m台机器.当作业在第2个处理中心加工时,需要多台机器同时加工.目标函数为最小化最大完工时间.讨论了3种情况,得到了以下结论:对于问题HF(1,... 研究了一类混合流水作业的排序问题,设置了2个处理中心,第1个处理中心含1台机器,第2个处理中心含m台机器.当作业在第2个处理中心加工时,需要多台机器同时加工.目标函数为最小化最大完工时间.讨论了3种情况,得到了以下结论:对于问题HF(1,P_(2))|M_(j)|C_(max)提出了3/2-近似算法,对于问题HF(1,P_(3))|M_(j)|C_(max),提出了3-近似算法,对于问题HF(1,P_(m))|M_(j)|C_(max),可以得到目标函数与最优解的比值为1+2 m. 展开更多

关键词 排序问题 最小化最大完工时间 近似算法

下载PDF 职称材料

禁止拖期交付的无等待流水车间调度问题算法研究

20

作者 宋存利 《大连交通大学学报》 CAS 2018年第6期100-105,共6页

在分析禁止拖期交付的无等待流水车间调度问题特征的基础上,建立了该问题的混合整数规划模型,提出了基于有向无环图的精确搜索算法ESA.该算法保证了对小规模问题的精确求解,而对稍有规模的问题,ESA算法效率较低,因此在ESA算法基础上又... 在分析禁止拖期交付的无等待流水车间调度问题特征的基础上,建立了该问题的混合整数规划模型,提出了基于有向无环图的精确搜索算法ESA.该算法保证了对小规模问题的精确求解,而对稍有规模的问题,ESA算法效率较低,因此在ESA算法基础上又提出了基于ESA的分段迭代搜索算法SISA-ESA,从而保证了算法能在较短时间内找出问题的较优解.最后进行了仿真实验,将此算法的运行结果与传统算法的运行结果进行比较,实验证明了所提出的算法的有效性和可行性. 展开更多

关键词 无等待流水车间 精确搜索算法 交货期 最小化完工时间

下载PDF 职称材料