并行分批排序问题综述 被引量：13

1

作者 张玉忠 曹志刚 《数学进展》 CSCD 北大核心 2008年第4期392-408,共17页

并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序... 并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序问题的最新进展作了全面的介绍,指出了许多尚未解决的问题和许多新的研究方向,给出了丰富的参考文献,旨在把感兴趣的读者迅速带到此研究领域的前沿. 展开更多

关键词 并行分批排序 NP-困难 近似算法

下载PDF 职称材料

同类机环境下不同尺寸工件的分批调度问题 被引量：9

2

作者 李小林 杜冰 +1 位作者 许瑞 陈华平 《计算机集成制造系统》 EI CSCD 北大核心 2012年第1期102-110,共9页

为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。由于该问题是NP难解的,给出了一个下界以衡量近似算法的性能,并证明了该下界的有效性。提出了批的隐性加工时间的概念,... 为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。由于该问题是NP难解的,给出了一个下界以衡量近似算法的性能,并证明了该下界的有效性。提出了批的隐性加工时间的概念,并以此为基础给出了一种新的局部优化算法,对最大最小蚁群算法进行了改进。使用启发式算法最终对同类机环境下分批调度问题进行求解。通过仿真实验将该蚁群算法与遗传算法、微粒群优化算法及BFLPT等进行比较和性能分析。 展开更多

关键词 同类机 批调度 蚁群优化算法 组合优化 启发式算法

下载PDF 职称材料

考虑能耗约束的并行机组批调度 被引量：7

3

作者 李国臣 乔非 +2 位作者 王俊凯 马玉敏 卢凯璐 《中南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2017年第8期2063-2072,共10页

研究并行批处理机的组批调度问题,考虑炉容相同、功率不同的非等同并行机的总能耗约束,考虑工件尺寸和到达时间不同,以最小化最大完工时间为目标建立混合整数规划模型。并行机组批调度问题属于NP-hard问题,采用先组批后调度的两阶段方... 研究并行批处理机的组批调度问题,考虑炉容相同、功率不同的非等同并行机的总能耗约束,考虑工件尺寸和到达时间不同,以最小化最大完工时间为目标建立混合整数规划模型。并行机组批调度问题属于NP-hard问题,采用先组批后调度的两阶段方式求解。组批阶段采用基于FFLPT和BFLPT的启发式规则,调度阶段设计带邻域搜索的粒子群-遗传混合算法对模型进行求解。以轧辊生产企业并行热处理设备为研究案例进行模型和算法验证,分析不同能耗约束下最大完工时间优化值,并比较算法的优化性能。实验结果表明:本文算法提高标准遗传算法的收敛速度,且优于2种启发式算法;能耗与最大完工时间之间存在冲突关系,通过本文的模型和算法得到能耗与最大完工时间的近似Pareto前沿面,可为企业的实际生产提供指导。 展开更多

关键词 并行机 组批调度 能耗约束 最大完工时间 粒子群-遗传算法 邻域搜索

下载PDF 职称材料

染缸排产建模及滑动时间窗启发式调度算法 被引量：3

4

作者 隗千千 董兴业 王焕政 《计算机应用》 CSCD 北大核心 2020年第1期292-298,共7页

针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度(STWS)算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为... 针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度(STWS)算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。 展开更多

关键词 染缸排产 启发式算法 增量调度模型 异构并行机 批处理调度

下载PDF 职称材料

考虑工序并行的差异工件批调度研究 被引量：4

5

作者 唐红涛 杨志鹏 刘家毅 《工业工程》 北大核心 2021年第3期68-76,114,共10页

针对铸造车间差异工件组批多约束的问题,在工序可并行加工的前提下构建以最小化最大完工时间和最小化沙箱空置率为优化目标的并行工序批调度模型,设计一种改进和声算法求解该调度模型,提出一种单工序编解码方式和2种机器分配规则用于解... 针对铸造车间差异工件组批多约束的问题,在工序可并行加工的前提下构建以最小化最大完工时间和最小化沙箱空置率为优化目标的并行工序批调度模型,设计一种改进和声算法求解该调度模型,提出一种单工序编解码方式和2种机器分配规则用于解决工件分批、沙箱选择、工序分配及机器选择的问题。在算法中提出一种新的和声产生方式和更新机制,同时为改善算法的局部搜索能力,加入模拟退火算法执行局部搜索过程。最后根据企业实际生产数据进行仿真实验,验证本文模型的有效性。 展开更多

关键词 工序并行 批调度 多约束 和声搜索算法

下载PDF 职称材料

一类具有三重指标的分批排序问题 被引量：3

6

作者 李文华 《工程数学学报》 CSCD 北大核心 2007年第1期183-186,共4页

本文研究现代排序问题一具有三重指标的批容量无限制平行分批排序问题。第一指标为最大延迟,第二指标为最大完工时间,第三指标为关于工件完工时间的任意正规函数。本文通过分析前两个指标最优解的性质给出了此问题的多项式时间算法。

关键词 平行分批排序 最大延迟 最大完工时间 三重指标 动态规划

下载PDF 职称材料

基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究 被引量：2

7

作者 柳龙华 陈晶晶 +3 位作者 姜秀梅 陈桥 武斌功 管在林 《工业工程与管理》 CSCD 北大核心 2023年第1期59-66,共8页

在多品种混流生产车间里,广泛存在着各种批量的任务在多台并行机上调度优化问题。这种并行机批量调度需要考虑批量大小设置、加工顺序优化、设备充分利用等多种要素,是一类典型NP-hard问题,且当任务加工完后还需要考虑转运过程时,问题... 在多品种混流生产车间里,广泛存在着各种批量的任务在多台并行机上调度优化问题。这种并行机批量调度需要考虑批量大小设置、加工顺序优化、设备充分利用等多种要素,是一类典型NP-hard问题,且当任务加工完后还需要考虑转运过程时,问题将变得更加复杂。为了减少并行机生产过程中任务拖期和在制品积压,寻求更好的生产调度方案,针对典型并行机生产和转运场景,以最小化加权完工时间及拖期工件的惩罚费用、作业切换成本、库存成本之和为优化目标,设计了基于启发式规则的仿真程序与遗传禁忌算法相结合的优化算法,研究单工序不相关并行机调度环境下车间批量调度的最优调度方案,再通过案例验证了本文优化算法的有效性。结果表明,优化算法得出的并行机批量调度方案使得作业切换次数和拖期订单大大减少,减少在制品库存的同时提高了转运资源的利用率。 展开更多

关键词 并行机调度 转运约束 批量调度 仿真程序 遗传禁忌算法

原文传递

改进粒子群算法的不相关并行批处理调度优化 被引量：2

8

作者 杜利珍 叶涛 +2 位作者 王宇豪 张亚军 宣自风 《系统仿真学报》 CAS CSCD 北大核心 2023年第7期1549-1561,共13页

针对粒子群优化(particle swarm optimization,PSO)算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题,提出了一种改进PSO的调度优化算法,用于最小化最大完工时间求解。采用基于工件序列的实数编码方式... 针对粒子群优化(particle swarm optimization,PSO)算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题,提出了一种改进PSO的调度优化算法,用于最小化最大完工时间求解。采用基于工件序列的实数编码方式进行编码操作;基于该问题的混合整数规划模型,设计了一种J_B局部搜索的新策略;将模拟退火算法的Metropolis准则引入种群粒子的个体极值搜索。通过随机生成的小型、中型和大型实例对该算法的性能进行了测试,并与针对该调度问题提出的元启发式算法和其他3种元启发式算法进行了比较。实验结果和统计测试表明,该算法的性能明显优于对比算法。 展开更多

关键词 不相关并行 批调度 局部搜索策略 粒子群算法 模拟退火

下载PDF 职称材料

工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法 被引量：3

9

作者 刘晓霞 余山杉 罗文昌 《运筹学学报》 北大核心 2020年第1期131-139,共9页

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一... 考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案. 展开更多

关键词 平行分批排序 拒绝 动态规划 近似算法

下载PDF 职称材料

并行多机批调度的混合粒子群算法研究 被引量：2

10

作者 常俊林 王庆 +1 位作者 孟彦军 蒋晓剑 《化工自动化及仪表》 CAS 2014年第4期397-401,454,共6页

针对调度目标为最小化最大完工时间的并行多机批调度问题,提出了改进的基于批序列编码的混合粒子群算法。在基本粒子群算法的基础上,引入了学习因子二阶振荡、随机权重、最大速度线性递减及自然选择等方法,改善了算法本身易陷入局部最... 针对调度目标为最小化最大完工时间的并行多机批调度问题,提出了改进的基于批序列编码的混合粒子群算法。在基本粒子群算法的基础上,引入了学习因子二阶振荡、随机权重、最大速度线性递减及自然选择等方法,改善了算法本身易陷入局部最优及早熟收敛等问题,并解决了因引入新的方法造成算法收敛速度慢及寻优能力差等问题。由仿真结果可知:改进的算法均优于常规的粒子群算法,且根据批序列编码的改进算法更优于常规基于工件序列编码的改进算法。 展开更多

关键词 粒子群算法 并行机 批调度 最大完工时间

下载PDF 职称材料

面向两客户的差异工件平行机批调度问题 被引量：1

11

作者 谭琦 陈华平 +1 位作者 张松 李小林 《系统工程学报》 CSCD 北大核心 2013年第4期543-553,共11页

将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序... 将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序并安排到平行机,然后设计了一个多目标蚁群优化算法MOACO(multi-objective ant colony optimization)对不同客户中的工件进行分批并结合TSEDD完成对问题Pareto最优解集的求解.实验结果表明,与经典的多目标问题求解算法NSGA-Ⅱ和SPEA2算法相比,MOACO具有较好的求解效果,且随着问题中工件规模的增大,算法的优势更加明显. 展开更多

关键词 两客户 平行机 批调度 差异工件 多目标蚁群优化算法

下载PDF 职称材料

并行分批排序综述 被引量：2

12

作者 井彩霞 吴瑞强 贾兆红 《运筹与管理》 CSSCI CSCD 北大核心 2020年第1期223-239,共17页

并行分批排序起源于半导体芯片制造过程.在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时.首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机... 并行分批排序起源于半导体芯片制造过程.在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时.首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向. 展开更多

关键词 并行分批排序 时间复杂性 启发式算法 智能算法 近似算法 综述

下载PDF 职称材料

无关机上极小化求和问题的平行分批排序(英文) 被引量：1

13

作者 苗翠霞 张玉忠 王成飞 《运筹学学报》 CSCD 2010年第4期11-20,共10页

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨... 本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法. 展开更多

关键词 运筹学 平行分批排序 无关机 拒绝费用 拟多项式时间算法

下载PDF 职称材料

p与d一致时的分族分批排序误工个数问题

14

作者 曹国梅 《河南科学》 2009年第7期775-778,共4页

研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的.对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O(mb(nm)2m)的动态规划算法.

关键词 平行批排序 分族分批 P与d相一致 误工个数 动态规划

下载PDF 职称材料

一类无界的不相容工件族分批排序加权总完工时间问题 被引量：1

15

作者 曹国梅 《常熟理工学院学报》 2009年第4期22-24,共3页

考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明.对工件有k个到达时间的情形,给出了一个复杂性为O(2^(k-1)nlogn)的启发式算法.

关键词 平行批排序 不相容工件族分批排序 加权总完工时间 启发式算法.

下载PDF 职称材料

加工时间相同的分族分批排序加权总完工时间问题

16

作者 曹国梅 石忠和 《安阳工学院学报》 2009年第4期99-101,共3页

考虑极小化加权总完工时间的单机分族分批排序问题,给出了最优排序的性质和算法,并加以证明,对工件有k个到达时间的情形,给出了一个复杂性为的启发式算法。

关键词 排序 平行批排序 分族排序 加权总完工时间 算法

下载PDF 职称材料

一种求解并行多机间歇调度问题的自适应EDA算法

17

作者 李作成 钱斌 +2 位作者 胡蓉 历莉 车国霖 《计算机与应用化学》 CAS CSCD 北大核心 2013年第7期743-747,共5页

针对广泛存在于化工生产过程中的并行多机间歇调度问题,提出了一种自适应分布估计算法,用于最小化最早完工时间(makespan)。首先,提出了一种具有自适应学习能力的改进策略,该策略根据当前解的改善状况自适应调节学习速率,有效克服了EDA... 针对广泛存在于化工生产过程中的并行多机间歇调度问题,提出了一种自适应分布估计算法,用于最小化最早完工时间(makespan)。首先,提出了一种具有自适应学习能力的改进策略,该策略根据当前解的改善状况自适应调节学习速率,有效克服了EDA对学习速率较敏感和依赖的不足,进而使得算法的搜索宽度和深度得到合理平衡;其次,设计了一种基于双精英个体的协同进化策略,该策略通过双概率模型协同进化,使算法能充分利用优秀个体的信息来指导搜索方向。仿真实验和算法比较验证了AEDA的有效性和鲁棒性。 展开更多

关键词 分布估计算法 并行多机 间歇调度 协同进化 自适应调节

原文传递

多目标启发式狼群算法求解不相关并行机分批调度问题 被引量：4

18

作者 荀洪凯 陶翼飞 +1 位作者 张源 何李 《信息与控制》 CSCD 北大核心 2023年第1期93-103,114,共12页

针对考虑机器加工约束的不相关并行机分批调度问题,以工件种类切换次数和机器启停评价函数为优化目标,提出一种多目标启发式狼群算法进行求解。该算法在生成初始种群的过程中,融入列表反向学习和基于机器加工效率的启发式策略,并设计了... 针对考虑机器加工约束的不相关并行机分批调度问题,以工件种类切换次数和机器启停评价函数为优化目标,提出一种多目标启发式狼群算法进行求解。该算法在生成初始种群的过程中,融入列表反向学习和基于机器加工效率的启发式策略,并设计了一种不规则实数矩阵编码方式来实现任务分批。采用局部和全局邻域搜索相结合的方式实现狼群算法中智能行为搜索,通过分批调整学习机制对当前结果进行邻域搜索,利用改进整数解Pareto非支配排序方式循环迭代。最后通过不同规模实际算例测试和相关算法比较,验证了该算法的有效性和优越性。 展开更多

关键词 并行机分批调度 多目标启发式狼群算法 工件种类切换次数 启停评价函数 列表反向学习策略 分批调整学习机制

原文传递

平顺移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度 被引量：2

19

作者 孔继利 苑春荟 +1 位作者 杨福兴 贾国柱 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2017年第11期2882-2896,共15页

对平行顺序移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度问题展开研究.构建以加工制造设备总停机次数、批量工件生产周期以及搬运批量工件的总次数为决策目标的基于分层序列法的多目标决策模型,利用该模型可确定批... 对平行顺序移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度问题展开研究.构建以加工制造设备总停机次数、批量工件生产周期以及搬运批量工件的总次数为决策目标的基于分层序列法的多目标决策模型,利用该模型可确定批量工件的最优加工排序方案.建立平行顺序移动模式的加工与调整时间模型,该模型是求解生产周期的基础,也是为批量工件的最优调度方案制定生产作业计划的依据.提出并设计平行顺序移动模式下考虑加工时间与调整时间可分离的禁忌搜索算法对问题进行求解.研究结果表明:本研究可为平顺移动模式下考虑加工时间与调整时间可分离的批量生产流水车间选出批量工件的最优调度方案,同时可为批量工件的加工和加工制造设备的调整制定精确的生产作业计划. 展开更多

关键词 平行顺序移动模式 调整时间 流水车间批量调度 多目标决策模型 禁忌搜索算法

原文传递

单机分族分批排序的最小误工个数问题 被引量：1

20

作者 曹国梅 《四川理工学院学报（自然科学版）》 CAS 2008年第5期19-21,共3页

文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。

关键词 排序 平行批分族排序 误工工件个数 动态规划

下载PDF 职称材料