一种分布式混合流水线调度优化方法

摘要

本发明实施例提供一种分布式混合流水线调度优化方法，该方法包括：初始化至少两个调度方案，并确定每个调度方案中所有工件的工厂分配结果以及初始阶段每一工厂的工件加工顺序；对于每一调度方案，重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足预设条件；最终获得拖期最小的调度方案，以供实现分布式混合流水线调度。通过重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，从而在较低的计算复杂度情况下快速实现算法的收敛，得到总拖期最小的调度方案，进而提高流水线调度效率。另外，通过双种群发散性搜索和局部增强搜索，进一步优化算法，从而得到总拖期更优的调度方案。

权利要求

1.一种分布式混合流水线调度优化方法，其特征在于，包括：

初始化至少两个调度方案，并确定每个调度方案中所有工件的工厂分配结果以及初始阶段每一工厂的工件加工顺序；

对于每一调度方案，重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足预设条件；

停止执行迭代后，将总拖期最小的调度方案作为最终调度方案，以供实现分布式混合流水线调度；

其中，所述调度规则用于确定每一阶段的工件加工顺序。

2.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，所述至少两个调度方案中的任意一个调度方案，按启发式方法确定初始阶段每一工厂的工件加工顺序，所述启发式方法包括：将所有工件按到期时间升序排列；

按升序排列序列中的先后顺序，选取一个工件分别分配至每个工厂序列的每个位置处，根据每一调度规则确定第二阶段及后续所有阶段的加工顺序并计算总拖期，保留总拖期最小的分配结果；

重复上述按升序排列序列中的先后顺序，选取一个工件分别分配至每个工厂序列的每个位置处，计算总拖期，以及保留总拖期最小的分配结果的过程，直至所有工件分配完成，最终获得初始阶段每一工厂的工件加工顺序。

3.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，所述调度规则的种类根据选取概率确定，相应地，所述方法还包括：每次迭代后，增大或保持优势调度规则的选取概率，减小或保持劣势调度规则的选取概率，并根据更新后的每一调度规则对应的选取概率，从多种调度规则中选取下次迭代的调度规则；

其中，优势调度规则指对同一个调度方案能获得较小总拖期的调度规则，劣势调度规则指对同一个调度方案获得较大总拖期的调度规则。

4.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，所述调度规则包括改进的列表调度规则LST，相应地，若选取概率确定的调度规则为LST时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间升序排列确定工件的加工顺序，若两个以上工件完工时间相等，则根据到期时间与剩余阶段的总加工时间的差值升序排列，确定工件的加工时间。

5.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，所述调度规则包括改进的最早到期时间规则IDD，相应地，若选取概率确定的调度规则为IDD时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间以及当前阶段机器的最早空闲时间，确定工件的加工顺序。

6.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，所述调度规则包括改进的拖期优先规则IPRTT，相应地，若选取概率确定的调度规则为IPRTT时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间、当前阶段机器的最早空闲时间以及未完成工件的惩罚系数，确定工件的加工顺序。

7.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，每次迭代后：对于总拖期为第一类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行小范围调整，对于总拖期为第二类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行大范围调整；

将调整后的初始阶段作为每一调度方案下次迭代的初始阶段；

其中，所述第一类为所有调度方案的总拖期升序排列的前50％，所述第二类为所有调度方案的总拖期升序排列的后50％。

8.根据权利要求1所述的分布式混合流水线调度优化方法，其特征在于，每次迭代后：对于总拖期最小的调度方案，对拖期最大的工厂和拖期最小的工厂，进行初始阶段工厂分配及每一工厂的工件加工顺序的小范围调整；

将调整后的初始阶段作为相应调度方案下次迭代的初始阶段。

说明书

一种分布式混合流水线调度优化方法

技术领域

[0001] 本发明涉及混合流水线分析领域，尤其涉及一种分布式混合流水线调度优化方法。

背景技术

[0002] 目前，分布式制造和调度已经成了一种趋势。分布式制造可以利用多个工厂或者企业的资源与加工条件，实现资源配置与共享，在此基础上以合理的运输与使用成本加快
产品的生产制造。经典流水作业车间中，一组工件按加工顺序经过多个制作阶段，每个阶段只有一台机器在运行，而现在，为了增加产能并且平衡不同阶段之间机器的加工能力，在某些加工阶段引入了多台机器同时进行加工，即混合流水车间调度。混合生产是未来制造业
的发展趋势，具有灵活性、通用性。

[0003] 目前求解分布式流水线调度问题以及混合流水线调度问题的方法主要有：精确算法、启发式算法以及智能优化算法。精确算法包括动态规划法，分支定界法等，通过数学规划模型求解目标最优值，虽然理论上能求得最优解，但由于计算量与存储量的限制，不适于求解大规模问题。启发式算法主要通过已有的经验、知识来缩小搜索域，构造近似最优解，原理简单，求解速度快，但通常解的性能较差。常用的启发式算法有变邻域下降法、基于工厂分配规则的启发式算法等。智能优化算法在启发式算法的基础上引入了迭代搜索机制，
架构简单，性能优良，并且具有很强的适用性，常用的智能优化算法包括遗传算法、模拟退火算法、禁忌搜索算法、果蝇优化算法等。

[0004] 由于分布式混合流水线调度问题具有大规模，强耦合等特性，现有的精确算法计算量太大；启发式算法效果较差，且易陷入局部极小；而目前的智能优化算法没有针对问题特性的设计，存在计算复杂度高，收敛缓慢、优化效果有限等缺点。综上，目前的分布式混合流水线调度方法存在计算复杂度高、收敛慢的问题。

发明内容

[0005] 为了解决上述问题，本发明实施例提供一种分布式混合流水线调度优化方法。

[0006] 本发明实施例提供一种分布式混合流水线调度优化方法，包括：初始化至少两个调度方案，并确定每个调度方案中所有工件的工厂分配结果以及初始阶段每一工厂的工件
加工顺序；对于每一调度方案，重复执行根据多种调度规则为初始阶段后的每一阶段确定
加工顺序的迭代过程，直至满足预设条件；停止执行迭代后，将总拖期最小的调度方案作为最终调度方案，以供实现分布式混合流水线调度。

[0007] 本发明实施例提供的分布式混合流水线调度优化方法，对于每一调度方案，通过重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足
预设条件，从而在较低的计算复杂度情况下快速实现算法的收敛，最终得到总拖期最小的
调度方案，进而提高流水线调度效率。

附图说明

[0008] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发
明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0009] 图1为本发明实施例提供的分布式混合流水线调度优化方法流程图。

具体实施方式

[0010] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0011] 混合流水线调度问题根据各阶段机器特性可分为带相同并行机的混合流水线调度问题，带一致并行机的混合流水线调度问题和带不相关并行机的混合流水线调度问题。
本发明考虑的是带一致并行机的分布式混合流水线调度问题(distributed hybrid 
flowshop problem with uniform parallel machines,简称 DHFSP-UPM)。

[0012] DHFSP-UPM研究如何将n个工件Jj，j＝1,…,n分配到F个相同的流水线工厂进行加工，工件Jj需要按顺序依次通过s个工序操作{O1,j,O2,j,…,Os,j}， Oi,j表示Jj在第Si阶段进行加工。各阶段的机器为Mi,l，l＝1,…,mi，i＝1,…,s，机器Mi,l的速度为vi,l，在本发明实施例中1≤vi,1≤vi,2≤…≤vi,mi，若操作Oi,j的加工时间为pi,j，则安排给机器Mi,l后，实际加工时间变为pi,j/vi,l。本发明是实施例中，所有工件相互独立，释放时间都为0，且不允许抢占，机器连续可用且一次只能加工一个工件，每个工件依次按照相同工序进行加工，同一时刻
只能被一台机器加工，工件可以分配到不同工厂，工厂分配一旦确定就不能修改。优化目标为总拖期(total tardiness，简称TT)最小化。各参数描述参见表1：

[0013] 表1

[0014]

[0015]

[0016] 本发明实施例解决的问题可通过如下公式进行表述：

[0017]

[0018]

[0019]

[0020] ST1，j≥0，j＝1，...，n  (4)

[0021]

[0022] Si，j≥Ci-1，j，i＝1，...，s，j＝1，...，n  (6)

[0023] zf，i，j，j′+zf，i，j′，j≤1，f＝1，...，F，i＝1，...，s，j＝1，...，n  (7)[0024] zf，i，j，j′+zf，i，j′，j≥yf，i，l，j+yf，i，l，j′-1，f＝1，...，F，i＝1，...，s，[0025] j＝1，...，n，j′＞j  (8)

[0026] STi，j′-Ci，j+U×(3-yf，i，l，j-yf，i，l，j′-zf，i，j，j′)≥0，f＝1，...，F，i＝1，...，s，[0027] j＝1，...，n，j′≠j，l＝1，...，mi  (9)

[0028] xf，j＝{0，1}，f＝1，...，F，j＝1，...，n  (10)

[0029] yf，i，l，j＝{0，1}，f＝1，...，F，i＝1，...，s，j＝1，...，n，l＝1，...，mi  (11)[0030] zf，i，j，j′＝{0，1}，f＝1，...，F，i＝1，...，s，j＝1，...，n，j′＝1，...，n  (12)[0031] 式(1)表示目标函数，总拖期TT的计算方式。式(2)-(11)为约束，保证调度方案的可行性。其中(2)保证每个工件仅被分配到一个工厂，(3)保证每个工件在每个工厂的每个
阶段仅被分配到一个机器，(4)-(6)为工件加工时间约束，并保证所有工件的开始加工时间不小于0。式(7-9)确保加工过程中，同一时刻每台机器最多加工一个工件且每个工件最多
在一台机器上加工。式(10)-(12) 定义三组0-1决策变量。

[0032] 图1为本发明实施例提供的分布式混合流水线调度优化方法流程图，如图1所示，为解决DHFSP–UPM问题，本发明实施例提供一种分布式混合流水线调度优化方法，包括：

[0033] 101，初始化至少两个调度方案，并确定每个调度方案中所有工件的工厂分配结果以及初始阶段的工件加工顺序；

[0034] 在101中，先初始化多个(两个以上)调度方案(算法中称为种群个体)，多个调度方案为PopSize个，对应为初始化PopSize个种群个体。初始化后，对于每一种群个体，进行工件到工厂的分配，确定每一工厂加工哪些工件，以及初始阶段，每一个工厂先加工哪个工
件。

[0035] 本发明实施例对确定每个调度方案中所有工件的初始阶段的工件加工顺序的方法作不具体限定，包括但不限于，随机生成所有工件的初始阶段的工件加工顺序。相应地，本发明实施例对初始阶段的工件工厂分配方法不作具体限定，包括但不限于：采用平均负
载时间规则进行工件到工厂的分配。例如，工件个数n＝3,阶段数s＝2，工厂数F＝2，工件加工顺序为＝{3,1,2}，工件 J1、J2、J3的总加工时间分别为20，16，10，则工厂的平均负载时间为 (20+16+10)/2＝23，20<23，(20+16)>23，因此将J1分配到F1，将J2、J3分配到F2。

[0036] 以编码作为初始化的分配在算法中的描述，采用F个工件序列(一个工件序列对应1个工厂，即F个工厂)以及n个工件的编码序列共同表示工件的分配和加工优先级，以n＝5,F＝2的算例为例，编码序列为：

[0037]

[0038] 即初始阶段加工顺序为3、1、2、5、4，共有两个工厂，工厂1分配工件3、1，工厂2分配工件2、5、4，初始阶段工厂的加工顺序是工厂1为3、1和工厂2为2、5、4。

[0039] 102，对于每一调度方案，重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足预设条件。

[0040] 在102中，重复执行根据多调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足预设条件，具体为：重复执行根据初始阶段的加工顺序分配加工机器，使用选取概率确定的调度规则，为初始阶段后的每一阶段确定加工顺序并分配加工机器后，
获取调度方案的总拖期的迭代过程，直至满足预设条件。预设条件包括预设次数、预设时间以及一定次数后TT 不再减小。

[0041] 根据初始阶段的加工顺序，为每一工件分配加工机器。若每一阶段的加工机器若有多个，则需为初始阶段的工件分配加工机器，若只有一个，则按顺序加工即可。初始阶段的工件分配到工厂后，在后续其它阶段直至最后阶段，每一工厂内的工件不再发生变化，只变化工件的加工顺序。

[0042] 初始阶段分配后，需确定下一阶段的加工顺序。本发明实施例的一次迭代过程中，调度规则用于确定初始阶段后所有阶段的加工顺序，调度规则有多个。每一调度方案，对于不同的调度规则有对应的选取概率，而后根据选取概率从多个调度规则中选取一个。根据选取的调度规则确定后续所有阶段的工件加工顺序，并对应分配加工机器。

[0043] 本发明实施例对调度规则的数量和类型不作具体限定，包括但不限于设置3个调度规则分别为列表调度规则(list scheduling，简称LS)，最早到期时间规则(earliest 
due date，简称EDD)以及拖期优先规则(priority rule for total tardiness，简称
PRTT)。LS规则为按照工件的完工时间排序进行分配，EDD 为根据到期时间进行排序，PRTT综合考虑完工时间和到期时间。例如，初始迭代时，对于每一调度方案，设置三类调度规则的选取概率分别为1/3。对于初始阶段后的每一阶段，根据确定的调度规则确定工件加工顺序，根据加工顺序分配机器，完成一次迭代过程。

[0044] 在包括初始阶段在内的每一阶段，工厂的工件加工顺序确定后，需对应为工件分配加工机器。本发明实施例对机器分配的方法不作具体限定，包括但不限于采用最早完成
机器规则进行机器分配。例如，工件Jj在阶段i加工时间pij＝6，在上一阶段的完工时间为3，设阶段i中有两台机器：Mi,1的释放时间(即可以开始进行加工的时间)为3，加工速度vi1为1,Mi,2的释放时间为4，加工速度为2。则工件安排在Mi,1加工时，开始时间为max(3,3)＝3，完成加工时间为3+6＝9；若安排在Mi,2，开始时间为max(3,4)＝4，完成加工时间为4+6/2＝7<9，所以选择Mi,2进行加工。

[0045] 103，停止执行后，将总拖期最小的调度方案作为最终调度方案，以供实现分布式混合流水线调度。

[0046] 在103中，停止执行后，得到多个调度方案，将最后一次迭代后TT最小的调度方案作为最终方案，用于流水线调度。

[0047] 本实施例提供的分布式混合流水线调度优化方法，对于每一调度方案，通过重复执行根据多种调度规则为初始阶段后的每一阶段确定加工顺序的迭代过程，直至满足预设
条件，从而在较低的计算复杂度情况下快速实现算法的收敛，得到总拖期最小的调度方案，进而提高流水线调度效率。

[0048] 基于上述实施例的内容，作为一种可选实施例，所述至少两个调度方案中的任意一个调度方案，按启发式方法确定初始阶段每一工厂的工件加工顺序，所述启发式方法包
括：将所有工件按到期时间升序排列；按升序排列序列中的先后顺序，选取一个工件分别分配至每个工厂序列的每个位置处，根据每一调度规则确定第二阶段及后续所有阶段的加工
顺序并计算总拖期，保留总拖期最小的分配结果；重复上述按升序排列序列中的先后顺序，选取一个工件分别分配至每个工厂序列的每个位置处，计算总拖期，以及保留总拖期最小
的分配结果的过程，直至所有工件分配完成，最终获得初始阶段每一工厂的工件加工顺序。

[0049] 对于初始化的多个调度方案中，选取任意一个调度方案，按启发式方法 (NEH)确定初始阶段每一工厂的工件加工顺序，启发式方法有多种，本发明实施例对该调度方案通
过启发式方法，确定初始阶段每一工厂的工件加工顺序的过程不作具体限定，此处只列出
一个改进的启发式方法(INEH)。以调度规则包括上改进型述LST、IDD以及IPRTT为例，INEH具体步骤包括：将所有工件按照到期时间升序排序，并按排列顺序依次分配工件；将当前待分配工件分配至每个工厂序列中的每个位置，并分别用上述三种解码规则进行解码，保留
使TT最小的个体序列及其调度；重复分配直到所有工件被分配，从而获得初始阶段每一工
厂的工件加工顺序。最后，该调度方案与其它调度方案一起参与上述根据多种调度规则为
初始阶段后的每一阶段确定加工顺序的迭代过程，从中选取一个总拖期最小的调度方案。

[0050] 本实施例提供的分布式混合流水线调度优化方法，通过启发式方法，获取初始阶段分配结果较优的调度方案，并结合上述根据多种调度规则为初始阶段后的每一阶段确定
加工顺序的迭代过程，从而使得获取总拖期最小的调度方案具有更优解。

[0051] 基于上述实施例的内容，作为一种可选实施例，调度规则的种类根据选取概率确定，相应地，上述方法还包括：每次迭代后，增大或保持优势调度规则的选取概率，减小或保持劣势调度规则的选取概率，并根据更新后的每一调度规则对应的选取概率，从多种调度
规则中选取下次迭代的调度规则；其中，优势调度规则指对同一个调度方案能获得较小总
拖期的调度规则，劣势调度规则指对同一个调度方案获得较大总拖期的调度规则。

[0052] 考虑到每种调度规则各有侧重点，为充分发挥每种调度规则的性能，本发明实施例中采用多调度规则协同的方法，每一调度方案根据实际性能进行评估，选择适合的调度
规则。每次迭代过程中，每个调度方案根据选取概率确定调度规则。以三种调度规则分别为LS、EDD和PRTT为例，三种调度规则的初始选取概率分别设为1/3，在第一次和二次迭代时均按照初始概率选择调度规则，第二次迭代中，所有阶段的工件加工顺序确定并分配机器后，计算TT。若第二次选取的调度规则TT更小，则第二次的调度规则为优势调度规则，第一次的调度规则为优势调度规则。增大第二次的调度规则对应的选取概率，减小第一次的调度规
则对应的选取概率，并用于第三次迭代的调度规则的选取。若第二次选取的调度规则TT更
大或相等，则保持第一、第二次调度规则对应的选取概率。即每次迭代后，增大或保持优势调度规则的选取概率，减小或保持劣势调度规则的选取概率。按更新后的概率，依概率轮盘赌为每一调度方案确定第三次迭代的调度规则，对于后续迭代次数中调度规则的确定过程
同理。

[0053] 本发明实施例对增大或保持优势调度规则的选取概率，减小或保持劣势调度规则的选取概率，并根据更新后每一调度规则对应的选取概率，从多种调度规则中选取下次迭
代的调度规则的方法不作具体限定，包括但不限于：

[0054] 对于任一个调度方案，设第g-1次迭代时使用调度规则i，第g次迭代选取调度规则k，若调度规则k所得拖期更小，则PSkg＝PSk(g-1)+1,PSig＝PSi(g-1)-1, 该调度方案在第g次迭代的后续操作中都使用调度规则k，否则PSkg＝PSk(g-1)， PSig＝PSi(g-1)，该调度方案在第g次迭代的后续操作中都使用调度规则i。对每一个调度方案都进行以上调度规则的更新。
更新第g+1次迭代时每一调度规则i的选取概率为Pi＝PSig/PopSize，其中，i＝{LS、EDD、PRTT}。按更新后的概率，依概率轮盘赌为每一调度方案确定第g+1次迭代的调度规则；其
中， PSkg为第g次迭代时选用调度规则k的调度方案个数，PSig为第g次迭代时选用调度规则i的调度方案个数，PopSize为调度方案的总个数。

[0055] 本实施例提供的分布式混合流水线调度优化方法，每次迭代后，增大或保持优势调度规则的选取概率，减小或保持劣势调度规则的选取概率。按更新后的概率，依概率轮盘赌为每一调度方案确定下次迭代的调度规则，从而每一调度方案自适应的选取调度规则，
进而获得更优的TT更小的最终调度方案。

[0056] 基于上述实施例的内容，作为一种可选实施例，所述调度规则包括改进的列表调度规则(list scheduling with tiebreaking，简称LST)，相应地，若选取概率确定的调度规则为LST时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间升序排列确定工件的加工顺序，若两个以上工件完工
时间相等，则根据到期时间与剩余阶段的总加工时间的差值的升序排列，确定工件的加工
时间。

[0057] 初始阶段每一工件的工厂分配结果确定后，后续阶段的分配，工厂加工哪些工件是固定的，但是顺序待确定，工件的加工顺序的确定可以看作是工厂内每一工件加工顺序
的确定，本发明实施例中，调度规则中包括改进的列表调度规则，改进的LST具体为，第二阶段开始，根据每个工厂上一阶段各工件的完工时间的升序排序来确定加工顺序。当有两个
及以上工件完工时间相等，则按照dij升序排列确定， 其中，dj为工件j
的到期时间， 为工件j第i阶段及其之后的加工时间，即剩余阶段(当前阶段及其
之后阶段)的总加工时间。改进的列表调度规则，若两个以上工件完工时间相等，则根据到期时间与所有阶段的总加工时间的差值的升序排列，确定工件的加工顺序，有利于最小化
总拖期。

[0058] 基于上述实施例的内容，作为一种可选实施例，调度规则包括改进的最早到期时间规则(improved due date，简称IDD)，相应地，若选取概率确定的调度规则为IDD时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间以及当前阶段机器的最早空闲时间，确定工件的加工
时间。

[0059] LST规则按照完工时间进行排序，可以使得调度更为紧凑，但相对的，对于完工时间晚但到期时间紧的工件而言，用LST规则反而会增大拖期。IDD 规则更多考虑到期时间，本发明实施例中，从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间以及当前阶段机器的最早空闲时间，确定工件的加工顺序。具体方法包括如下：

[0060] 将前min(mi，nf)个工件按tij升序排序，tij＝max(dij，Ci-1，j)，将前min(mi，nf) 工件分配完成后，后续工件按tij＝max(dij，max(Ci-1，jmMT))升序排列。其中，mMT 表示当前机器的最早空闲时间，dij为到期时间dj与剩余阶段的总加工时间 的差值，其它参数参见表1。最后根据排列结果确定工件的加工顺序。

[0061] 本实施例提供的分布式混合流水线调度优化方法，根据工件上一阶段的完工时间、工件的到期时间以及当前阶段机器的最早空闲时间，确定工件的加工顺序，综合考虑多方因素，有利于最小化总拖期。

[0062] 基于上述实施例的内容，作为一种可选实施例，调度规则包括改进的拖期优先规则(the improved priority pule for total tardiness，简称IPRTT)，相应地，若选取概率确定的调度规则为IPRTT时，所述为初始阶段后的每一阶段确定加工顺序，包括：从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间、当前阶段机器的最早空闲时间以及未完成工件的惩罚系数，确定工件的加工顺序。

[0063] IPRTT规则在IDD规则的基础上，增加了对未完成工件的惩罚项，通过惩罚系数α实现。本发明实施例中，从第二阶段起，对于每个工厂，根据工件上一阶段的完工时间、工件的到期时间、当前阶段机器的最早空闲时间以及未完成工件的惩罚系数，确定工件的加工顺序。具体方法包括如下：

[0064] 前min(mi，nf)个工件按tij升序排序，tij＝αCi-1，j+max(Ci-1，j，dij)，将这些工件分配完成后，后续工件按tij＝αCi-1，j+max(max(Ci-1，j，mMT)，dij)升序排列。具体参数标识参见表1，最后根据排列结果确定工件的加工顺序。

[0065] 本实施例提供的分布式混合流水线调度优化方法，根据工件上一阶段的完工时间、工件的到期时间、当前阶段机器的最早空闲时间以及未完成工件的惩罚系数，确定工件的加工顺序，综合考虑多方因素，有利于最小化总拖期。

[0066] 基于上述实施例的内容，作为一种可选实施例，每次迭代后：对于总拖期为第一类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行小范围调整，对于总拖期为第二类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行大范围调
整；将调整后的初始阶段作为每一调度方案下次迭代的初始阶段；其中，其中，所述第一类为所有调度方案的总拖期升序排列的前50％，所述第二类为所有调度方案的总拖期升序排
列的后 50％。

[0067] 为增强算法的全局搜索能力，设计发散性搜索环节。每一次迭代后，首先将种调度方案根据总拖期值(性能)分为两个类别，分别针对不同类别进行初始阶段的工厂分配结果以及每一工厂的工件加工顺进行调整。其中，性能较优的第一类调度方案进行小范围调整
(细搜索)，性能较差的第二类调度方案进行大范围的调整(粗搜索)，将该针对两类调度方
案初始阶段进行调整的过程称为双种群发散性搜索。在具体实施过程中可以将所有调度方
案按照总拖期进行排序，前50％为第一类，后50％为第二类，也可根据具体情况进行比例的调整。

[0068] 细搜索主要包括以下3种操作：

[0069] F_insert：随机选择工厂f及其中的一个工件，将它插入到πf另一个随机位置，并相应调整πF+1(对应与上述π的最后一行)

[0070] BF_Swap：随机选择两个工厂fi，fj以及各工厂内的一个工件，交换它们在πfi和πfj中的位置，并相应调整πF+1

[0071] BF_insert：随机选择工厂f及其中一个工件，将它插入到另一个随机工厂编码的随机位置中，并相应调整πF+1

[0072] 其中，πF+1的编码按照从π1到πF的编码顺序叠加进行调整。

[0073] 在具体实施过程中，在每次迭代中，顺序执行以上三种操作，择优(选取总拖期小)保留调度方案。

[0074] 粗搜索主要包括以下2中操作：

[0075] Insert：随机选择πF+1中的一个工件，将它插入到πF+1另一随机位置中，根据得到的π′F+1重新进行解码产生初始阶段的调度方案。

[0076] Swap：随机选择πF+1中的两个工件，交换位置，根据得到的π′F+1重新进行解码产生初始阶段的调度方案。

[0077] 在具体实施过程中，在每次迭代中，顺序执行以上两种操作，择优(选取总拖期小)保留调度。

[0078] 由上可知，细搜索主要针对调度层面中工厂间和工厂内的局部环节调整，保留具有优良个体调度的大部分信息，而粗搜索对编码层面重新进行调整，使劣势个体(总拖期较大的)尽可能有所改进。

[0079] 本实施例提供的分布式混合流水线调度优化方法，对于总拖期为第一类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行小范围调整，对于总拖期为第二
类的，对初始阶段的工厂分配结果以及每一工厂的工件加工顺序进行大范围调整，从而总
拖期小的一类可以通过小范围调整进一步找到更优的调度方案，总拖期大的一类可以通过
大范围调整进一步找到更优的调度方案，避免了陷入局部最优。

[0080] 基于上述实施例的内容，作为一种可选实施例，每次迭代后：对于总拖期最小的调度方案，对拖期最大的工厂和拖期最小的工厂，进行初始阶段工厂分配及每一工厂的工件加工顺序的小范围调整；将调整后的初始阶段作为相应调度方案下次迭代的初始阶段。

[0081] 本发明实施例中，对算法的最优解(总拖期最小的调度方案)进行初始阶段工厂分配及每一工厂的工件加工顺序的小范围调整(将该过程称为局部增强搜索)，记拖期最大的
工厂为关键工厂Fmax，拖期最小的工厂为Fmin。局部搜索步骤包括：

[0082] Step1：对调度解中每个工厂进行F_insert操作；

[0083] Step2：选取Fmax中Tardiness最大的工件，插入到Fmin任意位置中；

[0084] Step3：选取Fmax中Tardiness最大的工件，与Fmin任意工件交换位置。

[0085] 具体实施过程中，每次迭代可顺序执行上述步骤直到性能没有改善为止，将调整后的初始阶段作为相应调度方案下次迭代的初始阶段。

[0086] 本实施例提供的分布式混合流水线调度优化方法，通过对拖期最大的工厂和拖期最小的工厂，进行初始阶段工厂分配及每一工厂的工件加工顺序的小范围调整，使获得的
最优调度方能够进行小范围调整，避免陷入局部最优。

[0087] 基于上述各实施例的内容，对本发明进行举例说明，选取LST、IDD和 IPRTT三个调度规则作为本案例的调度规则，采用上述依概率轮盘赌为每一调度方案确定下次迭代的调度规则的方法，其中一个种群个体由改进的启发式方法INEH产生，并结合双种群发散性搜
索、局部增强搜索进行迭代。将本发明另一实施例的方法称为群智能优化算法(swarm 
intelligence optimization algorithm，简称SIOA)，进一步验证SIOA的效果如下所述。

[0088] 为了验证本发明案例中所用算法在带一致并行机的分布式混合流水线调度问题中的有效性，设计了450个大规模测试算例。每个算例的到期时间由公式
产生，其中u服从范围为[0，1]的均匀分布，λ∈{0.5，2，4}为到期时
间因子，用于控制到期时间的紧张程度，λ越小则到期时间越紧。测试算例规模为n＝{20，
50，100}，s＝{2，5，8}，F＝{2，3，4，5，6}共45 种组合，每种组合有10个不同算例。预设条件对应终止准则为CPU运行时间：0.1×n×s，评价指标为相对百分偏差(relative 
percentage deviation，简称 RPD)。

[0089]

[0090] 其中TTal为算法得到的拖期，TTmin为多种算法得到的最小拖期，TTmax为多种算法得到的最大拖期。

[0091] 采用试验设计方法(design of experiment，DOE)考察参数对算法性能的影响，SIOA中参数包括种群规模PopSize，以及IPRTT中对工件释放时间的惩罚系数α。采用算例
n20_s5_F3_1进行DOE测试，每个参数设4个水平值，表2为SIOA参数的水平取值，如表2所示。

[0092] 表2

[0093]

[0094] 根据参数正交表对每组参数独立运行10次，表3为参数正交表及响应值 (RV)，结果如表3所示：

[0095] 表3

[0096]

[0097] 进而计算得到各参数的水平值响应及参数对性能影响的等级，表4为各参数平均RV，如表4所示：

[0098] 表4

[0099]水平 PopSize α
1 297.8 356.3
2 285.6 274.5
3 299.2 284.1
4 309.5 277.2
Delta 23.9 81.7
排秩 2 1

[0100] 可见α对算法性能影响较大，其次是PopSize，最佳参数组合为： PopSize＝10，α＝4。

[0101] 为验证改进的解码规则的有效性，每个大规模算例各产生1000个随机初始解，分别用LS、LST，EDD、IDD，PRTT、IPRTT进行解码，得到结果有 70.1％的算例中LST优于LS，
66.7％的算例IDD优于EDD，72.1％的算例PRTT 优于IPRTT。

[0102] 由于贪婪迭代算法(Iterate d Gree dy methods，简称IG)是目前解决分布式流水线问题以及混合流水线问题较为有效且新颖的算法，本发明将SIOA与 IG进行仿真比较，并且为验证算法各个环节有效性，将算法与仅用一种解码规则LS的启发式方法NEH、使用多种解码规则的启发式方法INEH，初始解都为随机产生的SIOA-nN以及无局部增强搜索环节
的SIOA-nLS进行对比。表5为λ＝0.5时算法比较结果，表6为λ＝2时算法比较结果，表7为λ＝
4 时算法比较结果，表中数值为相对百分比偏差。仿真结果如各表所示，可以得出，SIOA是求解DHFSP-UPM的有效算法。

[0103] 表5

[0104]F NEH IG SIOA iNEH SIOA-nN SIOA-nLS
2 93.78 20.45 7.45 60.22 63.43 11.30
3 87.49 35.31 6.16 61.09 59.13 8.74
4 86.30 57.76 4.83 62.09 17.41 6.98
5 77.79 63.87 5.54 58.75 8.07 6.47
6 74.60 61.41 4.05 55.45 8.79 8.10

[0105] 表6

[0106]F NEH IG SIOA iNEH SIOA-nN SIOA-nLS
2 64.56 2.18 0.56 40.80 30.58 33.65
3 61.37 8.02 7.24 36.43 26.53 30.34
4 59.44 27.76 6.24 31.52 14.55 26.54
5 40.35 20.72 3.17 18.41 13.02 15.63
6 33.55 16.21 5.07 20.51 11.27 16.46

[0107] 表7

[0108]F NEH IG SIOA iNEH SIOA-nN SIOA-nLS
2 46.99 2.25 0.32 25.92 22.50 22.56
3 43.19 9.19 5.44 21.08 12.13 16.94
4 29.22 11.14 2.78 12.24 742 9.48
5 13.18 5.38 0.39 6.44 4.65 5.55
6 11.33 7.45 0.15 6.81 6.63 5.87

[0109] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该
计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施
例或者实施例的某些部分所述的方法。

[0110] 最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；
而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和
范围。