基于逆序虚拟零部件的紧密衔接综合调度算法

郭伟飞，宋豫川+，周 璠，雷 琦，吕向飞

(1.重庆大学 机械传动国家重点实验室，重庆 400030；2.重庆江增船舶重工有限公司，重庆 402263)

0 引言

生产调度是对一定时间段内的企业资源进行优化配置，以达到优化某个或某些特定生产指标的目的。有效的调度优化算法能缩短生产周期、降低生产成本、增加企业利润和提高客户满意度[1]。传统的生产调度研究一直习惯于将加工与装配调度割裂开进行研究，主要针对的是加工调度，而对装配调度研究较少，且多集中在大批量流水线作业产品上，普遍认为不存在物料短缺，没有真正意义上考虑装配约束。装配线平衡和产品排序是目前装配调度研究的主流方向，如鲁建厦等[2]针对混流汽车装配线排序问题，提出一种融入禁忌搜素算法的混合人工蜂群算法。李大双等[3]提出一种将殖民竞争算法与延迟接受爬山算法相结合的混合算法，用于解决多约束双边装配线平衡问题。在考虑装配线节拍和日可用工时的约束下，郑谐等[4]对飞机脉动式装配线平衡问题进行了研究，并提出一种基于可行序列编码方式的遗传算法。因此，将加工与装配一同处理的综合调度问题被提出，并逐渐引起学者们的关注。经过多年来的不断发展，综合调度问题已经发展成为区别于作业车间调度问题和流水车间调度问题的第三类调度问题[5]。

目前，一些学者们已在综合调度领域做了大量研究，并取得了一定的成果。以谢志强教授最为突出，他提出了一系列基于产品加工工艺树的综合调度算法，如基于拟关键路径法(Allied Critical Path Method ,ACPM)和最佳适应调度方法(Best Fit Scheduling Method, BFSM)的动态作业车间调度算法[6]、基于工序集的动态关键路径多产品制造调度算法[7]、非紧密衔接工序动态车间调度算法[8]、基于交货期紧迫度的综合调度算法[9]、考虑后续工序的择时综合调度算法[10]和考虑串行工序紧密度的择时综合调度算法[11]等。综合调度问题主要存在于单件小批量且对装配组件具有较高精度要求的复杂产品，如模具。然而，事实上，在复杂产品实际加工生产中，由于生产工艺、存储能力或者生产管理方式等原因，导致了紧密衔接约束限制的出现，它要求紧后工序的开始时间必须等于紧前工序的完成时间。目前，紧密衔接综合问题大致可分为单一紧前工序紧密衔接的情形和非单一紧前工序紧密衔接的情形。李志敏[12]首先对第一种情形进行了研究，他在ACPM和BFSM调度策略的基础上，提出一种移动交换法来满足工序间的单一紧前工序紧密衔接约束，实现了对非柔性的复杂产品综合调度问题的求解。然而，由于采用的ACPM调度策略造成紧后工序的开始时间往往不是其紧前工序的结束时间，需要额外的调整操作，增加了算法的复杂度。为了克服上述的不足，谢志强等[13]提出一种将具有单一紧前工序紧密衔接约束条件的工序组进行统一联动的综合调度算法，避免了额外的调整操作，降低了算法的复杂度，但仍存在忽略了长路径上工序对调度结果的影响因素。针对第二种情形，在上述研究成果的基础上，谢志强等[14]综合利用信号驱动、逆序调度和锁定紧密衔接工序组的前沿贪心策略，提出一种基于逆序信号驱动的紧密衔接综合调度算法，同时它具有复杂度低和能实现对紧密衔接紧前工序数无限制问题求解的优势。然而，上述这些分析方法或构造性的方法比较适合小规模的复杂产品综合调度问题，随着问题规模的不断增大，加之综合调度问题中更为复杂的装配约束关系，该类方法在计算求解时间方面受到一定的制约[15]。此外，以上算法属于启发式算法，它们虽然能够对特定的问题求得较好的解，但是算法通用性较差。

目前，已证明绝大多数生产调度问题都是NP-hard问题，不存在有效的多项式时间求解方法。因此，研究人员将研究目光投向了各种近似方法。尤其自20世纪80年代以来，受自然现象或物理规律启发而发展起来的元启发式算法，为解决复杂组合优化的调度问题提供了新的手段并已发展成为主流方法。鉴于复杂产品综合调度问题也属于比较复杂的NP-hard问题，元启发式算法与启发式算法相比，更适应于实际大规模的复杂产品综合调度问题，可以较好地满足实际问题的需求。目前，关于复杂产品综合调度问题的元启发式算法报道还不是很多，只有少数学者进行了研究。如王林平等[16-17]采用一种基于选择解码字符串(Selective Decoding String, SDS)解码的遗传算法来对综合调度问题进行求解，它能保证经SDS解码方法转化后生成符合问题约束的可行解。赵诗奎等[15]在提出虚拟零部件概念的基础上设计出了一种基于遗传算法的产品综合调度算法，该算法通过一种基于虚拟零部件级别的分区编码方式来保证初始种群的可行性，此外，它的遗传操作方法也能保证生成的子代个体的可行性，同时实验也表明该算法具有良好的求解速度和质量。石飞等[18]进一步研究并提出一种基于工序约束链编码的遗传算法来求解综合调度问题，该算法的最大优势在于设计的编码方法能保证初始解空间的可行性和完备性。以上求解综合调度问题的遗传算法虽然具有各自的优点，但也都存在一些明显的不足，如SDS解码方法无法保证遗传操作过程中个体的可行性，导致在解的全域中进行搜索，极大地降低了算法的求解效率。基于虚拟零部件级别分区编码的产品综合调度算法中的分区编码方式会在原本不存在顺序约束关系的零部件之间强加上一层或多层约束关系，导致该编码不具备完备性，限制了遗传操作搜索的空间范围，必然对算法的求解效率造成影响。基于工序约束链编码的遗传算法无法保证产生子代个体的可行性，需要进行额外的检测和修复操作，这无疑增加了算法的计算量。综上所述，不难看出目前求解复杂产品综合调度问题的元启发式算法普遍存在明显的缺陷和不足。这也必然会制约求解更加复杂的紧密衔接综合调度问题的元启发式算法的发展，更令人遗憾的是，关于求解紧密衔接综合调度问题的元启发式算法的研究报道目前还尚未发现。

在众多的元启发式算法中，遗传算法经40多年的研究已进入一个比较成熟的阶段，具有深厚的研究基础。为了借鉴遗传算法在综合调度问题上已有的研究成果，本文将其应用于求解紧密衔接综合调度问题，建立了问题的数学模型，提出一种基于逆序虚拟零部件双亲孩子表示法的编码方法，设计了能确保满足复杂产品逆序虚拟零部件顺序约束的遗传算子以及两种各具特色且能保证生成原问题的可行解的解码方法，并通过多个实例验证了算法的有效性和优越性。

1 问题描述

综合调度问题研究的是在边加工边装配生产模式下如何优化调度复杂产品工序，使其总用时最小。而紧密衔接综合调度问题又增添了紧密衔接约束，属于一种特殊的综合调度问题。为了便于问题的分析，一般将加工和装配工序统一为加工，加工和装配设备统一为设备[19]。该问题可描述为：设有n道工序的复杂产品需要在m台设备上进行加工，一道工序在某一时刻只能被一台设备加工，一台设备在某一时刻也只能加工一道工序；设备一旦加工某道工序，则中途不能中断，直至加工完毕后方能加工其他工序；每道工序只能在其所有紧前工序加工完毕后，才能开始加工；存在紧密衔接约束的工序的开始加工时间必须是其紧密衔接的紧前工序的完工时间。若工序oi在设备Mk上加工，则Xik=1，否则Xik=0；Si、Tik和Ci分别为工序oi在其相应加工设备上的开始时间、加工时间和完工时间；Fk为设备Mk的总空闲时间；Pi和Ni分别为工序oi的紧前工序集合和紧密衔接的紧前工序集合，显然Ni⊆Pi，此外，在Pi和Ni分别存在的情况下，工序oj和ol分别为Pi和Ni中的任意一个工序。因此，该问题的数学模型为：

minCmax=min{max(Ci)}。

(1)

s.t.

min{Si}&min{Fk}；

(2)

Si≥max(Sj+Tjk′),Xik=1,Xjk′=1,oj∈Pi；

(3)

Si≥Sh+Thk,Xik=1,Xhk=1；

(4)

Cl=Si,ol∈Ni。

(5)

其中：式(1)中的max(Ci)表示复杂产品最后一道工序的结束时间，minCmax是综合调度优化目标，即复杂产品的总加工时间尽可能小；式(2)表示复杂产品各道工序应尽早开始加工，且尽可能地缩短加工设备上的总空闲时间；式(3)中工序oj是工序oi的一个紧前工序，表示各个工序必须在其所有紧前工序之后加工；式(4)中工序oh是与工序oi同一台加工设备的前一工序，表示同一加工设备上的工序只能依次进行加工；式(5)中工序ol是工序oi的一个紧密衔接的紧前工序，表示紧密衔接的紧前工序的完工时间是其紧密衔接的紧后工序的开始时间。

复杂产品的加工和装配完全工艺图是树状结构，对应的工艺图被称为产品的加工工艺树，树中节点代表工序，边代表工艺约束的偏序关系[15]。针对部分工序间存在紧密衔接约束关系的复杂产品，则采用扩展加工工艺树[20]来表示，它使用虚线框标出存在紧密衔接约束关系的工序。此外，由于在树状结构的扩展加工工艺树中存在一个父节点与多个子节点的偏序关系，因此，在扩展加工工艺树中既可能存在单一紧前工序紧密衔接约束关系的情况，也可能存在非单一紧前工序紧密衔接约束关系的情况，如图1所示。由于单一紧前工序紧密衔接约束关系也可视为非单一紧前工序紧密衔接约束关系的特例，因此，在本文中二者不作严格的区分，统一视为非单一紧前工序紧密衔接约束关系的情况。从图1中的复杂产品扩展加工工艺树不难看出，紧密衔接综合调度问题不仅需要考虑工序间的先后顺序约束关系，还需要考虑工序间特殊的紧密衔接约束关系，导致工序之间必须遵循更加严格的顺序约束关系，加大了问题求解的复杂度，从而成为解决该问题的主要难点。

2 算法设计

基于上述对紧密衔接综合调度问题的描述以及对难点的分析，本文采用基于逆序虚拟零部件的遗传算法对问题进行求解，研究了算法相关的实现技术。在深入分析复杂产品扩展加工工艺树结构特点的基础上，实现了逆序虚拟零部件的剪枝查找，并提出了紧密衔接逆序虚拟零部件、非紧密衔接逆序虚拟零部件、叉点逆序虚拟零部件以及子孙逆序虚拟零部件等相关概念。在此基础上，设计了满足逆序虚拟零部件顺序约束关系的编码方法以及交叉和变异算子，此外，又提出了两种能保证生成满足紧密衔接逆序虚拟零部件内的紧密衔接约束关系的解码方法，进而实现对问题的求解。

2.1 基于逆序虚拟零部件双亲孩子表示法的编码

编码是解的遗传基因的表示，实现将求解问题的解表达成遗传空间的染色体或个体。它会影响遗传算法后续的各个阶段，是遗传算法设计的关键，其设计必须考虑染色体的合法性、可行性和有效性，以及对问题空间解表达的完全性[21]。不好的编码方法会产生不可行的问题解，需要增加额外的修补操作，从而降低算法的执行效率。在经典的作业车间调度问题研究中，基于工序的编码是应用最为广泛的编码方式，它能保证生成问题的可行解[22]，其根本原因是该调度问题中各工件是相互独立的。然而，由于复杂产品综合调度问题中工件间存在约束，造成基于工序的编码方法无法直接使用，更无法直接应用于存在紧密衔接约束的特殊综合调度问题中，因此，本文基于文献[15]中的虚拟零部件剪枝查找方法，提出了针对紧密衔接综合调度问题的逆序虚拟零部件剪枝查找方法，以及基于逆序虚拟零部件双亲孩子表示法的编码方法。

2.1.1 逆序虚拟零部件的剪枝查找方法

将包含非单一紧前工序紧密衔接约束关系的复杂产品所对应的扩展加工工艺树用有向图来表示。由于在树状结构的扩展加工工艺树中存在一个父节点与多个子节点的偏序关系，若采用正序处理的思路，要想保证多个子节点的结束时间相同，会使调度过程变得复杂，因此，本文采用逆序处理的思路对问题进行分析与求解。图2所示为上述复杂产品P的逆序扩展加工工艺树以及其有向图，图中带阴影的节点表示存在紧密衔接约束的工序。逆序虚拟零部件剪枝查找方法与文献[15]中的剪枝查找方法略有不同，它需要结合复杂产品紧密衔接约束信息对有向图进行剪枝，依次查找出各个逆序虚拟零部件，具体实现步骤如下：

步骤1计算逆序扩展加工工艺树所对应的有向图中各节点的入度数。

步骤2从一个入度数为0的节点开始(称为起始节点)，沿着有向边查找下一节点，若起始节点对应的为紧密衔接工序(即带阴影的节点)，则采用树的广度优先遍历进行查找，直至遇到非紧密衔接工序对应的节点(称为终止节点)；若起始节点对应的为非紧密衔接工序，则采用树的深度优先遍历进行查找，直至遇到入度数大于0或紧密衔接工序对应的节点(也称为终止节点)，将起始节点到终止节点的所有节点(不含终止节点)从有向图中剪枝，它们所对应的工序集构成一个逆序虚拟零部件。

步骤3重复步骤2，直至所有的入度数为0的节点剪枝完毕。

步骤4将剪枝完毕后剩余的节点构成的子图作为新的有向图，并重复步骤2和步骤3。

步骤5重复步骤4，直至不能再剪枝为止。

最终，通过上述剪枝方法可得到一系列逆序虚拟零部件。以图2所示为例，经上述操作后的结果如图3所示，不难发现，存在紧密衔接约束关系的工序共同构成一个逆序虚拟零部件，如紧密衔接工序P2、P3、P4以及P7共同构成了逆序虚拟零部件RVC2，同时也令它们具备必属于同一个逆序虚拟零部件的特性。这种特性为后续编码和遗传算子解决逆序虚拟零部件间的顺序约束关系奠定基础。

2.1.2 基于改进的双亲孩子表示法表示树状结构逆序虚拟零部件

从图3b中可以看出，逆序虚拟零部件之间呈现的关系并非一一对应，而是一多对应，对应关系复杂化之后，则线性结构不便于描述这种复杂情形，需要用符合树形结构特点的其他存储方式来存储这种非线性结构。按照“存数值、存联系”的原则并结合后续所提出算法的特点，本文基于树的双亲孩子表示法[23]，提出了改进的双亲孩子表示法来存储经过剪枝查找操作后所产生的树状结构逆序虚拟零部件信息。

改进的双亲孩子表示法仍采用数组存储树状结构逆序虚拟零部件中的节点信息，共有6列，分别为下标、逆序虚拟零部件、对应的原工序集、双亲位置、孩子位置和工序数目。下标即为逆序虚拟零部件的编号，同时每个逆序虚拟零部件节点的双亲和孩子都是通过这个编号标示出来的。需要注意的是：工序数目并不总是表示逆序虚拟零部件中包含的原工序的数量，相关定义如下。

定义1紧密衔接逆序虚拟零部件。它包含的多道工序间存在着紧密衔接约束关系。如图3b中的逆序虚拟零部件RVC2和RVC3。

定义2非紧密衔接逆序虚拟零部件。它包含一道或多道具有线性次序约束的工序且它们之间都不存在紧密衔接约束关系。如图3b中的逆序虚拟零部件RVC1、RVC4和RVC5。

定义3叉点逆序虚拟零部件。它是指在逆序虚拟零部件有向图中直接与多个逆序虚拟零部件节点存在顺序约束关系的节点所对应的逆序虚拟零部件，即出度大于1的节点所对应的逆序虚拟零部件。如图3b中的逆序虚拟零部件RVC1和RVC2。

定义4根节点逆序虚拟零部件。它是指在逆序虚拟零部件有向图中只有直接后继的节点所对应的逆序虚拟零部件，即入度等于0的节点所对应的逆序虚拟零部件。如图3b中的逆序虚拟零部件RVC1。

定义5逆序虚拟零部件RVCi的子孙逆序虚拟零部件。它是指在逆序虚拟零部件有向图中以逆序虚拟零部件RVCi节点为根的子树中的所有节点所对应的逆序虚拟零部件。如图3b中逆序虚拟零部件RVC4和RVC5都是逆序虚拟零部件RVC2的子孙逆序虚拟零部件。本文规定逆序虚拟零部件RVCi的子孙逆序虚拟零部件不包含其本身。

定义6逆序虚拟零部件RVCi的工序数目No。

式中ni是非紧密衔接逆序虚拟零部件RVCi中包含的原工序数量。

基于上述定义，用改进的双亲孩子表示法表示图3b中的树状结构逆序虚拟零部件具体如表1所示。

表1 逆序虚拟零部件双亲孩子表示法示例

2.1.3 基于逆序虚拟零部件双亲孩子表示法的编码

目前，采用元启发式算法求解综合调度问题的研究较少，这是因为相比传统的车间调度问题，综合调度问题存在更加复杂的装配顺序约束关系，导致已有的各种编码方式失效[15]。本文在树状结构逆序虚拟零部件可视为由根节点不断延伸结果的思想指导下，提出一种基于逆序虚拟零部件双亲孩子表示法的编码方法，它能满足树状结构逆序虚拟零部件顺序约束关系，具体步骤如下：

步骤1基于逆序虚拟零部件双亲孩子表示法，通过双亲位置查找根节点(即双亲位置为0的逆序虚拟零部件所对应的节点)，将查找到根节点对应的逆序虚拟零部件对应的下标构成初始可调度逆序虚拟零部件集S。

步骤2从起始可调度逆序虚拟零部件集S中随机地选择一个下标号作为此时染色体的编码基因，同时更新对应的逆序虚拟零部件工序数目。更新工序数目的具体方法为：首先令对应的工序数目值减去1；然后判断此时其工序数目值是否变为0，若为0，则令该逆序虚拟零部件的双亲位置为其自身的下标值，同时对应的孩子逆序虚拟零部件的双亲位置值变为0。

步骤3转步骤1，再对新得到的可调度逆序零部件集S进行判断，若为空集，则终止；否则继续步骤2操作。

通过上述操作可得到一条完全满足树状结构逆序虚拟零部件顺序约束关系的染色体，图4为上述图3b中所示的树状结构逆序虚拟零部件有向图的染色体编码示意图。其中非紧密衔接逆序虚拟零部件下标号出现的次数等于其包含的原工序的数量，如其中只出现一次的下标1代表着非紧密衔接虚拟零部件RVC1所对应的唯一原工序P1；而每个紧密衔接逆序虚拟零部件下标号都只会出现一次，分别代表着对应紧密衔接虚拟零部件包含的所有工序，如下标3代表着紧密衔接逆序零部件RVC3所对应的原工序集P5和P9。

2.2 选择操作

常见的选择操作方法有锦标赛选择法、最佳个体保存法和轮盘赌选择法等。本文算法采用锦标赛选择法，同时辅以精英保留策略。

2.3 交叉操作

常见的交叉操作有单点交叉、多点交叉、均匀交叉和基于工件优先顺序的交叉等。为保证交叉后所生成的新的子代个体仍满足树状结构逆序虚拟零部件顺序约束关系，本文借鉴基于工件优先顺序的交叉的思想，提出一种基于叉点逆序虚拟零部件优先顺序的交叉方法。

设有两个父代染色体P1和P2，交叉产生的子代染色体分别为C1和C2，基于叉点逆序虚拟零部件的优先顺序交叉的具体操作步骤如下：

步骤1随机选择一个叉点逆序虚拟零部件并确定其所有子孙逆序虚拟零部件，进而将逆序虚拟零部件集分为两个非空的子集RVCS1和RVCS2，其中RVCS1包含所有子孙逆序虚拟零部件。特殊地，若不存在叉点虚拟零部件，则随机选择一个根节点逆序虚拟零部件代替叉点逆序虚拟零部件。

步骤2复制P1包含RVCS2中的逆序虚拟零部件下标基因到C1，P2包含RVCS2中的逆序虚拟零部件下标基因到C2，保留它们的位置。

步骤3复制P2包含RVCS1中的逆序虚拟零部件下标基因到C1，P1包含RVCS1中的逆序虚拟零部件下标基因到C2，保留它们的顺序。

以图3b所示的树状结构逆序虚拟零部件有向图为例，如图5所示为上述基于叉点逆序虚拟零部件的POX交叉算子的操作过程，其中选取的叉点逆序虚拟零部件为RVC2。

2.4 变异操作

常见的变异操作有互换变异、逆序变异、插入变异等。为保证变异后所生成的新的子代个体仍满足树状结构逆序虚拟零部件顺序约束关系，本文借鉴插入变异的思想，提出一种新的适应于紧密衔接综合调度问题的插入变异方法。

设有父代染色体P，变异产生的子代染色体为C，新的插入变异的具体操作步骤如下：

步骤1随机选择一个逆序虚拟零部件作为变异逆序虚拟零部件。

步骤2在变异的父代染色体P中确定变异虚拟零部件所有子孙逆序虚拟零部件下标基因的首位位置first和紧前逆序虚拟零部件基因的最末位位置last。特殊地，若不存在子孙逆序虚拟零部件，则first=length(Chromosome)+1，其中length(Chromosome)表示染色体的长度；若不存在紧前逆序虚拟零部件，则last=0。

步骤3在区间[last+1,first-1]随机确定所有变异虚拟零部件下标基因的位置，其他虚拟零部件下标基因顺序保持不变，同时判断能否得到一条新的不同于父代染色体P的染色体。

步骤4若能够得到一条新的不同于父代染色体P的染色体，则新得到的染色体即为变异产生的子代染色体C，否则，重复步骤1～步骤3，直至得到一条不同于父代染色体P的染色体C。

以图3b中所示的树状结构逆序虚拟零部件有向图为例，如图6所示为上述插入变异算子的操作过程。图中所示随机选取的变异逆序虚拟零部件为RVCS3，在区间[2,5]随机确定的变异逆序虚拟零部件基因位置为2。

2.5 考虑紧密衔接约束关系的解码

为了获得原紧密衔接综合调度问题的调度方案，同时结合本文编码的特点，本文分别从间接和直接两个角度设计了两种不同的基于插入式贪婪解码[24]的解码方法。它们的主体思路都是通过按照特定的染色体基因顺序进行解码来满足对应问题中工序间的先后顺序约束关系，同时又对紧密衔接逆序虚拟零部件对应的染色体基因进行特殊解码来满足对应问题中工序间的紧密衔接约束关系，进而保证它们所生成的调度方案的可行性。

2.5.1 基于主动逆序调度方案转化的解码

基于主动逆序调度方案转化的解码方法主要分为两步：首先，采用一种基于插入式贪婪解码的主动逆序调度解码方法，得到原问题的逆序紧密衔接综合调度问题的主动逆序调度方案；然后，通过一种转化方法，实现将主动逆序调度方案转化成原问题所对应的调度方案。该解码方法虽然无法保证生成原问题的主动调度方案，但是能保证生成不大于主动逆序调度方案最大完工时间的调度方案。

本文设计的基于插入式贪婪解码的主动逆序调度解码方法的具体步骤如下：

步骤1设定复杂产品各道工序的初始化预定最早开工时间值，若无特殊说明，则均为0。

步骤2按照从左到右的顺序，依次读取染色体上的逆序虚拟零部件RVCi的下标号。

步骤3判断RVCi是否为紧密衔接逆序虚拟零部件，若不是，则转步骤4，否则，转步骤5。

步骤4若RVCi为非紧密衔接逆序虚拟零部件，计算相应工序的实际开工时间和实际完工时间，同时更新相关信息。

设对应的工序为oi，oi的预定最早开工时间为si，oi的加工设备为Mk，加工时间为tik，实际开工时间为Si，实际完工时间为Ci。相关计算步骤如下：

(1)从前向后依次计算并检查设备Mk上的空闲时间区域[ts,tc](在后续中如无特殊说明，默认为[ts,+)属于[ts,tc]的特殊情况)，如果max(si,ts)+tik≤tc，则令Si=max(si,ts)。

(2)计算工序oi实际完工时间Ci=Si+tik。

(3)更新设备Mk的空闲区域，同时，用Ci与oi紧后工序or的预定最早开工时间进行比较，选择较大的作为工序or新的预定最早开工时间。

步骤5若RVCi为紧密衔接逆序虚拟零部件，计算相应一系列工序的实际开工时间和实际完工时间，同时更新相关信息。

设对应的一系列工序为oi1,…,oii′，且它们的先后顺序满足它们之间的顺序约束关系，对应的加工设备为Mk1,…,Mki′，对应的预定最早开工时间为si1,…,sii′，对应的加工时间为ti1,…,tii′，对应的实际开工时间为Si1,…,Sii′，对应的实际完工时间为Ci1,…,Cii′。相关计算步骤如下：

(1)确定在不考虑加工设备状况的情况下该系列工序oi1,…,oii′可行的预定最早开工时间ssi1,…,ssii′和预定最早完工时间cci1,…,ccii′。具体操作如下：

1)由于工序oi1,…,oii′在逆序扩展加工工艺树中所对应的部分仍为树状结构，因此，可视为一个独立的加工工艺树，且根节点对应的工序为oi1。分别将工序oi1,…,oii′视为叶节点，计算它们在相应的加工工艺树中的路径长度[25]，且分别记为pi1,…,pii′。

2)通过公式f(j)=max(si1+pip,sij)+tij，其中pip表示工序oij的紧前工序oip路径长度，得到f(1),…,f(i′)，实际上f(j)表示在满足工序oij预定最早开工时间的条件下工序oij的完工时间。

3)令ccij′=max(f(j))，ssij′=ccij′-tij′，同时结合工序oi1,…,oii′之间的紧密衔接约束关系的特点，依次计算出其他剩余工序可行的预定最早开工时间和预定最早完工时间。

1)按照由前向后的顺序，依次计算并检查设备Mk1上的空闲时间区域[ts,tc]，如果max(ssi1,ts)+ti1≤tc，则表示在不考虑其他工序的情况下工序oi1可安排在该空闲时间区域加工；否则，检查下一个区域，直至寻找到一个可安排工序oi1加工的空闲时间区域。

3)在当前寻找到可安排工序oi1加工的空闲时间区域的条件下，在工序oi2,…,oii′的加工设备Mk2,…,Mki′上从前向后依次计算并检查相应设备上的空闲时间区域，判断相应的工序是否可安排在该空闲时间区域。假设空闲时间区域为[tsj,tcj]，工序oij可安排在空闲时间区域[tsj,tcj]需满足的条件为：max(ssij,tsj)+tij≤tcj&tsj≤lsij&tcj≥ecij。

(3)确定工序oi1,…,oii′的实际开工时间为Si1,…,Sii′和实际完工时间为Ci1,…,Cii′，同时更新相关设备和工序的预定最早开工时间。具体操作如下：

2)通过公式Sij=esij+d,Cij=ecij+d，确定工序oi1,…,oii′的实际开工时间Si1,…,Sii′和实际完工时间Ci1,…,Cii′。

3)更新相应设备Mk1,…,Mki′的空闲区域，同时，依次通过Ci1,…,Cii′与其对应紧后工序的预定最早开工时间的比较来更新它们预定最早开工时间。

步骤6判断是否读取完毕，若读取完毕，则结束，否则转步骤2。

通过上述主动逆序调度解码方法能将一条基于逆序虚拟零部件双亲孩子表示法编码的染色体解码成一个原问题所对应的逆序紧密衔接综合调度问题的主动逆序调度方案。为得到原紧密衔接综合调度问题的调度方案，本文在上述主动逆序解码结果的基础上，又提出一种相应的转化方法。为便于描述，本文将主动逆序调度方案进行逆序调整[14]后所对应的调度方案称为“反转调度方案”。转化方法的具体步骤如下：

步骤1计算存在紧密衔接约束关系的工序在正序调度方案中的实际开工时间和实际完工时间。通过公式PSij=RMakespan-Cij,PCij=PSij+tij,∀oij∈OSi，其中：PSij和PCij是指工序oij在正序调度方案中的实际开工时间和实际完工时间；RMakespan是指主动逆序调度方案的最大完工时间；OSi是指所有存在紧密衔接约束关系的工序集，计算出它们在正序调度方案中的实际开工时间和实际完工时间。

步骤2分别更新相关加工设备的空闲区域和工序的预定最早开工时间。相关计算步骤如下：

(1)根据步骤1得到的工序实际开工时间和实际完工时间，更新它们相应加工设备的空闲区域。

(2)根据步骤1得到的工序实际完工时间，更新在原问题的扩展加工工艺树中它们各自紧后工序的预定最早开工时间。具体为：用工序的实际完工时间与它的唯一紧后工序的预定最早开工时间进行比较，选择较大的值作为它的紧后工序新的预定最早开工时间。

步骤3对不存在紧密衔接约束关系的工序执行贪婪解码操作，确定它们在正序调度方案中的实际开工时间和实际完工时间。相关计算步骤如下：

(1)设定不存在紧密衔接约束关系的工序的初始化预定最早开工时间值，若无特殊说明，则均为0。

(2)正向标准化主动逆序调度解码获得的工序染色体。采用文献[26]中的正向标准化方法，按照工序的完工时间进行正向标准化。

(3)按照从右到左的顺序，依次读取正向标准化后的工序染色体上的基因genei，设对应的工序为oi，同时判断oi是否为紧密衔接工序，若是，则跳过，否则，转步骤(4)。

(4)若oi是非紧密衔接工序，计算该工序的实际开工时间和实际完工时间，同时更新相关信息。

设oi的预定最早开工时间为si，oi的加工设备为Mk，加工时间为tik，实际开工时间为Si，实际完工时间为Ci。具体操作如下：

1)按照由前向后的顺序，依次计算并检查设备Mk上的空闲时间区域[ts,tc]，如果max(si,ts)+tik≤tc，则令Si=max(si,ts)；否则，检查下一个区域，直至寻找到一个可安排工序oi1加工的空闲时间区域。

2)计算工序oi实际完工时间Ci=Si+tik。

3)更新设备Mk的空闲区域，同时，用Ci与oi正序紧后工序op的预定最早开工时间进行比较，选择较大的作为工序op新的预定开工时间。

(5)判断读取是否完毕，若读取完毕，则结束，否则转步骤(3)。

需要说明的是：通过上述转化方法虽然无法保证生成原问题的主动调度解，但是所得到的调度方案的最大完工时间值不大于转化前主动逆序调度方案的最大完工时间值，甚至有可能进一步减少。原因在于：①“反转调度方案”与主动逆序调度方案在每台加工设备上的工序加工顺序相反，并且拥有相同的关键路径和完工时间；②一方面该转化方法在保持存在紧密衔接约束关系的工序在正序调度方案中与“反转调度方案”位置相同的同时，另一方面又通过贪婪解码算法左移“反转调度方案”中不存在紧密衔接约束关系的工序。因此，转化后生成的调度方案能保证调度方案的最大完工时间值不增加，并有进一步减少的可能。

2.5.2 基于插入式贪婪解码的主动解码

按照文献[14]提出的方法对获得的逆序调度方案进行逆序调整便可得到原问题的调度方案(即“反转调度方案”)，然而从反转调度方案的甘特图中不难发现，除关键路径上的工序外，其他工序的开工时间并非都是其能开工的最早时间。因此，为避免本文算法的最终调度结果也出现上述问题，本文又提出一种能保证生成原紧密衔接综合调度问题的主动调度的解码方法。该主动解码操作与上述基于插入式贪婪解码的主动逆序调度解码方法大体相同，主要不同之处在于步骤2和步骤5的(1)，它们在原紧密衔接综合调度问题的主动解码方法中的具体操作如下：

步骤2：按照从右到左的顺序，依次读取染色体上的正序虚拟零部件PVCi的下标号(称正序虚拟零部件仅为了与上述逆序虚拟零部件区分开)。

步骤5的(1)：确定在不考虑加工设备状况的情况下紧密衔接正序虚拟零部件PVCi对应的一系列工序oi1,…,oii′可行的预定最早开工时间ssi1,…,ssii′和预定最早完工时间cci1,…,ccii′。此外，需要说明的是：工序oi1,…,oii′顺序是满足它们在原问题中的紧密衔接约束关系的。具体操作如下：

1)由于工序oi1,…,oii′在原问题的扩展加工工艺树中所对应的部分仍为树状结构，仍可视为一个独立的加工工艺树，且根节点对应的工序为oii′。分别将工序oi1,…,oii′视为叶节点，计算它们在相应的加工工艺树中的路径长度，且分别记为pi1,…,pii′。

2)通过公式dpij=max(pij′)-pij,spij=pij+sij,msp=max(spij),ssij=msp-pij,ccij=ssij+tij，∀j∈{1,2,…,i′},∀j′∈{1,2,…,i′}，依次计算出工序oi1,…,oii′可行的预定最早开工时间和最早完工时间。

3 实例测试

众所周知，针对传统的作业车间调度问题算法的研究可直接采用已有的国际通用基准实例进行测试，然而目前复杂产品综合调度问题尚未建立起基准测试实例，更不用说紧密衔接综合调度问题基准测试实例。为验证本文所提算法的性能，选用目前发现的相关文献中的测试实例进行测试。由于本文在基于逆序虚拟零部件双亲孩子表示法的编码方法的基础上，提出了基于主动逆序调度方案转化的解码方法和基于插入式贪婪解码的主动解码方法。虽然这两种解码方法都能求解出原紧密衔接综合调度解的解码方法，但是为了更好地发挥它们各自的优势，并提高它们对应算法的性能，在下面的实例测试中，本文针对它们分别采用不同的策略进行处理。由于基于主动逆序调度方案转化的解码方法实际上在每个解码过程中使用了两次贪婪解码方法，这无疑增加了计算时间，结合该方法具有不增加调度优化目标的优点，本文在测试过程中只针对经过不断迭代最终获得最优主动逆序调度方案进行转化操作，以求在更加短的时间内获得原问题满意的解。而基于插入式贪婪解码的主动解码方法不存在上述基于主动逆序调度方案转化的解码方法需要两次解码的问题，因此本文在下面测试过程中对于种群中的每个个体都使用该主动解码方法直接生成原问题的主动调度。

本文两种算法是在Win7系统下采用MATLAB语言编程实现，运行的计算机中央处理器的主频为3.40 GHz，内存为8.00 GB，对下述每个实例都各自独立运行求解10次。算法的相关参数设置相同，具体如下：种群规模大小为100，最大迭代次数为50，交叉概率为0.9，变异概率为0.1。

3.1 实例1

本实例来源于文献[14]，它实际上是一个严格意义上的存在非单一紧前工序紧密衔接约束关系的紧密衔接综合调度问题。图2所示即为其逆序扩展加工工艺树，通过剪枝查找操作后建立的逆序虚拟零部件双亲孩子表示法如表1所示。分别采用本文两种算法对该实例进行求解。基于主动逆序调度方案转化的遗传算法在求解的10次过程中，平均完工时间为19且最优解也为19，平均用时为2.359 s，其中一个调度结果如图7所示。基于插入式贪婪解码的遗传算法在求解的10次过程中，平均完工时间也为19且最优解也为19，平均用时为2.48 s，其中一个调度结果如图8所示。文献[14]提出的基于逆序信号驱动的紧密衔接综合调度算法求得的结果为19，相应的调度结果如图9所示。显然，本文两种算法都能得到与基于逆序信号驱动的紧密衔接综合调度算法相同的结果，且平均用时不超过3 s，因此，本实例测试结果表明本文算法的有效性。

3.2 实例2

本实例来源于文献[20]，它实际上是一个严格意义上存在单一紧前工序紧密衔接约束关系的多复杂产品紧密衔接综合调度问题。通过剪枝查找操作后建立的逆序虚拟零部件双亲孩子表示法如表2所示。分别采用本文两种算法对该实例进行求解。基于主动逆序调度方案转化的遗传算法在求解的10次过程中，平均完工时间为41，且最优解也为41，平均用时为3.924 s，其中一个调度结果如图10所示。基于插入式贪婪解码的遗传算法在求解的10次过程中，平均完工时间也为41，且最优解也为41，平均用时为4.247 s，其中一个调度结果如图11所示。将本文两种算法的求解结果与其他文献算法的求得结果进行比较，文献[6]中算法的求解结果为44，相应的调度结果如图12所示，文献[20]中算法的求解结果为46，相应的调度结果如图13所示。显然，本文两种算法的求解结果都优于上述文献中算法的求解结果，且平均用时不超过5 s，因此，本实例测试结果表明本文算法的有效性和优越性。

表2 逆序虚拟零部件双亲孩子表示法示例

3.3 实例3

本实例来源于文献[13]，它实际上是一个严格意义上存在单一紧前工序紧密衔接约束关系的多层紧密衔接综合调度问题。通过剪枝查找操作后建立的逆序虚拟零部件双亲孩子表示法如表3所示。分别采用本文两种算法对该实例进行求解。基于主动逆序调度方案转化的解码方法的遗传算法在求解的10次过程中，平均完工时间为26，且最优解也为26，平均用时为5.683 s，其中一个调度结果如图14所示。基于插入式贪婪解码的遗传算法在求解的10次过程中，平均完工时间为27且最优解也为27，平均用时为6.191 s，其中一个调度结果如图15所示。将本文两种算法的求解结果与文献[13]中算法的求得结果进行比较，而文献[13]中算法的求解结果为28，相应的调度结果如图16所示。显然，本文两种算法的求解结果都优于上述文献中算法的求解结果，且平均用时不超过7 s，因此，本实例测试结果表明本文算法的有效性和优越性。

表3 逆序虚拟零部件双亲孩子表示法示例

3.4 实例4

本实例来源于文献[14]，它是比实例3更加复杂的存在单一紧前工序紧密衔接约束关系的多层紧密衔接综合调度问题。通过剪枝查找操作后建立的逆序虚拟零部件双亲孩子表示法如表4所示。针对本实例，分别采用本文两种不同解码方法的遗传算法对该实例进行求解，基于主动逆序调度方案转化的遗传算法在求解的10次过程中，平均完工时间为28，且最优解也为28，平均用时为5.683 s，其中一个调度结果如图17所示。基于插入式贪婪解码的遗传算法在求解的10次过程中，求解平均完工时间为28，且获得最优解也为28，并且每次的平均用时为6.848 s，其中一个调度结果如图18所示。将本文算法的求解结果与其他文献算法的求得结果进行比较，文献[13]中算法的求解结果为31，相应的调度结果如图19所示。文献[14]中算法的求解结果为29，相应的调度结果如图20所示，同时不难看出工序A2、A18、A19和A12等都不是它们能开工的最早时间，即该调度方案为非主动调度。显然，本文算法的求解结果优于上述文献中算法的求解结果，且每次的平均用时不超过7 s，此外，本文所提出的基于插入式贪婪解码的遗传算法能保证生成主动调度。综上所述，本实例测试结果也表明本文算法的有效性和优越性。

表4 逆序虚拟零部件双亲孩子表示法示例

4 结束语

本文将单一紧前工序的紧密衔接综合调度问题和非单一紧前工序的紧密衔接综合调度问题统一进行处理，结合问题之间的共性，从逆序调度的角度提出了基于逆序虚拟零部件的遗传算法，提高了算法的通用性。相关结论如下：

(1)通过对复杂产品逆序扩展加工工艺树的有向图进行剪枝查找操作，达到了降低层次、简化约束的目的，同时建立了逆序虚拟零部件双亲孩子表示法，并提出了相应的编码方法，为后续问题的解决奠定了坚实的基础。

(2)针对基于逆序虚拟零部件双亲孩子表示法，设计出了相应的能满足复杂产品逆序虚拟零部件顺序约束的遗传算子，并提出了两种各具特色的解码方法，保证了生成原问题的可行解，提高了算法的求解速度和质量。

(3)通过对已有文献中相关实例的测试，验证了本文算法求解紧密衔接综合调度问题的有效性和优越性。

本文所提出的遗传算法为解决紧密衔接综合调度问题提供一种新的解决方法，且具有较高的通用性和有效性，同时也对进一步深入研究紧密衔接综合调度问题有一定的理论和实际意义。此外，也为遗传算法求解其他特殊综合调度问题提供了一定的借鉴价值，如存在多工序同时结束的综合调度问题、存在多设备工序的综合调度问题等。