Loading [MathJax]/extensions/TeX/boldsymbol.js

考虑柔性设备加工能力的综合调度算法

周伟, 丁雪莹, 谢志强

周伟, 丁雪莹, 谢志强. 考虑柔性设备加工能力的综合调度算法[J]. 华南师范大学学报(自然科学版), 2024, 56(2): 110-118. DOI: 10.6054/j.jscnun.2024029
引用本文: 周伟, 丁雪莹, 谢志强. 考虑柔性设备加工能力的综合调度算法[J]. 华南师范大学学报(自然科学版), 2024, 56(2): 110-118. DOI: 10.6054/j.jscnun.2024029
ZHOU Wei, DING Xueying, XIE Zhiqiang. An Integrated Scheduling Algorithm Considering the Processing Capacity of Flexible Equipment[J]. Journal of South China Normal University (Natural Science Edition), 2024, 56(2): 110-118. DOI: 10.6054/j.jscnun.2024029
Citation: ZHOU Wei, DING Xueying, XIE Zhiqiang. An Integrated Scheduling Algorithm Considering the Processing Capacity of Flexible Equipment[J]. Journal of South China Normal University (Natural Science Edition), 2024, 56(2): 110-118. DOI: 10.6054/j.jscnun.2024029

考虑柔性设备加工能力的综合调度算法

基金项目: 

国家自然科学基金项目 61772160

国家级大学生创新创业项目 202310203003

吉林师范大学博士项目 2022014

详细信息
    通讯作者:

    谢志强, Email: xiezhiqiang@hrbust.edu.cn

  • 中图分类号: TP301.6

An Integrated Scheduling Algorithm Considering the Processing Capacity of Flexible Equipment

  • 摘要:

    现有柔性综合调度研究中,没有考虑设备系统的协同加工能力,从而降低了设备系统高密加工和快速加工能力。针对此问题,文章将柔性设备可进行加工的工序数作为优化对象、以竞争资源较为紧张的设备资源为优化要素,提出了考虑柔性设备加工能力的综合调度算法(ISA-CPCFE):首先,采用优先调度层级较高与加工时长较短的工序的策略,提高了工序并行调度的力度;其次,提出一种最小化调度标尺与动态调整柔性设备优先级的策略,进一步提高了设备紧凑调度的力度。最后,将ISA-CPCFE算法与基于剪枝分层、基于设备驱动、基于实际路径、基于逆序层优先的算法进行对比实验。结果表明:ISA-CPCFE算法实现了复杂产品加工时间更短、柔性设备系统整体利用率更高的优化目标,调度效果更优。

    Abstract:

    In the existing research on flexible integrated scheduling, the lack of consideration for the collaborative processing capability of equipment systems reduces their high-density and rapid processing capabilities. In response to this issue, the number of processes that can be processed by flexible equipment is taken as the optimization object and the equipment resources with tight competition resources are taken as the optimization element, and proposes an integrated scheduling algorithm (ISA-CPCFE) that considers the processing capacity of flexible equipment. Firstly, the strategy of prioritizing processes with higher levels and shorter processing times is adopted to improve the parallel scheduling of processes. Secondly, a strategy is proposed to minimize the scheduling scale and dynamically adjust the priority of flexible equipment, further enhancing the intensity of compact equipment scheduling. Finally, a comparative experiment was conducted between the ISA-CPCFE algorithm and algorithms based on pru-ning layering, device driven, actual path, and reverse order layer priority. The results show that the ISA-CPCFE algorithm achieves the optimization goals of shorter processing time for complex products and higher overall utilization of flexible equipment systems, with better scheduling effects.

  • 随着人们生活水平的不断提高,兼具个性化和约束结构的复杂产品的需求日益突出,传统的生产制造模式已经不能完全适应更加多元化复杂产品的加工制造要求,生产制造中的柔性调度问题已经成为亟待解决的一类NP-hard问题[1]

    为了能够更好地解决此类产品生产制造的需求,众多学者从柔性生产调度的扰动性、灵活性、双柔性和群智性等方面进行了深入的研究[2-12]。例如,针对具有树型结构复杂产品的生产制造需求,谢志强[13]提出了将加工和装配协同处理的综合调度模式。

    现代柔性制造系统中,设备系统的特征和加工能力具有多样性,而工序又可以选择不同的加工设备,如何利用柔性设备的高密加工和快速加工的特征来减少设备约束、提高设备系统整体利用率已成为柔性综合调度系统的研究热点。目前,关于柔性综合调度的研究,多采用启发式算法和智能算法。在启发式柔性调度算法中,代表性算法有基于剪枝分层的算法(ISA-BPL)[14]、基于设备驱动的算法(ISA-BDD)[15]、基于实质路径的算法(ISA-BDDEP)[16]、基于逆序层优先的算法(ISA-BROLP)[17]、考虑根子树纵横预调度的算法[18]和工艺树子树循环分解的算法[19],然而,这些算法都是从设备匹配工序的角度来提高设备利用率,忽视了柔性设备整体利用率的问题。在具有代表性的智能优化柔性调度算法(如遗传算法、蚁群算法和混合粒子群算法)中,由于树型结构产品的工件之间具有严格的约束关系,所以,在初始解的可行性、最优解的遗漏性、调度算法的编码方式和进化算子的时效性等方面存在应用受限的问题。例如,综合运用邻域搜索和混合遗传算法的算法[20]中的每个解的染色体由机器序号和工序序号组成,减低了工序并行处理的力度;基于网络设备协作的算法[21]缩小了最优解的范围。又如,考虑工序优先级及工序间约束关系的编码策略[22]无法保证初始种群个体的完备性;考虑设备优化方向的策略[23]降低了工序紧密加工的力度;以灰狼的狩猎过程作为离散灰狼更新算子的改进灰狼算法[24]无法体现工件之间内在的约束关系。

    针对现有柔性综合调度算法中存在的忽略设备协同加工的高密性和快速性的问题,本文以设备序列整体利用率为研究角度,以树型结构产品生产调度总用时的更优解为优化目标,提出了考虑柔性设备加工能力的综合调度算法(ISA-CPCFE)。本文的主要贡献有:

    (1) 在柔性综合调度中,以对应加工工序的数量之和作为设备加工能力的定义标准,提出了动态调整设备优先级的策略。

    (2) 关于调度算法,采用层级降序和加工用时升序的策略;关于分配算法,采用调度标尺策略和对设备优先级进行动态调整的策略。

    (3) 在横向的优化效果:以树型产品结构属性中的层级关系为研究角度,有效提高了工序并行加工的力度;在纵向的优化效果:以制造系统设备序列的优先级为研究角度,有效提高了工序在设备上紧凑加工的力度。

    柔性调度系统的一个显著特征是设备加工能力不唯一,使得加工工序和设备之间产生了一对多的可选性与加工时间的差异性。因而柔性设备加工能力的综合调度研究焦点主要体现在如何更加合理地协同处理工序间的加工约束和分配问题。

    具体要求如下:

    (1) 每个工序具有唯一序号标识且可对应多个加工设备,加工设备也具有唯一序号标识;

    (2) 同一工序对应不同设备的加工用时不一定相同;

    (3) 工序选定设备后,加工过程中具有加工时间的确定性和连续性;

    (4) 每一道工序能够开始加工的充要条件是其已经不具备前序约束的制约;

    (5) 所有工序全部加工结束的时间即为产品的生产调度总用时。

    以树型结构表示产品工序调度顺序和约束特征,在树型产品中工序用A代表,工序序列为A={Ai} (1≤in);设备用M代表,设备序列为M={Mj} (1≤jm);在前提为满足工件间的约束关系时,不同产品的初始调度时刻不受限。本文的目标函数,即优化复杂产品生产调度的总用时为:

    min(max(TSAiMj+TAiMj))(1in,1jm), s.t. {TSAi+1MjTEAiMk0(1km,1jm),TSAuMjTEAvMj0(1u<vn),TAiMj=xij(TEAiMjTSAiMj),

    其中:AiMj表示工序Ai在设备Mj上加工,TAiMj表示工序Ai在设备Mj的加工时间,TAiMjS表示工序Ai在设备Mj的开始加工时间,TAiMjE表示工序Ai在设备Mj的完工时间;工序Ai是否在设备Mj上加工的判断系数为xij∈{0, 1},xij=1表示工序Ai在设备Mj上加工,xij=0表示工序Ai无法在设备Mj上加工;第1个约束条件为紧前、紧后工序加工时的约束条件;第2个约束条件为工序Au和Av在相同设备Mj上对应的加工约束条件。

    定义1[25]  (层优先级)对于具有n层结构的树型产品,从根节点工序开始, 自上而下地将各层工序的层级依次定义为1, 2, …, n。规定:层级为1的根节点工序的层优先级最低,为1;层级为2的根节点工序的紧后工序的层优先级为2;以此类推、逐层升级,第n层上的工序的层优先级最高,为n

    定义2[26]  (设备优先级)将设备资源M={M1, M2, …, Mm}中各台设备对应的加工工序数量之和作为此设备是否优先加工的标准,即定义加工工序数量最少的设备优先加工的级别(即设备优先级)最低,为第1级;加工工序数量次多的设备优先级为2;以此类推,设备优先级随着其对应的加工工序数量的增多而升高,加工工序数量最多的设备优先级最高,允许存在相同的设备优先级。

    定义3  (调度标尺)将工序Ai在设备Mj上加工结束需用的时间定义为设备资源系统的调度标尺,记为SRAiMj

    定义4  (调度系统矩阵)调度系统矩阵定义为:

    \boldsymbol{R}=\left[\begin{array}{cccc} T_{\mathrm{A}_{1} \mathrm{M}_{1}} & T_{\mathrm{A}_{1} \mathrm{M}_{2}} & \cdots & T_{\mathrm{A}_{1} \mathrm{M}_{m}} \\ T_{\mathrm{A}_{2} \mathrm{M}_{1}} & T_{\mathrm{A}_{2} \mathrm{M}_{2}} & \cdots & T_{\mathrm{A}_{2} \mathrm{M}_{m}} \\ \cdots & \cdots & & \cdots \\ T_{\mathrm{A}_{n} \mathrm{M}_{1}} & T_{\mathrm{A}_{n} \mathrm{M}_{2}} & \cdots & T_{\mathrm{A}_{n} \mathrm{M}_{m}} \end{array}\right],

    其中,TAiMj表示在设备Mj上加工工序Ai的用时。

    与其他柔性综合调度算法不同,本文以加工工序数量较多、竞争资源相对紧张的设备为优化因素,结合产品工艺树中层序的约束关系,从实现设备加工的高密性和快速性的角度优化了柔性综合调度的整体调度效果。

    以层级为调度的优先级策略,一方面可以提高工序并行效率;另一方面,对约束性较强的前序工序优先进行调度,可以带动对其紧后工序的加工,从而实现设备加工的高密性。本文的核心策略是优先级策略,使柔性资源协同综合调度的设备整体利用率得到提升。本文的调整策略采用调度标尺策略,通过最小化调度标尺的策略,可以实现复杂产品加工的快速性,进一步提高工序紧凑加工力度。

    ISA-CPCFE算法的流程图见图 1,具体步骤详细表述如下:

    图  1  ISA-CPCFE算法的流程图
    Figure  1.  Flowchart of the ISA-CPCFE algorithm

    Step 1:建立柔性调度系统的工序设备矩阵R,计算在工序与设备一对多关系的情况下,各个工序的不同加工时间。

    Step 2:计算设备序列中各个设备的优先级。

    Step 3:初始SRAiMj=0。

    Step 4:判断当前层优先级最高的工序是否唯一:如果唯一,则调度并转Step 8;否则转Step 5。

    Step 5:判断工序设备矩阵R中,层级相同的工序加工完毕时间是否最少:如果最少,则调度并转Step 8;否则转Step 6。

    Step 6:以最小化SRAiMj为标准,通过工序设备矩阵R来确定符合条件的工序:如果SRAiMj值相同,则按照设备优先级降序调度符合条件的工序。

    Step 7:从工序设备矩阵R中删除已经调度完毕的工序和设备的加工数据,更新矩阵R、设备优先级和SRAiMj

    Step 8:层优先级递减。

    Step 9:判断所有工序是否调度完毕:如果调度完毕,则转Step 10;否则转Step 4。

    Step 10:调度结束,退出。

    在柔性调度系统中,建立工序设备矩阵R的时间复杂度为O(n2)、计算和调整设备优先级的时间复杂度为O(n);对于工艺树结构,无论其结构是否复杂,计算其工序层优先级的时间复杂度均为O(n);计算调度标尺时,因为需要遍历所有设备对调度标尺进行比对,所以时间复杂度为O(n2)。综上,ISA-CPCFE算法的时间复杂度为max(O(n), O(n2))=O(n2)。

    现以图 2所示的复杂产品A为例进行调度实例说明,共包含了21道加工工序,每道工序包含的信息分别为工序序号、工序加工所在设备和在每个设备上加工所用工时,中间用“/”分隔。

    图  2  加工工艺图
    Figure  2.  Processing process diagram

    具体步骤如下:

    Step 1:如表 1所示,建立工序在柔性设备上的加工用时表,初始时设备M4对应18道工序,其余设备均对应14道工序,由此可得M4的设备优先级为2,M1、M2、M3的设备优先级均为1。复杂产品A的工艺树共有6层,工序A21和A20位于第6层,所以工序A21和A20的层优先级最高。

    表  1  工序在柔性设备上的加工用时
    Table  1.  The processing time of process on flexible equipment 工时
    工序 设备
    M1 M2 M3 M4
    A1 20 25 15
    A2 20 15 25
    A3 15 20 25
    A4 20 20
    A5 20 20 15
    A6 20 15 25
    A7 20 40
    A8 15 20
    A9 25 25 30 25
    A10 20 20 45
    A11 25 20 20
    A12 10 15 25
    A13 15 15 35
    A14 15 20 40
    A15 30 30
    A16 30 15 20
    A17 15 20 25
    A18 20 20 20
    A19 20 25 25 35
    A20 15 20 35
    A21 10 15
    注:“—”表示无法在此设备上调度该工序。
    下载: 导出CSV 
    | 显示表格

    Step 2:层优先级最高的工序有2个:A21、A20,不唯一,而由工序在柔性设备上的加工用时(表 1)可知工序A20在设备上最少的加工用时为TA20M1=15、工序A21在设备上最少的加工用时为TA21M1=10,故优先在设备M1上调度工序A21。工序A21调度完毕后,依据min(SRA20M1,SRA20M2,SRA20M3)=min(25,20,35)=20的标准,在设备M2上调度工序A20。第6层的工序的调度顺序为:A21/M1/10、A20/M2/20。

    Step 3:删除已经调度的工序A20和A21,更新设备优先级。此时设备M4仍然加工18道工序,设备M3还需要加工14道工序,设备M1和设备M2还均需加工13道工序,所以M4的设备优先级为3, M3的设备优先级为2, M1、M2的设备优先级为1;更新SRA21M1=10、SRA20M2=15。

    Step 4:第5层的工序总共有5道,分别是A15、A16、A17、A18和A19,不唯一。其中加工用时最少的工序为A16和A17,为15工时,但是M3的设备优先级高于M1,所以先在设备M3上调度A16,然后根据最小化调度标尺的原则依次调度工序A18、A17。工序A15在设备M4和设备M2上具有相同的调度标尺,但是设备M4的优先级较高,所以选择在设备M4上调度工序A15。因此,第5层的工序的调度顺序为:A16/M3/15、A18/M4/20、A17/M1/15、A19/M3/25、A15/M4/20。

    Step 5:按照设备优先级和最小化调度标尺原则,第4层至第2层的工序的调度序列为:{A12/M1/10,A9/M2/25,A13/M1/15,A11/M4/20,A10/M3/20,A14/M1/15},{A7/M2/20,A5/M4/15,A6/M3/15,A8/M2/15},{A2/M1/20,A3/M3/20,A4/M4/20}。如图 3所示,ISA-CPCFE算法的调度总用时为120工时。动态调整设备优先级的过程如表 2所示。

    图  3  ISA-CPCFE算法的调度结果甘特图
    Figure  3.  Gantt chart of scheduling results of ISA-CPCFE algorithm
    表  2  动态调整设备优先级的过程
    Table  2.  The process of dynamically adjusting device priorities
    层级(降序) 设备加工工序数量/道 设备优先级(降序)
    M1 M2 M3 M4
    6 14 14 14 18 M4∶2,M1、M2、M3∶1
    5 13 13 14 18 M4∶3,M3∶2,M1、M2∶1
    4 12 13 12 16 M4∶3,M2∶2,M1、M3∶1
    3 9 11 11 16 M4∶3,M2、M3∶2,M1∶1
    2 9 9 10 15 M4∶3,M3∶2,M1、M2∶1
    1 8 9 9 14 M4∶3,M2、M3∶2,M1∶1
    下载: 导出CSV 
    | 显示表格

    图 1所示的复杂产品A为例,将ISA-CPCFE算法与相同研究领域中的基于剪枝分层的算法(ISA-BPL)[15]、基于设备驱动的算法(ISA-BDD)[16]、基于实质路径的算法(ISA-BDDEP)[17]、基于逆序层优先的算法(ISA-BROLP)[18]进行对比实验。

    (1) 基于剪枝分层的算法(ISA-BPL)。该算法采用了剪枝分层法设计简化工艺流程,依次采用工序-设备预分配策略、工序-设备预约策略、柔性加工策略和事件驱动策略为各加工类型制定不同的工序调度方案。

    (2) 基于设备驱动的算法(ISA-BDD)。该算法依次采用了冲突调解策略、设备驱动策略、动态实质短路径策略和短用时策略,解决了柔性调度中设备与工序互选冲突的问题。

    (3) 基于实质路径的算法(ISA-BDDEP)。该算法依次采用了并行优化分配策略、实质短路径策略和最早加工结束策略,调度分配在空闲设备驱动时刻可重叠加工的工序。

    (4) 基于逆序层优先的算法(ISA-BROLP)。该算法依次采用了逆序层优先、动态拟长路径策略、设备选择策略、设备抢占策略和基于完工时间翻转的调度方案转换策略,从根节点开始调度直至叶节点加工完毕结束。

    图 1所示复杂产品A为例,采用4种对比算法分别对复杂产品A进行调度。结果(图 4)显示:

    图  4  4种算法的调度结果甘特图
    Figure  4.  Gantt chart of the scheduling results of 4 algorithms

    (1) ISA-BPL算法调度复杂产品A的顺序集合为{A21/M1/10,A9/M2/25,A16/M3/15,A18/M4/20,A20/M1/15,A11/M3/20,A17/M1/15,A15/M2/30,A5/M4/15,A13/M3/15,A12/M1/10,A19/M1/20,A7/M2/20,A10 /M3/20,A14/M1/15,A3/M2/15,A6/M3/15,A8/M2/15,A2/M3/15,A4/M3/20,A1/M4/15},加工总用时为140工时。

    (2) ISA-BDD算法调度复杂产品A的顺序集合为{A20/M1/15,A21/M2/15,A16/M3/15,A18/M4/20,A19/M1/20,A15/M2/30,A11/M3/20,A9/M4/25,A17/M1/15,A13/M3/15,A14/M2/20,A5/M4/15,A12/M1/10,A10/M3/20,A7/M4/40,A8/M2/15,A6/M1/20,A4/M3/20,A2/M1/20,A3/M2/15,A1/M1/20},加工总用时为135工时。

    (3) ISA-BDDEP算法调度复杂产品A的顺序集合为{A20/M1/15,A21/M2/15,A18/M3/20,A16/M4/20,A17/M1/15,A15/M2/30,A13/M3/15,A11/M4/20,A19/M1/20,A9/M2/25,A10/M3/20,A14/M1/15,A12/M1/10,A8/M4/20,A6/M3/15,A5/M1/20,A7/M2/20,A4/M4/20,A2/M3/15,A3/M2/15,A1/M4/15},加工总用时为125工时。

    (4) ISA-BROLP算法调度复杂产品A的顺序集合为{A20/M1/15,A16/M3/15,A9/M4/25,A19/M1/20,A15/M2/30,A18/M3/20,A5/M4/15,A14/M1/15,A11/M3/20,A21/M2/15,A10/M4/45,A13/M3/15,A17/M1/15,A8/M2/15,A12/M1/10,A7/M2/20,A4/M3/20,A6/M4/25,A3/M2/15,A2/M3/15,A1/M4/15},加工总用时为145工时。

    由5种算法的设备整体利用率、加工总用时和设备加工空隙(表 3)可知:

    表  3  5种算法的加工总用时和设备系统整体利用率
    Table  3.  The total processing time and overall utilization rate of equipment system of 5 algorithms
    对比算法 复杂产品A的加工总用时/工时 设备系统空闲时间总和/工时 设备系统整体利用率/%
    ISA-BPL 140 95 80.0
    ISA-BDD 135 45 90.0
    ISA-BDDEP 125 50 87.3
    ISA-BROLP 145 80 83.3
    ISA-CPCFE 120 30 92.7
    下载: 导出CSV 
    | 显示表格

    (1) ISA-CPCFE算法的设备整体利用率达到了92.7%,与ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法相比,ISA-CPCFE算法的设备整体利用率分别提高了12.7%、2.7%、5.4%、9.4%。

    (2) ISA-CPCFE算法的加工总用时比ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法分别减少了20、15、5、25工时,减少率分别为14.3%、11.1%、4%、17.2%。

    (3) ISA-CPCFE算法的加工空隙共30工时,与ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法相比,分别减少了68.4%、33.3%、45.5%、62.5%。

    综上可知,与4种对比算法相比,ISA-CPCFE算法在解决柔性综合调度系统中调度效果更优,主要原因如下:

    (1) ISA-CPCFE算法采用了“层优先”的策略进行工序调度,并且根据工序矩阵,首选同层中加工用时较短的工序进行调度,这些都是综合调度横纵优化经典策略,有效地减少了并行工序的加工时间。根据ISA-CPCFE算法的调度结果,设备M2和设备M4上的所有工序实现了无缝衔接的高密排序调度,2台设备的利用率均达到了100%。而4种对比算法的策略都是以纵向优化为主的调度思想,拉长了工序在调度过程中的加工空隙。例如,在柔性设备系统中应用ISA-BPL算法后,从t=40时刻到t=125时刻,设备M4出现了共计85个工时的加工空隙。

    (2) ISA-CPCFE算法提出了最小化调度标尺和动态调整设备优先级的策略进行工序分配,是从柔性设备系统整体规划工序的分配问题,达到了设备上工序紧密加工的快速调度效果。例如,在ISA-CPCFE算法中设备优先级较高的M4上共加工6道工序,调度工序数量大于ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法。又如,柔性设备系统应用ISA-CPCFE算法后,在设备M1上的t=10时刻开始加工工序A17,开始加工时间比ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法分别提前了15、25、5、50工时。

    为了提高柔性设备的整理协同加工能力,本文提出了考虑柔性设备加工能力的综合调度算法(ISA-CPCFE),将柔性设备可加工工序数量作为优化对象,通过提高设备资源的整体利用率来实现复杂产品调度用时更少的优化目标。研究结果表明:

    (1) 本文提出的柔性设备优先级调度策略,通过减少设备的加工空隙,缩短了复杂产品的加工总用时。与ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法相比,ISA-CPCFE算法的加工总用时分别减少了14.3%、11.1%、4%、17.2%;

    (2) 本文提出的最小化调度标尺策略,通过紧凑调度工序,提高了柔性设备系统的整体利用率。与ISA-BPL、ISA-BDD、ISA-BDDEP、ISA-BROLP算法相比,ISA-CPCFE算法的设备整体利用率分别提高了12.7%、2.7%、5.4%、9.4%;

    (3) 本文综合运用“层优先+设备优先级优先+调度标尺最小化优先”的策略,实现了复杂产品纵横双向的优化效果,在相同研究领域中,实现了更佳的调度效果。

    ISA-CPCFE算法可为后续开展多产品的柔性综合调度、网络协同的综合调度、动态柔性综合调度等研究提供基础,后续可将该算法扩展到具有协同计算能力的复杂产品分布式制造调度系统的设计与实现。

  • 图  1   ISA-CPCFE算法的流程图

    Figure  1.   Flowchart of the ISA-CPCFE algorithm

    图  2   加工工艺图

    Figure  2.   Processing process diagram

    图  3   ISA-CPCFE算法的调度结果甘特图

    Figure  3.   Gantt chart of scheduling results of ISA-CPCFE algorithm

    图  4   4种算法的调度结果甘特图

    Figure  4.   Gantt chart of the scheduling results of 4 algorithms

    表  1   工序在柔性设备上的加工用时

    Table  1   The processing time of process on flexible equipment 工时

    工序 设备
    M1 M2 M3 M4
    A1 20 25 15
    A2 20 15 25
    A3 15 20 25
    A4 20 20
    A5 20 20 15
    A6 20 15 25
    A7 20 40
    A8 15 20
    A9 25 25 30 25
    A10 20 20 45
    A11 25 20 20
    A12 10 15 25
    A13 15 15 35
    A14 15 20 40
    A15 30 30
    A16 30 15 20
    A17 15 20 25
    A18 20 20 20
    A19 20 25 25 35
    A20 15 20 35
    A21 10 15
    注:“—”表示无法在此设备上调度该工序。
    下载: 导出CSV

    表  2   动态调整设备优先级的过程

    Table  2   The process of dynamically adjusting device priorities

    层级(降序) 设备加工工序数量/道 设备优先级(降序)
    M1 M2 M3 M4
    6 14 14 14 18 M4∶2,M1、M2、M3∶1
    5 13 13 14 18 M4∶3,M3∶2,M1、M2∶1
    4 12 13 12 16 M4∶3,M2∶2,M1、M3∶1
    3 9 11 11 16 M4∶3,M2、M3∶2,M1∶1
    2 9 9 10 15 M4∶3,M3∶2,M1、M2∶1
    1 8 9 9 14 M4∶3,M2、M3∶2,M1∶1
    下载: 导出CSV

    表  3   5种算法的加工总用时和设备系统整体利用率

    Table  3   The total processing time and overall utilization rate of equipment system of 5 algorithms

    对比算法 复杂产品A的加工总用时/工时 设备系统空闲时间总和/工时 设备系统整体利用率/%
    ISA-BPL 140 95 80.0
    ISA-BDD 135 45 90.0
    ISA-BDDEP 125 50 87.3
    ISA-BROLP 145 80 83.3
    ISA-CPCFE 120 30 92.7
    下载: 导出CSV
  • [1]

    GAREY M, JOHNSON D. Computers and intractability: a guide to the theory of NP-completeness[M]. Sanfrancisco: W. H. Freeman, 1979: 82-93.

    [2]

    MA Y, HE Z W, WANG N M, et al. Tabu search for proactive project scheduling problem with flexible resources[J]. Computers and Operations Research, 2023, 153: 106185/1-38.

    [3]

    ZHANG H, QIN C, ZHANG W, et al. Energy-saving schedu-ling for flexible job shop problem with AGV transportation considering emergencies[J]. Systems, 2023, 11(2): 103-124. doi: 10.3390/systems11020103

    [4]

    LUO Q, DENG Q W, XIE G H, et al. A Pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility[J]. Robotics and Computer-Integrated Manufacturing, 2023, 82: 102534/1-16.

    [5] 丁可欣, 仲智, 朱洁. 基于边缘云的动态和抢占式任务卸载调度算法研究[J]. 华南师范大学学报(自然科学版), 2023, 55(1): 113-120. doi: 10.6054/j.jscnun.2023011

    DING K X, ZHONG Z, ZHU J. Stochastic and preemptive task offloading for edge-cloud computing[J]. Journal of South China Normal University(Natural Science Edition), 2023, 55(1): 113-120. doi: 10.6054/j.jscnun.2023011

    [6] 閤泰梓, 唐秋华, 成丽新. 基于DQN协同进化算法的柔性作业车间能效调度优化[J/OL]. 计算机集成制造系统, (2023-02-27)[2023-10-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20230224.1901.011.html.

    XIA T X, TANG Q H, CHENG L X. Energy-efficient optimization of flexible job-shop scheduling based on DQN co-evolutionary algorithm[J/OL]. Computer Integrated Manufacturing Systems, (2023-02-27)[2023-10-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20230224.1901.011.html.

    [7] 王芳, 唐秋华, 饶运清, 等. 求解柔性流水车间调度问题的高效分布估算算法[J]. 自动化学报, 2017, 43(2): 280-293. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201702010.htm

    WANG F, TANG Q H, RAO Y Q, et al. Efficient estimation of distribution for flexible hybrid flow shop scheduling[J]. Journal of Automation, 2017, 43(2): 280-293. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201702010.htm

    [8] 陈伟能, 卢暾, 蒋嶷川, 等. 群智演化协同计算的研究进展与趋势[J]. 华南师范大学学报(自然科学版), 2023, 55(1): 1-18. doi: 10.6054/j.jscnun.2023001

    CHEN W N, LU T, JIANG Y C, et al. Advances and trends in crowd intelligence evolutionary and collaborative computation[J]. Journal of South China Normal University(Natural Science Edition), 2023, 55(1): 1-18. doi: 10.6054/j.jscnun.2023001

    [9]

    CHEN X L, LI J Q, DU Y. A hybrid evolutionary immune algorithm for fuzzy flexible job shop scheduling problem with variable processing speeds[J]. Expert Systems with Applications, 2023, 233: 120891/1-21.

    [10] 巴智勇, 袁逸萍, 李明, 等. 考虑分层耦合约束的复杂产品综合调度算法[J/OL]. 计算机集成制造系统, (2023-08-01)[2023-10-20]. http://kns.cnki.net/kcms/detail/11.5946.tp.20230801.1204.002.html.

    BA Z Y, YUAN Y P, LI M, et al. Integrated scheduling algorithm of complex product with hierarchical coupling constraints[J/OL]. Computer Integrated Manufacturing Systems, (2023-08-01)[2023-10-20]. http://kns.cnki.net/kcms/detail/11.5946.tp.20230801.1204.002.html.

    [11] 程强, 高元杰, 初红艳, 等. 基于多目标差分进化算法的机加工柔性作业车间调度[J]. 北京工业大学学报, 2023, 49(3): 335-345. https://www.cnki.com.cn/Article/CJFDTOTAL-BJGD202303003.htm

    CHENG Q, GAO Y J, CHU H Y, et al. Flexible job shop scheduling of machining based on multi-objective diffe-rential evolution algorithm[J]. Journal of Beijing University of Technology, 2023, 49(3): 335-345. https://www.cnki.com.cn/Article/CJFDTOTAL-BJGD202303003.htm

    [12] 唐伦, 李师锐, 杜雨聪, 等. 基于多智能体柔性演员-评论家学习的服务功能链部署算法[J/OL]. 电子与信息学报, 2023, 45(8): 2893-2910.

    TANG L, LI S R, DU Y C, et al. Deployment algorithm of service function chain based on multi-agent flexible actor-critic learning[J/OL]. Journal of Electronics and Information, 2023, 45(8): 2893-2910.

    [13] 谢志强. 工件间有约束的复杂产品工序调度研究[D]. 哈尔滨: 哈尔滨理工大学, 2009.

    XIE Z Q. Study on operation scheduling of complex pro-duct with constraint among jobs[D]. Harbin: Harbin University of Science and Technology, 2009.

    [14] 桂忠艳, 杨静, 谢志强. 基于剪枝分层的柔性加工车间调度算法[J]. 控制与决策, 2017, 32(11): 1921-1932. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201711001.htm

    GUI Z Y, YANG J, XIE Z Q. Scheduling algorithm for flexible job shop based on pruning and layering[J]. Control and Decision, 2017, 32(11): 1921-1932. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201711001.htm

    [15] 谢志强, 周含笑, 于洁, 等. 基于设备驱动的综合柔性调度冲突调解算法[J]. 北京理工大学学报, 2014, 34(11): 1150-1156. https://www.cnki.com.cn/Article/CJFDTOTAL-BJLG201411011.htm

    XIE Z Q, ZHOU H X, YU J, et al. Conflict mediation algorithm of the integrated flexible scheduling based on device driver[J]. Transactions of Beijing Institute of Technology, 2014, 34(11): 1150-1156. https://www.cnki.com.cn/Article/CJFDTOTAL-BJLG201411011.htm

    [16] 谢志强, 桂忠艳, 杨静. 基于设备驱动和实质路径的动态并行综合柔性调度算法[J]. 机械工程学报, 2014, 50(18): 203-212. https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB201418031.htm

    XIE Z Q, GUI Z Y, YANG J. Dynamic parallel integrated flexible scheduling algorithm based on device driver and essential path[J]. Journal of Mechanical Engineering, 2014, 50(18): 203-212. https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB201418031.htm

    [17] 谢志强, 王茜. 基于逆序层优先的柔性综合调度算法[J]. 电子与信息学报, 2022, 44(5): 1554-1562. https://www.cnki.com.cn/Article/CJFDTOTAL-DZYX202205006.htm

    XIE Z Q, WANG Q. Flexible integrated scheduling algorithm based on reverse order layer priority[J]. Journal of Electronics & Information Technology, 2022, 44(5): 1554-1562. https://www.cnki.com.cn/Article/CJFDTOTAL-DZYX202205006.htm

    [18]

    TENG H K, XIE Z Q, YUE X G, et al. A flexible integrated scheduling algorithm for dynamic determination processing equipment considering the Root-Subtree vertical and horizontal pre-scheduling[J]. IEEE Access, 2022, 10: 132298/1-16.

    [19] 谢志强, 周伟, 杨静. 工艺树子树循环分解的资源协同综合调度算法[J]. 机械工程学报, 2022, 58(13): 228-239. https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB202213020.htm

    XIE Z Q, ZHOU W, YANG J. Resource cooperative integrated scheduling algorithm based on sub-tree cycle decomposition of process tree[J]. Journal of Mechanical Engineering, 2022, 58(13): 228-239. https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB202213020.htm

    [20] 谢志强, 周伟, 杨静. 考虑层级调度次序的资源协同综合调度算法[J]. 计算机集成制造系统, 2022, 28(11): 3391-3402. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ202211006.htm

    XIE Z Q, ZHOU W, YANG J. Resource cooperative integrated scheduling algorithm considering hierarchical sche-duling order[J]. Computer Integrated Manufacturing Systems, 2022, 28(11): 3391-3402. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ202211006.htm

    [21]

    XIE Z Q, YANG D, MA M R, et al. An improved artificial bee colony algorithm for the flexible integrated scheduling problem using networked devices collaboration[J]. International Journal of Cooperative Information Systems, 2020, 29(1): 2040003/1-19.

    [22]

    GAO Y L, XIE Z Q, LIU X Y, et al. Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure[J]. Advances in Mechanical Engineering, 2020, 12(12): 1-15.

    [23]

    ZHOU W, ZHOU P W, ZHENG Y, et al. A heuristic integrated scheduling algorithm via processing characteristics of various machines[J]. Symmetry, 2022, 14(10): 2150-2170. doi: 10.3390/sym14102150

    [24]

    KONG X H, YANG Y H, YANG W Q, et al. Solving the flexible job shop scheduling problem using a discrete improved grey wolf optimization algorithm[J]. Machines, 2022, 10(11): 1100/1-38.

    [25]

    XIE Z Q, YANG G, TAN G Y. An algorithm of JSSP with dynamic collection of job with priority[C]//Proceedings of the International Technology and Innovation Conference 2006-Advanced Manufacturing Technologies. Hangzhou: Institution of Engineering and Technology, 2006: 106-111.

    [26] 周伟, 谢志强. 考虑多工序设备权重的资源协同综合调度算法[J]. 电子与信息学报, 2022, 44(5): 1625-1635. https://www.cnki.com.cn/Article/CJFDTOTAL-DZYX202205014.htm

    ZHOU W, XIE Z Q. Resource collaborative integrated scheduling algorithm considering multi-process equipment weight[J]. Journal of Electronics & Information Techno-logy, 2022, 44(5): 1625-1635. https://www.cnki.com.cn/Article/CJFDTOTAL-DZYX202205014.htm

图(4)  /  表(3)
计量
  • 文章访问数:  65
  • HTML全文浏览量:  11
  • PDF下载量:  23
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-12-03
  • 网络出版日期:  2024-06-21
  • 刊出日期:  2024-04-24

目录

/

返回文章
返回