基于博弈论的虚拟制造网络车间调度优化方法

随着全球供应链的迅速发展和广泛应用，越来越多的中小企业联合构建虚拟制造网络(virtual manufacturing network, VMN)来生产单个企业无法完成的特定复杂产品[1]。构建及运行VMN的关键问题之一是对生产过程进行科学管理，以较高的柔性和效率满足客户个性化需求。在作业调度决策过程中，需要考虑顾客和制造商的利益：来自不同顾客的订单都应尽快得以满足；VMN应以最高的效率和最低的成本完成所有加工任务。然而顾客和制造商双方利益有时互相促进，有时互相冲突，因此有必要开发一种具有协调机制的作业调度方法以均衡双方利益。

博弈论是平衡多方利益的有效工具之一，近年来许多学者将之用于作业调度领域。TAYEB等[2]将博弈论原理用于带机器故障维修计划的车间作业调度问题。LI等[3]引入纳什均衡方法来解决集成工艺规划与调度问题，并设计了混合遗传算法。ZHOU等[4]构建了网络化制造环境下作业调度问题的博弈论数学模型，并开发了基于遗传算法的求解算法来求解该数学模型。周光辉等[5-6]针对服务型制造车间关键任务调度问题和服务型制造系统外包任务分配决策问题，开发了基于博弈论的Stackelberg模型。SUN等[7]、ZHANG等[8]应用非合作博弈理论，建立了动态生产环境下柔性作业车间调度问题的调度博弈模型。但这些研究都忽略了顾客和制造商双方利益的均衡。本文针对虚拟制造网络的车间调度问题，利用博弈论的纳什均衡策略使各顾客和制造商VMN之间的利益达到均衡。

1 虚拟制造网络车间调度问题描述

VMN车间调度问题可以表述如下：一个VMN由多个企业组成，每个企业提供不少于一台的加工设备用于共享。这些共享的设备记作Mj (j = 0，1，…，m-1)，其中，m为设备的台数。该VMN需要加工一批来自不同客户订单的工件，记作Ji (i=0，1，…，n-1)，其中，n为工件的个数。工件Ji包含hi道工序，记作Oi,l(l=0，1，…，hi-1)。每个工件的工序必须按照事先约定的顺序进行操作。工序Oi,l有ki,l个加工设备可供选择，工序Oi,l的候选加工设备集合记作Mi,l。工序Oi,l在其第q个候选加工设备上的加工时间记作pi,l,q(q=0，1，…，ki,l-1)。工序Oi,l的最小加工时间记作pi,l，pi,l=min(pi,l,q)。本文假设VMN中所有加工设备都已准备就绪且不发生故障。

2 虚拟制造网络车间调度博弈模型

本文采用博弈论思想，将上述VMN车间调度问题建模为一个包含n+1个参与者的非合作博弈模型。该模型表述为三元组G=(n+1, S, U)，其中， S为所有参与者的行动策略集，S={s0，s1，…， sn}，st表示第t个参与者的策略，t=0，1，…，n；U为所有参与者的收益函数集，U={u0，u1，…，un}，ur为第r个参与者的收益函数，r=0，1，…，n。

2.1 参与者

在该博弈模型中，VMN及需要加工的n个工件都视为博弈的参与者。VMN决定工件的加工顺序，每个工件选择自己的加工路径。

2.2 行动策略

该模型包含行动策略不同的两类参与者：工件及整个制造系统VMN。加工工件Ji的策略 si=(mi,1,mi,2,…,mi,hi)，其中，mi,l∈Mi,l。假设某工件有3道工序，且每道工序有3台可供选择的机器，那么该工件可能的行动策略有27个。VMN的策略sn = (l1，l2，…，ln)表示n个加工工件之间的相对加工顺序关系。

2.3 收益函数

博弈过程中，每个参与者根据自己的策略采取行动，从而获得收益，并期望最大化自身利益。加工工件的目标是希望以最快的速度完成加工，VMN的目标是以最短的时间完成所有工件。

加工工件的流程时间越短，收益越大，故加工工件收益函数设计为加工工件流程时间的递减函数，即加工工件Ji的收益函数为

式中，fi为工件Ji的流程时间。

当工件Ji的流程时间fi达到其下界

即加工过程中没有任何等待时，它获得最大收益。

VMN完成所有工件所耗时间makespan越短，收益就越大，故其收益函数设计为makespan的递减函数，即VMN的收益函数为

其中，ms表示makespan，ms=max(fi)。如果ms达到其下界 m

fi)，那么VMN获得最大收益。

每个参与者的收益不仅与自身的行动策略有关，还受其他参与者行动策略的影响。有时它们之间的相互影响是积极的，若所有工件都能以最短的流程时间完成加工，则VMN的makespan最短。有时它们之间的相互影响是消极的，某个工件在追求自身的最短流程时间时，可能要延迟其他工件的加工，从而引起其他工件的流程时间延长，有时甚至导致整个VMN的makespan延长。所以，需要找到所有参与者利益的平衡点。

2.4 纳什均衡

对于本文的n+1非合作博弈模型而言，一个纳什均衡就是一个n+1重策略。如果每个工件能在不延长makespan的情况下，都能以最短的流程时间完工，那么这时每个参与者所采取的行动策略就为该博弈模型的一个纳什均衡

此时所有参与者，谁也不愿意再改变其行动策略，因为谁偏离了其自身的最佳策略，所获得的收益不会得以增加，即满足下式：

本文的n+1非合作博弈模型不一定存在纯纳什均衡。为了解决此问题，本文定义使得每个参与者都获得最大收益的解为理想纳什均衡。很明显，如果博弈模型满足

则该博弈模型存在理想纳什均衡，反之亦然。

式(4)是个极强条件，大多数调度问题都不具备该性质。本文针对不存在理想纳什均衡的博弈模型定义一个解与理想纳什均衡之间的距离：

可见，使得D越小的解越优。本文把具有最小D的解称为D最小纳什均衡。如果一个解是理想纳什均衡，那么它对应的D为0。

由此，本文将调度问题转化为寻找D最小纳什均衡问题。下一小节将具体阐述利用遗传算法求解D最小纳什均衡。在这此前，通过一个例子来理解本文的博弈模型。

表1给出的调度实例考察了一个包含3个加工机器的VMN(假设时间单位为min)。现有3个工件需要安排加工，工件J0只要完成工序O0,0和O0,1就可以交付。由于工序O0,0有2台可选加工机器，工序O0,1有3台可选加工机器，所以工件J0有6种不同的加工路径策略。同理，工件J1有12种加工路径策略，工件J2有6种加工路径策略。3个工件有3！种不同加工顺序关系，所以一共有6×12×6×6=2 592种可能的调度方案。该调度实例对应的博弈模型有4个参与者，一共有2 592种不同的行动策略组合。在不同的行动策略组合下，4个参与者可能得到不同的收益。表2比较了2个不同行动策略组合下的各参与者收益情况。由表2发现，策略S1和S2的区别在于：根据策略S1，工序O2,0在机器M2上加工，而根据策略S2，工序O2,0在机器M0上加工；另外，3个工件加工顺序也不同。不难发现，策略S2是一个纳什均衡，而S1不是。

3 基于遗传算法的D最小纳什均衡求解算法

本文设计了基于遗传算法的优化算法来寻找博弈模型的D最小纳什均衡。算法流程如下：

(1)设定算法的参数。如果式(4)成立，则该实例存在理想纳什均衡，输出理想纳什均衡，算法终止；否则该实例不存在理想纳什均衡，进入下一步骤。

(2)随机生成初始种群，评估每个个体的适合度。

(3)通过各种遗传操作，如选择、变异和交叉，由当前种群演变成新一代种群。

(4)判断本次迭代是否满足终止条件即是否达到一定的迭代次数。如果满足条件，则算法终止，最佳个体即为所求；否则，转到步骤(3)，进入下一次迭代。

由于篇幅有限，仅侧重于编码与解码机制以及适应度函数的讨论。

3.1 编码与解码机制

编码是将调度问题可行解描述为遗传算法“染色体”的过程。“染色体”包含的调度问题可行解的信息就是博弈模型中每个参与者的行动策略。编码设计中，一方面需要考虑如何在染色体中完整包含这些信息，另一方面还需要尽量以紧凑的方式表达这些信息，以减少存储空间开销，同时还要方便遗传算法在进化过程中对染色体进行的各种遗传算子操作。

假设调度问题包括n个工件，则每个染色体被设计成n+1个部分。前n个部分对应n个工件的行动策略，即工件的各道工序所选择的加工机器。最后一个部分对应VMN，该部分染色体决定了所有工件的加工顺序。以表1中的实例为例，((1,0), (1,2,0), (2,0), (0,2,1))就是一个染色体。该染色体由4个部分组成。第1部分(1,0)是第1个工件J0的行动策略，它表达的意思是该工件的第1道工序O0,0在其候选加工设备集合中的机器M2上加工；该工件的第2道工序O0,1在其候选加工设备集合中的机器M0上加工。第2部分(1,2,0)是第2个工件J1的行动策略，它表达的意思是该工件的第1道工序O1,0在其候选加工设备集合中的机器M1上加工；该工件的第2道工序O1,1在其候选加工设备集合中的机器M2上加工；该工件的第3道工序O1,2在其候选加工设备集合中的机器M1上加工。第3部分(2,0)是第3个工件J2的行动策略。它表达的意思是该工件的第1道工序O2,0在其候选加工设备集合中的机器M2上加工；该工件的第2道工序O2,1在其候选加工设备集合中的机器M0上加工。最后一部分(0,2,1)是VMN给各个工件排序的策略，它表达的意思是第1个工件最先加工，其次是第3个工件，最后加工第2个工件。该编码机制的优点在于保持了染色体的线性表达，也保证了各种基本变异和交叉操作能很容易地在染色体上实现而不会产生非法解。

解码是编码的逆过程，把按照规则编写的染色体翻译成为可行的调度方案。以表1的实例来说明如何将染色体((1,0), (1,2,0), (2,0), (0,2,1))解码为活动调度方案。第1个工件J0的第1道工序O0,0在M2上加工并且在加工顺序中处于第1位，所以工序O0,0在0～4 min内在M2上加工。然后，J0的第2道工序O0,1在4～6 min内在M0上加工。第2个工件J1的第1道工序O1,0选择在M1上加工，由于此时M1上没有其他工件抢占机器，所以工序O1,0在0～4 min内在机器M1上加工。然后，J1的第2道工序O1,1选择在M2上加工。然而，第3个工件J2的第1道工序O2,0此时也选择在M2上加工。由于工件J2加工顺序相对于工件J1较前，所以工序O2,0在4～6 min内在机器M2上加工，而工序O1,1在6～7 min内在机器M2上加工。剩余的解码过程不再赘述。最终该染色体可解码成的活动调度方案如图1所示。

3.2 适应度函数

遗传算法评估每个个体的适应度时，适应度函数起到非常重要的作用。本文设计的适应度函数为

其中，

为第x代种群的第y个个体的适应值；

为第x代种群的第y个个体所对应的解与理想纳什均衡之间的距离；

为第x代种群的第y个个体中的工件Ji的流程时间；

为第x代种群的第y个个体对应的makespan。很明显，该适应值函数保证了优良个体将被赋予较大的适应值，较优个体在种群中存活并繁衍的机会较大。

前期仿真实验得到的合适遗传算法参数如下：种群的大小为100，最大迭代次数为100，交叉和变异操作的概率分别为0.8和0.2。

4 仿真实验及结果分析

为了验证本文优化调度方法的有效性，从相关文献中选择了若干具有代表性的benchmark问题进行测试。首先，本文以文献[4]中实例为例进行了测试，该实例规模为6×6，不存在理想纳什均衡。图2为用传统方法和用本文方法得到的优化调度方案甘特图。表3给出了两种方法的结果，其中，S1表示传统方法得到的最优解所对应的各个个体行动策略，S2表示本文方法得到的D最小纳什均衡所对应的各个参与者行动策略。当参与者是工件时，“加工机器/加工顺序”栏是工件对应的加工机器；当参与者是V(表示VMN)时，“加工机器/加工顺序”栏是所有工件的加工顺序。

由表3可以看出,两种方法都可以得到最优的makespan=36。然而，传统方法中并没有考虑各个顾客的利益，即不能在满足整个VMN生产成本最低的情况下，保证每个顾客订单尽可能早地完工交付，而本文方法在保证不延长makespan的基础上，使得工件J1、J3和J5比传统方法分别提前2 min、2 min和1 min单位完工。

另外，还选择了文献[9]中的10个实例进行了测试。该10个实例规模从2×2到4×5，其中，实例SFJS07存在理想纳什均衡，其他实例不存在理想纳什均衡。表4列出了各个实例的结果。当参与者是工件时，“加工机器/加工顺序”栏是工件对应的加工机器；当参与者是V(表示VMN)时，“加工机器/加工顺序”栏是所有工件的加工顺序。从表4中结果可以看到，实例SFJS04和SFJS08不可能同时使VMN的makespan和各个工件的流程时间都达到最小，但本文方法可以适当地均衡VMN和各个工件之间的利益。实例SFJS08不考虑各个工件的利益时，VMN的最优makespan是253 min；均衡各个工件利益时，VMN的最优makespan是256 min。虽然比传统方法得到的makespan多3 min，但保证了每个工件都获得尽可能小的流程时间，这意味着VMN以较小的成本代价使得所有顾客的要求尽早得以满足。图3、图4为2种方法在实例SFJS04和SFJS08的甘特图。

5 结语

本文将虚拟制造网络车间调度问题视为一场博弈，采用博弈论的概念和建模方法，提出了n+1非合作博弈调度优化模型，并设计了基于遗传算法的D最小纳什均衡求解算法。对多个实例的测试验证了所提调度优化方法是有效的，该方法能够均衡多个顾客和VMN之间的利益，保证制造商生产效率和顾客满意度的双赢。进一步的研究将使用博弈论的Stackelberg策略来开发虚拟制造网络环境下车间调度问题的优化方法，让虚拟制造网络中的某个企业占主导地位，其他企业作为跟随者，为支撑生产经营活动良好运作提供优化的车间调度解决方案。

[1] 白俊杰. 虚拟单元制造车间的规划与调度关键技术研究[D]. 南京：南京航空航天大学, 2010.

BAI Junjie. Research on the Key Technologies of Workshop Planning and Scheduling in Virtual Cellular Shop-floor [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2010.

[2] TAYEB F B, BENATCHBA K, MESSIAID A. Game Theory-based Integration of Scheduling with Flexible and Periodic Maintenance Planning in the Permutation Flowshop Sequencing Problem[J]. Operational Research, 2018, 18(1): 221-255.

[3] LI Xinyu, GAO Liang, LI Weidong. Application of Game Theory Based Hybrid Algorithm for Multi-objective Integrated Process Planning and Scheduling [J]. Expert Systems with Applications, 2012, 39(1): 288-297.

[4] ZHOU G H, JIANG P Y, HUANG G Q. A Game-theory Approach for Job Scheduling in Networked Manufacturing [J]. International Journal of Advanced Manufacturing Technology, 2009, 41(9/10): 972-985.

[5] 周光辉, 程元森, 肖忠东, 等. 服务型制造车间关键任务调度的Stackelberg博弈研究[J]. 中国机械工程, 2014, 25(3)： 341-345.

ZHOU Guanghui, CHENG Yuansen, XIAO Zhongdong, et al. Stackelberg Game for Critical Job Scheduling in Service-oriented Manufacturing Plants [J]. China Mechanical Engineering, 2014, 25(3)：341-345.

[6] 周光辉, 程元森, 朱家凯. 面向 SOMS 外包任务分配决策的一对一Stackelberg 博弈模型研究[J]. 应用科技, 2015, 42(2): 53-57.

ZHOU Guanghui, CHENG Yuansen, ZHU Jiakai. Research on the One-to-one Stackelberg Game Model Facing the Allocation Decision of SOMS Outsourcing Tasks[J]. Applied Science and Technology, 2015, 42(2): 53-57.

[7] SUN Dihua, HE Wei, ZHENG Linjiang, et al. Scheduling Flexible Job Shop Problem Subject to Machine Breakdown with Game Theory [J]. International Journal of Production Research, 2013, 52(13): 3858-3876.

[8] ZHANG Yingfeng, WANG Jin, LIU Sichao , et al. Game Theory Based Real-time Shop Floor Scheduling Strategy and Method for Cloud Manufacturing[J]. International Journal of Intelligent Systems, 2017, 32(4): 437-463.

[9] FATTAHI P, MEHRABAD M S, JOLAI F. Mathematical Modeling and Heuristic Approaches to Flexible Job Shop Scheduling Problems [J]. Journal of Intelligent Manufacturing, 2007, 18(3): 331-342.