文摘

流程序列时间选择性策略的综合调度算法(ISAOPSTSS)是一种先进的算法领域的综合调度。指出该算法流程的缺陷序列时间选择性策略。一般来说,有太多的“试验调度”。作者提出,没有需要在每一个“试验调度quasi-scheduling时间点。“事实上,进程调度方案可以通过试验安排在一些“quasi-scheduling时间点。“调度序列的结果是一样的,时间的策略。该算法减少了运行时的调度算法和改进算法的性能不降低优化效果。

1。介绍

调度是一个关键因素影响制造业的生产效率。有效的调度优化算法可以最大化生产效率在满足约束的前提下的企业订单,设备,和其他硬件和软件资源。目前,学者们做了很多研究在车间调度问题,和大多数主要分为加工车间调度问题(1- - - - - -10和流水车间11- - - - - -19]。这些算法主要为调度优化工件时,首先处理,然后组装成产品。目前,消费者对单个产品的需求越来越多,和制造工厂将面临越来越多的订单multivariety和小批量产品。这种情况如果生产仍处于加工组装后根据传统的生产方式将产品内部分裂并行处理和装配关系,降低生产效率。为了寻求解决这一新的研究领域,Zhi-Qiang et al。20.)提出了一个集成的调度算法,同时促进产品的加工和组装,开发出一系列调度优化算法,并扩大了许多新的研究领域。

2。相关的研究

目前,通用集成调度领域的研究,主要进行以下的研究一直。

Zhi-Qiang et al。20.)首先指出关键路径过程中树的重要位置,强调过程的调度过程中垂直关系树最终的调度结果密切相关。杨et al。21]提出的策略层优先级,短时间内,长路径,动态调整,并指出增加并行进程和水平关系之间的关系在此过程中树可以使调度结果更好。杨et al。22]指出文献[20.)注意产品树结构的垂直结构,忽视了水平并行处理同一设备的过程;同时,指出文献[21)关注产品的水平结构树结构和考虑了垂直路径的基础上水平层。然而,强调战略水平和忽视垂直不符合垂直定向产品调度机制。调度计划与垂直和水平的主要因素的主要因素。算法的优点是:垂直和水平的基础上,进一步优化垂直调度,符合综合调度主要是垂直的。缺点如下:尽管动态关键路径的想法是用来解决问题的串行过程和并行过程推进的同时,算法的想法过于宏观,由于一些因素的限制,不可能考虑串行流程之间的紧张。

鑫et al。23)确定过程的调度顺序根据路径的长度根据调度算法在文献[20.),并形成平行的4个处理组间,导致更多的空闲时间。一个集成的调度算法提出了基于设备空闲事件驱动。根据文献[23),鑫et al。24)提出了进一步优化调度结果通过使用回滚策略调度流程长路径的父节点;优点如下:它会增加设备的利用率,最大化“设备忙”原则,减少了设备的空闲时间,使流程更紧凑。缺点是“装置事件”总是寻找过程在当前可调度的并行过程。从流程的角度来看,该算法可以被视为一种改进的“层第一”“叶对齐”下调度模式。该算法提高了并行性和处理等待时间之间的串行过程,而忽略了垂直调度优化调度结果的影响。

总之,目前的研究可以在产品优化的并行调度流程,但串行流程的调度优化需要改进,同时考虑并行性。上述研究的基础上,谢et al。25)提出了时间选择性集成调度算法考虑串行操作的密实度(ISAOPSTSS)。算法不仅继承了当前算法的优势,确保并行进程之间,还优化了密实度之间串行流程的基础上,进一步强调垂直优化的调度思想。它避免了以往算法的缺点,优化调度结果。然而,ISAOPSTSS决定调度方案的过程更为复杂,导致操作冗余。本文提出了一种改进的算法,它可以减少算法的执行时间,提高该算法的性能没有减少算法的优化效果。

3所示。问题描述和分析

综合调度问题是研究如何安排产品完成时间最小化的过程,当产品在组装的生产方式处理。其中,研究人员把每个过程作为一个整体的加工和组装,统称为处理。加工时间、加工设备,和每个进程的偏序产品注明的产品处理树。综合调度应当具备下列条件:(1)每个进程只能在一台机器上处理(2)机器每次只能处理一个过程(3)当且仅当所有的预处理过程的完成加工(或没有预处理),这个过程可以处理(4)一定的处理过程不能被打断(5)处理结束时间之间的差异最新完成的过程和处理开始时间最早的起动过程的总处理时间的产品

4所示。调度策略的分析和设计

4.1。分析改进过程序列时间选择性策略

如图1,相反的顺序流程树的产品提出了ISAOPSTSS分析如下:步骤1:过程序列的测序策略应用于排序过程根据生产过程产品a树如图2首先计算所有叶子节点的路径长度的过程,结果表明:A10: 10, A9: 16日,A5: 21日A8: 20, A11: 9。因此,A5所在路径上的所有节点被选中作为第一个过程序列,和这些过程被添加到队列的过程问_u。在这个时候,在队列的顺序流程问_uA1, A2, A3、A4和A5;同时,在流程树中删除这些过程产品答:在这个时候,处理产品树变成了多个子树组成的森林。接下来,这些子树的叶节点的路径长度计算,结果如下:A10: 9, A9: 1, A8: 20日和A11: 8。选择的路径上所有节点A8所在作为第一个过程序列,并将这些流程添加到队列的过程问_u,在队列的顺序流程问_uA1, A2, A3、A4、A5、A6, A7和A8,和这些流程在流程树中删除产品a .以此类推,进程的进程队列的顺序吗问_u对应于流程树的最终产品是A1, A2, A3、A4、A5、A6、A7, A8, A10, A11, A9,这个序列将被用作调度序列的过程。步骤2:时间最长的操作顺序队列问_u前面的操作形成初始调度方案,如图3。步骤3:使用改进的过程序列的测序策略安排剩下的流程过程中队列问_u反过来。首先,A6计划过程。最早开始A6的处理时间是1,和处理设备米3所示。因为A2和A5一直在安排米3设备。A6的“quasi-scheduling时间点”是最早开始加工时间1、过程的最终处理时间4 A2,和过程的最终处理时间21 A5。尽量安排A6在这三个时间点,并得到三个试验调度方案如图4。

在如图所示的A6“quasi-scheduling计划”4,ISAOPSTSS计算的总处理时间每个“quasi-process调度计划”在每个“quasi-scheduling时间点”,形成方案如图4所示(b)被选中作为A6的调度方案。计划最少的总处理时间的A6调度方案。

事实上,根据流程序列时间选择性算法的特点,不需要计算的总处理时间每个“quasi-process调度计划”形成“quasi-scheduling时间点。”

首先,当前的总处理时间基本的调度方案 ,和当前调度过程的处理时间 。当前进程的总处理时间调度是 。

根据公式(1),当前进程的总处理时间Pquasi-scheduling方案 ,最小的处理时间 ,最大加工时间是总处理时间的总和t当前基本的调度方案和处理时间t当前调度的过程。可以看出,如果使用“quasi-scheduling时间点”的顺序安排的流程由前往后如果quasi-process调度方案的总处理时间 ,它可以确定quasi-scheduling quasi-process调度计划的时间点是当前进程调度方案,和不需要计算的总处理时间quasi-process调度方案quasi-scheduling时间点后的时间点;当然,总处理时间“quasi-operation调度计划”产生的“quasi-scheduling时间点”等于总处理时间基本的调度方案;然而,由于这一事实“quasi-scheduling时间点”计划的顺序从前线回到试验调度过程中,这位前“quasi-scheduling时间点”比后者的总处理时间从进程间的角度相同密实度。

因此,当前的进程调度方案将在以下两种情况讨论:(1)如果“quasi-process调度计划”的总处理时间在当前“quasi-scheduling时间点”生成大于当前的基本调度方案,总处理时间生成的“quasi-process调度计划”在接下来的“quasi-scheduling时间点”将继续坚定。(2)如果总处理时间生成的“quasi-process调度计划”从目前的“quasi-scheduling时间点”的总处理时间等于当前基本的调度方案,计算背后的“quasi-scheduling时间点”将会停止,并从当前生成的“quasi-process调度计划”“quasi-scheduling时间点”将被视为当前进程调度方案。

4.2。算法改进的过程序列时间选择性调度策略的设计

改进算法的具体步骤如下:步骤1:设置的基本调度方案的过程P作为D。步骤2:在计划D,k“quasi-scheduling时间点”加工设备米过程的P被发现,他们排队QT,j= 1。第三步:判断QT队列是空的。如果不是空的,QTi队列上的队列的操作。取出“quasi-scheduling时间点”T然后转到步骤4。如果它是空的,步骤12。第四步:判断T加工设备的空闲时间吗米或一个过程的结束时间在scheme中d .如果不是,转到步骤5,如果是这样,步骤6。第五步:处理开始时间过程的时间点T(正在处理的过程在时间点T)的总和T和过程的处理时间。第六步:时间点T作为过程的处理时间开始P安排流程P。第七步:流程序列时间选择性调整策略25)是用来调整过程影响调度过程P,形成的jth quasi-process P调度方案。第八步:总处理时间的jth quasi-processP调度方案计算。第九步:判断 是真的。如果是的,去第十步;否则,转到步骤11。第十步:在时间点获得的调度方案T作为过程的调度方案吗P14日,去一步。步骤11:j+ +,转到步骤3。步骤12:的总处理时间jquasi-processP调度方案相比,该方案选择最小的总处理时间。13步:判断该计划是独一无二的。如果它是独一无二的,选择它。如果不是独特的,选择方案与最早的处理开始时间过程P。步骤14:退出。

过程的流程图如图序列时间选择性调度策略1。

5。算法设计

改进算法的实现步骤如下:步骤1:倒序处理树是通过扭转加工过程中加工的偏序关系树。步骤2:运行队列中问_u通过使用流程序列排序策略。步骤3:所有流程最长的工艺步骤问_u排队等待,将形成初始调度方案P₀。步骤4:我= 1。第五步:判断问_u是空的。如果它是空的,去第八步;否则,进入步骤6。第六步:队列问_u排队获取当前调度过程P;处理时间是t,加工设备米。第七步:改进后的工艺步骤时间选择性策略应用于时间表P,过程获得P调度方案;我+ +,转到步骤5。第八步:形成产品调度甘特图和输出。

6。实验方法

为了验证算法的性能,设计一组实验进行比较。算法的性能是影响生产过程的结构树,加工设备的数量,处理时间。因此,该算法相比于ISAOPSTSS算法从不同的尺度参数的角度。首先,每个实验将随机生成50个产品。过程中的参数树是随机生成的。参数如下:流程树的结构(包括流程的总层数树,过程中每一层的数量,和过程的前后关系),流程的处理时间和设备数量在这一过程中树,和过程的加工设备的总数。每组实验将随机生成50个产品,因为产品结构是随机的,它可以有效地在不同的情况下,证明了算法的有效性。实现上述两个算法的c++语言开发c++ 4.9.9.2。安排随机生成的生产过程的树木,设置计数器的两个算法来监测乘以每个算法的“试验调度”,并记录他们的比较。由于算法提出了一个改进的算法在ISAOPSTSS提出,如果“审判调度”的数量的算法提出了比ISAOPSTSS在不同的参数条件下,本文提出的算法的有效性可以证明的。

7所示。结果与讨论

六组实验设计如下。在实验1中,如图5与算法相比,该算法在ISAOPSTSS。为了比较,50个产品流程树是随机生成的,流程的总数是30,和加工设备的总数量是3,6和9。在实验2中,如图6与算法相比,该算法在ISAOPSTSS。比较用于随机生成50组数据,流程的总数是50,和加工设备的总数量是3,6和9。在实验3中,如图7与算法相比,该算法在ISAOPSTSS。比较用于随机生成50组数据,流程的总数是80,和加工设备的总数量是3,6和9。在实验4,如图8与算法相比,该算法在ISAOPSTSS。比较用于随机生成50组数据,流程的总数是100,和加工设备的总数量是3,6和9。如图9、实验5显示了平均调度时间比较该算法和ISAOPSTSS算法的进程总数是30,50岁,80年和100年,分别。如图106、实验表明,在实验1中,当设备的总数量是3,6日和9日,分别平均算法的调度时间相比ISAOPSTSS。

上述实验数据的分析表明,算法的试验调度次数本文相比显著降低ISAOPSTSS试点计划的数量,并减少比率约为30%。

8。结论

本文提出的算法是一个时间序列算法的进一步优化操作。在保证优化结果的前提下,简化了算法步骤,减少了算法执行时间,提高了算法的性能。目前,ISAOPSTSS算法已经应用于批处理调度和two-job-shop调度等领域。它可能是下一步将该算法应用在这些领域来提高算法的性能。

数据可用性

没有数据被用来支持本研究。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

本研究由广东省教育委员会的项目(批准号2019 ktscx177),广东省科技计划项目(批准号2020 a1414010235),徽州的科技计划项目(批准号2020 sc0306023),惠州大学的教授和博士科研基金(批准号2019 jb014和2018 jb007)。