考虑工序序列动态时间紧迫度的逆序贪婪综合调度算法

2022-05-31曹望成谢志强裴莉榕

电子与信息学报 2022年5期

关键词：结点复杂度排序

曹望成谢志强裴莉榕

①(哈尔滨理工大学计算机科学与技术学院哈尔滨 150080)

②(牡丹江师范学院计算机科学与技术系牡丹江 157011)

1 引言

调度优化问题的典型实例有制造车间中工序[1]的排序优化问题，网格计算中工作流[2–4]的费用优化问题和云计算中云服务工作流应用程序[5,6]或MapReduce任务[7]的排序优化问题。

智能制造已作为核心专项工程纳入《中国制造2025》实施战略。全国“两会”政府工作报告[8]、《中国制造2025》和国务院关于积极推进“互联网＋”行动的指导意见中均明确指出我国将大力发展产品个性化定制。消费者对产品多元化及个性化需求的不断增加，促使产品类型趋向多品种、小批量。当制造多品种、小批量产品，特别是单件复杂结构产品时，如果按照传统的先分步加工调度最后整体装配调度的生产模式排产，必将割裂加工工序和装配工序可并行处理的关系，降低复杂单产品生产效率。

谢志强等人[9–11]提出了第3类产品制造调度模式：加工工序和装配工序一同处理的综合调度，简称综合调度。综合调度是智能制造的核心组成部分，更是实现中国制造2025和工业4.0[12]的重要手段，学者针对综合调度问题的算法优化做了大量研究工作。针对单车间一般综合调度问题，谢志强等人[13,14]提出的考虑串行工序紧密度的择时综合调度算法[13]和考虑后续工序的择时综合调度算法[14]，存在以下缺点：

(1)文献[13]的择时综合调度策略为每道工序选择当前完工总用时最小的方案，忽略了该道工序对属于同一工序序列的后续串行工序的影响，导致算法出现局部最优而影响产品调度结果的弊端；

(2)文献[14]的工序排序策略与文献[13]相同，在应用择时综合调度策略调度工序时不能总是优先处理对生产周期有较大影响的工序序列上的工序，必须回溯调整[15]，导致算法复杂度偏高。

综上所述，本文提出串行工序序列的时间紧迫度(TUD)定义，应用所提工序排序策略得到工序队列，再结合所提逆序贪婪调度策略，以工序为单位建立其工序调度方案，最后一道工序的调度方案即为产品调度方案。

2 问题模型描述

为便于综合调度，将加工工序和装配工序统一定义为工序，加工设备和装配设备统一定义为设备。复杂单产品进行综合调度时需满足以下要求。(1)所有工序的加工时间已知而且与其加工顺序无关，产品工序间的约束关系事先已知。(2)每道工序只能由一台设备加工，某时刻每台设备只能加工一道工序，工序一旦开始被加工则直至加工结束不能被间断。(3)允许工序之间等待，允许设备在工序到达之前空闲。(4)当工序无紧前工序或其紧前工序均被加工完毕时，该工序才能被加工。(5)车间内不存在相同设备。

个性化定制复杂结构单产品(如飞行器)的加工工艺拓扑关系结构图呈树状结构，结点间有向边的方向与树结构中相反，称为产品加工工序树，简称工序树。为方便叙述，文中“结点”等价于他所表示的“工序”。

定义1 逆序工序树。将工序树中有向边的方向取反之后所得到的树型结构。

定义2 工序序列(Process Sequence, PS)。逆序工序树中，从根结点或者某叉点孩子结点a开始，沿有向边的方向遍历结点，直到叶结点b为止，彼此之间具有串行偏序关系的结点序列，称为工序a到工序b的工序序列，记为P Sab。特别地，当工序序列只包含单个工序c时，此工序序列记为P Scc。

定义3 工序序列长度。工序序列中全部结点所代表工序的加工时间之和。

定义4 结点的路径。逆序工序树中，从根结点开始沿有向边的方向遍历到当前结点，所得到的有序结点序列称为当前结点的路径。

定义5 结点的路径长度。结点的路径上全部结点的加工时间之和。

定义6 关键路径。当前逆序工序树中，长度最长的叶结点的路径，若不唯一，选择包含工序数多的路径为关键路径，若仍不唯一，任选其一。

定义7 工序队列。用于存放初始逆序工序树中的全部结点按照工序排序策略所得到的排序结果，为方便描述，队列中的结点简写为该结点所代表的工序名称。

定义8 准调度时间点。根据工艺约束关系，某工序的紧前工序加工结束时间点之后其对应的设备上所有空闲时间段的开始时刻都是该工序的准调度时间点。

定义12 工序调度方案。设工序队列中第k道工序试调度共产生X个准调度方案，它们构成准调度方案集Pk(X) ，从Pk(X)中选择完工时间最小的方案为工序调度方案，记为Pk，若不唯一，则从中选择使该道工序尽早开始加工的方案。

定义13 产品调度方案。产品的全部n道工序试调度后产生的最佳调度方案，用P表示。

假设复杂单产品包含n道工序，需要m台设备。Ai表示编号为i(1≤i ≤n)的工序，sij表示Ai在设备Mj(1≤j ≤m) 上的加工开始时间，tij表示其在设备Mj上的连续加工时间。工序队列中第1道工序为根结点工序，其加工开始时刻为0，对应的工序调度方案为P1。设工序队列中第k道工序的工序调度方案为Pk，则Pn即为P，一般综合调度问题的目标函数及约束条件描述为

3 策略设计

本文中工序、设备和方案的结构描述如下。

(1)用链表存储产品初始逆序工序树，工序队列存储经排序后的全部结点，链表和队列中元素的结构为：Node- Aid :{int} /Mid:int /T:int /L:int/F:Node*/Q:Node*[]/Tb:int /Te:int。A id是结点表示的工序名， M id 是工序对应的设备名，T是工序在机器M id 上的加工时间，L是结点的路径长度，F是指向其紧前工序的指针，Q是指向结点紧后工序的指针集合， Tb 是工序实际开始加工时刻，Te是工序的加工结束时刻。

(2)调度方案的设备列表中设备结构为：M−Mid:int/NodeList:Node∗/finishtime:int。

Mid 是设备名；N odeList 是设备上已试调度的工序链表，工序按加工开始时刻由小到大排序；finishtime是当前设备完工时间的最大值。

(3)调度方案结构为：P −Pid:int/MachineList:M ∗/totaltime:int。

Pid 是方案名；M achineList是方案对应的设备列表；t otaltime是方案中所有设备完工时间的最大值。

3.1 工序排序策略

3.1.1 工序排序策略分析

定义14 工序序列的时间紧迫度(Time Urgency Degree, TUD)。 Ai表示当前逆序工序树关键路径上的叉点，Li(j)表示以 Ai的第j个孩子为起点的唯一最长工序序列的长度，将Li(j)减去以 Ai为紧前工序的最长工序序列的长度max(Li(x)),(x= 1,2,...,j,...)的差值定义为以 Ai为紧前工序的第j个工序序列的时间紧迫度，记为T Pi(j) =Li(j)−max(Li(x))。

将 TPi(j)大小作为判断以第j个工序序列为关键路径的子树的完工时间对当前逆序工序树完工时间影响程度的基本依据。工序序列时间紧迫度越大表明其所属子树对当前逆序工序树的完工总时间影响越大，子树上工序对设备的需求紧迫度越大，为缩短产品生产周期，优先调度该子树上的工序。工序序列由若干加工时间不等的工序组成，随着时间紧迫度值大的工序序列上的某道或某些工序加工完毕，由该工序序列剩余工序所组成的工序序列的时间紧迫度值将会发生变化，即工序序列的时间紧迫度是动态变化的。

3.1.2 工序排序策略的算法设计

设置一个工序队列 Queue 、一个整型变量N、两个链表L ist0 和L ist1。 Q ueue存放工序排序策略的结果；N是初始逆序工序树的层数；L ist0存储初始逆序工序树，L ist1保存排序前的工序树L ist0。

算法1：工序排序策略算法

(1) 初始化L ist0 ， L ist1为空；

(2) 创建逆序工序树L ist0：根据输入产品工序的信息、工序间偏序关系和设备信息创建工序结点，输入工序属性值，插入逆序工序树，属性L，Tb和T e初值为0；

(3) 计算各结点的路径长度和N，确定关键路径的长度T′，更新各结点L属性值：根结点的路径长度为根结点的加工时间，其余结点的路径长度为该结点的加工时间加上其紧前工序的路径长度；

(4) 初始化Q ueue；

(5) i=0；

(6) 用L ist1备份L ist0；

(7) 判断工序树中叶子结点个数是否为1，是转步骤(8)，否则转步骤(9)；

(8)i++，将叶子结点入Q ueue，转(11)；

(9) 调用算法2，对当前逆序工序树中叶子结点排序并依次入Q ueue；

(10)L ist0 复制L ist1，在工序树中删除所有叶子结点，转步骤(6)；

(11)判断入队列结点的指针F是否为空，是转步骤(13)，否则转步骤(12)；

(12)从工序树中删除所有叶子结点，转步骤(7)；

(13)将Q ueue中的元素逆置；

(14)退出：返回Q ueue，N。

3.1.3 当前逆序工序树中叶子结点排序算法设计

设置1个1维指针数组a[k](k=0,1,...,n −2)，1个1维整型数组b[k](k=0,1,...,n −2)，堆栈Stack1和 S tack2 。排序过程中，a[k]存放指向以关键路径上各叉点的孩子结点作为起点的唯一最长工序序列的指针，b[k]存放a[k]元素所指向的各工序序列的时间紧迫度的数值，将a[k]中元素按b[k]中对应数值由小到大排序；S tack1存放某工序序列所包含的全部叉点；S tack2 存放数组a[k]从前到后的各个元素。

算法2：当前逆序工序树中叶子结点排序算法

(1) 初始化a[k]，b[k] ，S tack1 ，S tack2为空，j=0；

(2) i++ ；

(3) 确定关键路径，将其作为初始逆序工序树中时间紧迫度最大的工序序列；

(4)j++，将关键路径最后一个结点存入Queue，qj为指向该工序序列首结点的指针；

(5) 判断指针qj指向的结点是否为叉点，是转步骤(6)，否则转步骤(7)；

(6) 叉点入S tack1；

(7) 指针后移指向下一结点；

(8) 判断指针否为空，是转步骤(9)，否则转步骤(5)；

(9) 从工序树中删除此时间紧迫度最大的工序序列中的工序；

(10)判断S tack1是否为空，是转步骤(16)，否则转步骤(11)；

(11) S tack1出栈，在逆序工序树森林中，为出栈结点的各紧后工序找到以其为起点的一个长度最长的工序序列，若不唯一，选择工序数多的，用a[k++]保存指向各最长工序序列的首结点的指针；

(12)依次计算各工序序列的时间紧迫度并存入b[k++]：为便于计算，方法是用各工序序列叶结点的路径长度减去初始工序树关键路径长度；

(13)判断S tack1是否为空，是转步骤(14)，否则转步骤(11)；

(14)将a[k]中元素按b[k]中对应数值由小到大排序，数值相等时按工序序列所包含的工序数由小到大排序；

(15)将a[k]元素从前到后依次入S tack2保存，清空a[k]和b[k]；

(16)判断S tack2是否为空，是转步骤(18)，否则转步骤(17)；

(17) S tack2出栈，出栈指针所指工序序列作为其所属子树的时间紧迫度最大的工序序列，转步骤(4)；

(18)退出。

3.2 逆序贪婪调度策略

3.2.1 逆序贪婪调度策略分析

工序队列中第1个元素为根结点，安排其在所需设备上的“0”时刻试调度形成唯一的P1。试调度工序队列中序号为i(i ≥2)的工序时，其紧前工序已被试调度完毕，因此序号为i的工序的准调度时间点已知，设Q T中元素个数为X，可形成X个工序准调度方案，从中选择结束时间最小的准调度方案，若不唯一，选择使该工序最早开始加工的方案作为Pi，依次类推，直到序号为n的工序试调度结束，Pn即为P。

逆序贪婪调度的优点有3个：(1)因为是按由根到叶的顺序试调度各工序，在试调度Q ueue中序号为i(i ≥2)的工序时，约束关系被破坏的已试调度工序数量少，只需考虑序号小于等于i−1的同设备工序；(2)当序号为i−1的工序试调度结束，序号为i的工序的“准调度时间点”便随之确定，算法效率高；(3)逆序贪婪调度以单个工序为单位进行试调度，形成Pi时即实现了前i道工序的充分并行处理。

3.2.2 逆序贪婪调度策略算法设计

4 算法设计与复杂度分析

4.1 算法设计

首先应用算法1对全部工序进行排序，形成工序队列；其次对工序队列中序号为1的根结点进行调度，形成P1，再对序号为i(2≤i ≤n)的工序应用算法3建立Pi；最后形成甘特图并输出。

算法4：考虑工序序列动态时间紧迫度的逆序贪婪综合调度算法

(1) 应用算法1对工序排序，得到包含n(n ≥1)个工序的Q ueue；

(2) 试调度根结点工序，形成P1；

(3) i=2；

(4) 判断i≤n是否成立，是转步骤(5)，否则转步骤(7)；

(5) 应用算法3建立Pi；

(6)i++，转步骤步骤(4)；

(7) 形成甘特图并输出；

(8) 退出。

4.2 算法复杂度分析

假设产品的工序数为n，有m台设备，逆序工序树的层数为N。

文中算法4是总算法，在算法4中调用1次算法1和循环n −1次调用算法3。算法1调用了算法2。因而算法4的时间复杂度为总的时间复杂度，即算法1和循环n−1次调用算法3的时间复杂度之和。

4.2.1 算法1的时间复杂度

算法1主要包括以下4个操作：

(1)建立逆序工序树

建立逆序工序树是根据输入的产品工序信息、工序间的偏序关系及设备信息建立链表的过程，为链表中的n个结点的属性赋初值，时间复杂度为n的整数倍，时间复杂度为O(n)。

(2)计算工序路径长度和工序树的层数

计算工序路径长度和工序树的层数只需要对逆序工序树由根开始进行1次遍历，时间复杂度为O(n)。

(3)调用算法2

影响算法2时间复杂度的核心操作可简单地描述为以下4个步骤：

(a)获取当前逆序工序树中的叶子结点；

(b)对步骤1中得到的叶子结点进行排序，将排序后的结点追加到工序队列的末端；

(c)删除当前逆序工序树的叶子结点，得到新的当前逆序工序树；

(d)重复步骤(a)，步骤(b)，步骤(c)，直到所有的结点都进入工序队列。

4个步骤中对前3个步骤的循环次数为初始逆序工序树的层数N，分析前3个步骤的时间复杂度。

步骤(a)只需要对当前逆序工序树进行1次遍历，设工序树中结点个数为ni(i=1,2,...,N)，显然有ni

步骤(b)每次进行排序的叶子结点数平均为n/N，进行排序的时间复杂度为O((n/N)2)，循环N次的时间复杂度为O(N×(n/N)2)=O(n2/N)。

步骤(c)删除当前逆序工序树的叶子结点只需要对当前工序树进行1次遍历，循环N次总的时间复杂度与步骤(a)相同，最大为O(n2)。

因此调用算法2的时间复杂度为O(n2)。

(4)将工序队列Q ueue中的元素逆置

借助一个堆栈即可实现工序队列 Q ueue 中n个元素的逆置，时间复杂度为O(n)。

综合分析，算法1的时间复杂度为以上4个操作的时间复杂度之和，即为O(n2)。

4.2.2 循环调用算法3的时间复杂度

5 算法实例与对比分析

本文提出的算法是基于理论分析，不针对任何具体实例，具有普遍意义，为了方便读者了解该算法，下面借助产品调度实例进一步说明。设制造企业的单件订单产品 A包含37道工序，需要4台设备，产品的逆序工序树如图1所示。逆序工序树中结点用长方框表示，长方框内的信息是对应工序4个属性的简写：工序名的编号i|设备名的编号j|工序的加工时间|结点的路径长度，其中加工时间为单位时间(h)。

图1 产品A的逆序工序树

应用文献[11]的策略确定产品 A中工序的调度次序为： A37 ，A 34 ，A 36 ，A 35 ，A 32 ，A 29，A33 ，A31 ，A30 ，A25 ，A26 ，A27 ，A24 ，A21，A20 ，A28 ，A22 ，A23 ，A19 ，A16 ，A15 ，A17，A18 ，A 12 ，A 9 ，A 13 ，A 14 ，A 10 ，A 11 ，A 8，A7 ，A 6 ， A2， A4 ，A 5，A 3 ， A1。同设备工序A17 与A 18的路径长度分别为9和8，加工时间都是1 h，A 18所在的路径为关键路径，文献[11] 只关注工序的路径长度，忽略了工序所在分支对产品周期的整体影响，优先处理工序 A17造成调度结果欠佳，产品生产周期为26 h。

应用文献[13]的工序序列排序策略将产品 A的10个工序序列按路径长度由大到小排序。调度过程中，以关键路径形成的初始调度方案为基础，每调度1道工序形成多个准调度方案，从中选择当前最佳调度方案，容易使算法陷入局部最优。比如在调度工序 A4 时， A4的4个准调度时间点分别为2，6，11，17，文献[13]选择在时间点11调度 A4，虽然当前方案总用时最少，但使得设备 M3上 A1与A 7,A7与A 23之间出现了空闲时间段，且 A4所在工序序列的完成时间滞后，整体调度结果欠佳，产品生产周期为32 h。应用文献[11]和文献[13]，调度甘特图如图2和图3所示。

图2 使用文献[11]算法调度产品A所得调度甘特图

图3 使用文献[13]算法调度产品A所得调度甘特图

应用本文所提算法调度产品 A。应用算法1对工序进行排序，其中排序第1层叶子结点时的工序序列划分示意图如图4所示，工序排序结果为：A37 ，A34 ，A35 ，A24 ，A32 ，A31 ，A11 ，A21，A28，A 2。

图4 排序第1层叶子结点时的工序序列划分示意图

全部工序排序后，将 Queue中的元素逆置，Queue 中从前到后为： A1 ，A 3 ，A 7 ， A4 ，A 13，A6 ，A 9，A 18，A 12 ， A 15，A 23 ，A 5，A 17 ，A 8，A20 ，A27 ，A10 ，A22 ，A14 ，A25 ，A33 ，A16，A26 ，A 19 ，A 30 ，A 29 ，A 36 ， A2 ，A 28 ，A 21，A11 ，A31 ，A32 ，A24 ，A35 ，A34 ，A37。Queue 出队列，试调度工序，只有试调度 A4，A12， A 16 ，A 24 建立P4，P9，P22，P34的过程中涉及准调度时间点的选取。 A4的准调度时间点为2和6，选择2； A12的准调度时间点为5和8，选择5；A16 的准调度时间点为8, 11和15，选择8；A 24的准调度时间点为14和19，选择19。4次试调度过程如图5所示，灰色工序对应的方案作为工序调度方案。本文算法调度产品 A的调度甘特图如图6所示，生产周期为24 h。