常规混合流水车间调度问题的等价变换

苏志雄，伊俊敏

SU Zhi-xiong, YI Jun-min

（厦门理工学院 管理学院，厦门 361024）

0 引言

混合流水车间（Hybrid Flow Shop, HFS）调度问题是在流水车间（Flow Shop, FS）调度问题的基础上发展起来的，其特点是所有阶段或部分阶段上存在并行设备。常规HFS调度问题可以描述为n个工件要在s 个阶段的流水车间上加工，其中阶段k具有M(k)个同速平行机、且至少有一个阶段存在两台以上的平行机，在满足一系列基本假设和约束条件的基础上去寻找一个调度解使得最大完工时间（makespan）最小。虽然不同的HFS问题不能完全满足常规问题的所有假设和约束，但是也只是在设备加工环境、加工约束和特征、优化准则等方面存在较小的差异。常规HFS问题作为HFS调度问题的“模板”，其研究成果可以为更加复杂的实际调度问题研究提供基础，受到了学术界和产业界的广泛关注。

由于常规HFS调度问题的NP难特性[1]，精确算法[2,3]只能求解很小规模的问题。对于近似求解方法来说，启发式算法[4,5]求解快速，然而其求解质量还有较大的改进空间；元启发式算法[6～10]求解质量较高，通常需要更多的计算资源，难以应用于大规模或者实时性要求高的问题。从已有研究来看，现有的调度算法在求解质量、求解效率方面仍存在一定的不足，其主要原因在于算法设计的理论基础不够完善，现有的调度算法尚未很好地融入领域知识（domain knowledge）。此外，文献[7]试图通过反例来说明常规HFS问题不具备加工可逆性：对于一个给定的工件排列次序（初始阶段），采用正序、逆序调度方法可以获得不同的makespan值；然而在给定工件排列次序的情况下，可以生成不同的工件设备指派方案，进而可以得到一系列不同的调度解，该结论并不严谨。因此，本文进一步对常规HFS调度问题的本质特征展开研究，首先通过逆序变换定义了常规HFS调度问题的逆序问题，然后从数学角度证明了两者之间的等价关系，最后给出了一种基于逆序变换进行问题求解的方法，旨在为后续的研究提供理论依据。

1 数学模型

1.1 符号定义

为了叙述方便，引入下列符号：

m为设备编号；

M(k)为阶段k上的平行机数；

(j,k)为工件j在第k个阶段的操作；

pjk为工件j在阶段k的加工时间；

tjk,cjk为工件j在阶段k的开工时间、完工时间；

Nkm为阶段k上的设备m所加工的操作集合；

Ωk为阶段k上的工件设备指派方案集合，集合的元满足以下两个条件：

Π 为对于给定的工件设备指派方案ω，可行的工件加工顺序方案集合；

S为可行调度解，其集合记为Ψ，不妨记其最大完工时间记为Cmax(S)。

1.2 析取图模型

对于给定的工件设备指派方案ω，常规HFS调度问题可以用赋权析取图来表示：是节点集，其中节点(j,k)表示工件j在第k个阶段的操作，而“0”与“*”分别表示整个加工开始的起点和代表全部加工结束的终点；A是合取弧的集合，反映了同一工件的不同操作之间的先后关系，用单向实线来表示；E是析取弧的集合，反映了同一设备上不同工件之间的加工先后关系，同一阶段的任意两个工件之间用双向虚线来连接；w 是有向图的权重，其中节点(j,k)的权重为pjk，而节点“0”、“*”和所有弧的权重都为0。

在上述描述中，调度的过程就是将双向箭头用单向箭头代替进而得到E′，使G成为一个无回路的单向图亦即确定了一个可行的工件加工顺序方案，该图可以简记为在满足时序约束、资源约束等的基础上，确定工件的开工时间，进而生成一个可行调度解S。例如，对于一个7个工件3个阶段的常规HFS调度问题，各阶段上的平行机数分别为2、2、3；已知工件的加工顺序方案，其中11=(1,2,3)，那么对应的如图1所示。由于的关键路径长度就是对应工件加工顺序方案的最优makespan值，因此在所有的中寻找一个具有最小关键路径的无回路单向图就是常规HFS调度问题，即

图1 实例的图表示

2 等价逆序变换

定义1：对于一个给定的具有n个工件的常规HFS调度问题，如果另外一个常规HFS问题满足以下两个条件：

对于任意的常规HFS调度问题（原问题），可以根据定义1的逆序变换得到相应的逆序问题。为了证明逆序变换的等价性，下面给出了优化问题的等价性定义。

定义2：如果两个优化问题满足：1）存在一个问题的可行解集合到另外一个问题的可行解集合的映射（不一定是“一对一”的情形）；2）任意一个可行解及其“像”具有相同的目标函数值；那么这两个优化问题是等价的。

引理1：对于原问题的任意一个可行调度解S，记其工件加工顺序方案为，那么至少存在逆序问题的一个可行调度解，其工件加工顺序方案构造如下：阶段上的设备m 所加工的工件有序集为且这两个调度解具有相同的makespan值。

证明：对于原问题的任意一个可行调度解S，亦即确定了一个无回路单向图且调度解的makespan值大于或等于的关键路径长度。下面，分两种情况进行讨论：

2）如果该调度解的makespan值Cmax(S)大于的关键路径长度，可以给出一种逆序问题调度解的构造方法：首先，对于逆序问题的工件加工顺序方案根据递推公式(1)计算工件的开工时间并记其最后阶段s上完工时间最迟的工件为j'；然后，令根据此种方法得到的可行调度解与原问题的可行调度解之间具有相同的makespan值。

综上所述，引理得证。

定理1：原问题及其逆序问题是等价的。

证明：1）令原问题及其逆序问题的可行解集合分别为A、B，现在构造一个从集合A到集合B的映射：

由定义2，定理得证。

并且当节点(j,k)在关键路径上的时候，等号成立。

由上述两点，定理得证。

定理3：对称定理：逆序问题的逆序是原问题。

3 逆序调度方法

由于常规混合流水车间调度问题及其逆序问题的等价性，可以通过原问题的任意调度算法来求解逆序问题，然后经过解的转化来获得原问题的调度解。下面给出此种逆序调度方法的求解框架：

Step1：逆序变换。对于给定的常规HFS调度问题，根据式(3)、式(4)可以确定逆序问题的相关参数（各阶段的平行机数和加工时间）。

Step2：利用原调度算法求解逆序问题。

Step3：将求得的逆序调度解“映射”回原来的解空间，得到原问题的调度解。即根据引理1，由逆序调度解的加工顺序方案可以得到原问题的一个加工顺序方案π，然后根据公式(1)来确定工件的开工时间tjk，进而获得原问题的完整调度解。

下面，以启发式算法求解一个10个工件5个阶段的算例j10c5a5[2]为例来进行说明。文献[4]通过仿真实验说明了采用第2种设备指派规则的NEH算法取得了最好的效果，不妨记此种算法为NF，相应的逆序调度算法记为NB。对于该算例，NF算法在步骤1求得工件加工优先级顺序jobOrder=[5 9 3 8 10 1 2 6 7 4]，进一步通过设备指派生成完整的调度解并得到Cmax=126；而通过NB算法求得等价逆序问题的jobOrder= [4 9 3 8 10 7 6 2 1 5]，Cmax=122，并将求得的逆序调度解“映射”回原来的解空间可以得到原问题的解，恰好该调度解为最优解。

4 仿真实验

以Carlier和Néron提出的77个Benchmark算例[2]作为测试数据，并根据求解难度将其分成两组：53个易解算例、24个难解算例[3]。本文的算法采用MATLAB语言编写，运行环境为Win8.1、i3-4130(3.40G)/4G的台式机。为了评价算法的有效性，采用以下3种指标：百分比偏差PD，运行时间CPU，最优比率（求得最优解的算例个数占该算例集算例总数的比率）。

表1 三种算法的计算结果比较

对于这两组算例，分别采用NF、NB以及正逆序相结合的求解算法（记为NFB）独立运行1次，对计算结果进行总结如表1所示。由表1可以看出，NF与NB的平均运行时间非常接近；从平均偏差、最优比率来看，NF优于NB。实际上，由于算例集的规模有限且不具有对称性，不能以此来判断算法的优劣；根据求解结果可以发现，对于不同的算例NF与NB各具优势。与NF、NB相比，从平均偏差、最优比率这两个指标来看，NFB均有较大幅度的提高。虽然NFB需要付出接近2倍的时间代价才可以获得更好的求解质量，但是其平均运行时间也仅为0.0023s，具有满足实际需求的计算效率。

5 结束语

本文针对常规混合流水车间调度问题的可逆性展开研究，给出了逆序变换、逆序问题的定义，并从数学角度证明了逆序变换的等价性。在此基础上，给出了一种逆序调度方法的求解框架，将问题求解方法的数量扩大了一倍，即对于任意已有的调度算法，均可以得到相应的逆序调度算法。特别是对于启发式方法，通过求解原问题及其逆序问题，只需花费较小的时间代价就可能获得更好的调度解。然而，在什么条件下去求解等价逆序问题更具优势，需要进一步去探讨。

[1] Gupta J N D.Two-stage hybrid flowshop scheduling problem [J]. Journal of the Operational Research Society,1988, 39(4):359-364.

[2] Carlier J, Néron E.An exact method for solving the multiprocessor flow-shop [J].RAIRO - Operations Research,2000, 34(1):1-25.

[3] Néron E, Baptiste P, Gupta J N D.Solving hybrid flow shop problem using energetic reasoning and global operations[J]. Omega-International Journal of Management Science,2001, 29(6): 501-511.

[4] Guinet A,Solomon M. Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time[J].International Journal of Production Research,1996,34(6):1643-1654.

[5] 屈国强.瓶颈指向的启发式算法求解混合流水车间调度问题 [J].信息与控制,2012,41(4):514-521,528.

[6] Nowicki E,Smutnicki C.The flow shop with parallel machines: A tabu search approach[J].European Journal of Operational Research,1998,106(2-3):226-253.

[7] Pan Q K, Wang L, Li J Q, etc.A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization[J].Omega-International Journal of Management Science,2014,45:42-56.

[8] Chung T P, Liao C J. An immunoglobulin-based artificial immune system for solving the hybrid flow shop problem[J].Applied Soft Computing,2013,13(8):3729-3736.

[9] Li J Q,Pan Q K,Wang F T.A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem[J].Applied Soft Computing,2014,24:63-77.

[10] Cui Z,Gu X S.An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems[J]. Neurocomputing,2015,148(1):248-259.

[11] Pinedo M.Scheduling theory,algorithms, and system[M].2nd ed. New Jersey:Prentice Hall,2002:133.