基于演化博弈的敏捷车间单元动态调度

随着人类经济社会进入新世纪 ，产品的制造模式和市场营销方式都发生了实质性的转变。供应网络全球化及不确定性客户需求的外部市撤境对当今制造企业及其生产车间提出了敏捷性的客观要求，也提供 了敏捷制造(Agile Manufac-tu ring，简称AM)的实现机遇和用武之地。AM已成为全球制造业转型升级的首演径 ，相应的敏捷车间(Agile Workshop，简称AW)作为AM模式下制造企业最基础的生产组织单位，已成为近年来商业界和理论界研究热点。AW是指在高度竞合、动态多变的外部商业环境中，供应商、制造商、服务商等实体参与构成的实时响应外界商机和需求变化的最基层动态生产组织单位。它区别于传统生产车间的最大特点是 ：它能基于虚拟化的形式展开单元快速调度，包括动态组合、调整及解散。基于AW的单元动态调度的实质就是在动态联盟成员企业所有可调用资源约束的前提下，怎样选择、组织、配置多方制造企业的制造性资源 ， ， r - - -- - - ， ， - - l - ，V ， V、 - - - - - - - - - - - - - - - - - ， L ， - - - - ， r l- r - - - - - 收稿日期：2013-04-09 修订 日期：2013-06-15基金项目：(1)国家自然科学基金项目(71102149)；(2)国家社会科学基金项目(11CJY064)；(3)工信部通信软科学研究项目(2013R01-2)；(4)教 育部人 文社 会科学研 究项 目(12YJC790084)；(5)陕西侍 育厅专项科 研计 划资助项 目(12JK0056)；(6)西安邮电大学青年教师科研基金项目(ZL201 1-22)。

作者简介：孔令夷(1977-)，男，副教授、博士研究生。研究方向：敏捷制造、演化博弈论、运营管理，E-mail：kly###xupt edu.cn以完成复杂多变的车间加工任务，取得生产任务完成的最大化综合满意度及最优客户满意度。

2国内外相关研究述评许多文献集中在AM概念论述，偏重于理论研究 ，很少对AM的底层车间给予研究 ，不利于实施。实际上，车间是敏捷企业中最基本的生产和管理单位，是实现AM重要而关键的领域 ，对诸多使能系统具有基础性影响。AM企业通过快速改造或重组来捕捉不可预见的机会，利用高度柔性的设备、标准的软件、可简单插接到生产车间的生产过程 ，在短时间内构成-个新的生产车间系统，按生产品种与批量的变化自动调整，使得车间系统成为按订单生产的新型制造车间--AW。AW依据可重用性、可重构性及可扩充性的敏捷性设计准则，在产品生产、任务计划、车间管理和资源集成过程中，通过先进调度技术，完成动态生产的场所。车间的工作性能、组织生产方式以及所采用的制造技术直接影响到产能、开发周期、成本及质量等。AW除了常规的生产管控功能外，还具有单元动态调度、网络交流合作的功能。因此，研究AW调度管理具有重要意义。本文拟论述基于多代理的AW管控结构，基于演化博弈探讨AW的单元动态调度技术。

再者 ，当前文献都缺乏AW的实证研究，除陈友玲㈦、陈刚㈣、罗天洪 、李应 、P.G.Li㈣，实证研究的文献极少。因此，本文将对AW调度算法作实证研究，以弥补不足。

第三 ，学者们 已展开 AW单元动态调度研究 ，但是并未取得满意结果，原因如下：(1)以往研究通常遵循 白上至下的AW单元动态调度思想，这样的研究方法因底层信息不能及时反礼取而影响了AW的整体敏捷性实现。

与之相反，自下至上调度车间单元，也面临着分布前沿科学(季刊)2013·2第7卷·总第26期I匝衄圈团圈 l式车间单元协同复杂性及冲突多发性的问题，而且可能会出现管控成本过高、单元通信联络密集的缺点。

(2)现有文献仅仅局限于研究调度单元设备等有形资源，而忽略了无形的工艺路线的调度技术和策略研究” 。实质上，车间调度必须整合单元和工艺，二者应保持同步性。

(3)部分学者将单元调度问题转化为复杂的数学集合模型，求解计算量大 ，寻优难度高，算法可行性较低 ，也不能准确映射AW 的动态变化特性。

(4)模糊 目标或多目标决策下的AW单元动态调度研究仍为空白点，而这才真正是AW研究的本质性、客观性要求m]。

未来车间将经历从传统功能车间到 以产品聚类为特征的AW的变革 ，AM将表现为由计算机网络控制的多个AW组成的分布式自主制造系统” 。车间生产网络的形成实质上是-个优化制造资源，构造面向需求的AM单元，形成AW的过程。关键就是要研究AW单元调度技术、重构方法、管理模式及实施对策，这是实现AM的基矗3问题提出车间的具体情况千差万别，即使是同类型车间，也由于生产设备的自动化程度、管理的方式、信息处理的手段等方面的不同而呈现出巨大的差异性。因此 ，本人拟结合 自上至下以及自下至上的单元动态调度思想，以图1为示例。

该 图就是基于 Multi-Agent(即三种代理 ：Job Agent，即工作代理 ；Resou rce Agent，即资源代理 ；Scheduling Agent，即调度代理)的AW单元动态调度框架。从图中可见 ，3个传统车间(A、B、C)具备可调度的加工资源，包括设备、物料、工具、工艺等，分布在4个传统的加工单元，每7 I前沿科学季刊)2013·2第7卷·总第26期I匝衄圈匣圈 f 姗 / 、 J出 1 Job 2 Job 3 J出 4 Job 5.. ...--. -、√ ；AM单 r ～ l 元5I 1 ：I面元4 i l I -，--I-- 1 Ii AM-3 l !； l i i ；圳单元2芸i：璺：### 三翻：。 I ### ###j### ：######崎### 0 0蜮 L旦 旦- L旦. ### 0 ### ###传统单元 1 佶统单元2 传统单元 3 传统单元4 / r - 、 传统车间B ， . 、传统车间A 姆卅/l 、 蝇enl / 佶统车间C /图1基于MuItI-Agenl的Aw单元动态调度框架个单元的资源数量和分布情况各不相同，以图中###所示。在AM模式下，各种资源可以被共享，既能服务于所在单元的生产加工，也能被调度与其他单元的资源共同构成新型的敏捷制造单元，用于完成新的加工作业，即Job。也就是说 ，所有资源是面向Job的资源，而并不是隶属于传统企业、传统车间，或受限于传统企业和传统车间的固有边界。图中共有 2个 AW，下辖 5个面向Job的AM单元--对应于5项生产加工作业的Job有待完成，这也意指AM企业需要扑捉利用的动态商机和潜在需求。-种资源可能同时要被调用组建多个AM单元，完成多个 Job，而且J0b也处于动态变化之中，比如图中5个AM单元的两两交叉部分的资源就是如此。

采用Multi-Agent技术构建AW单元动态调度模型 ，是为了实现AW的敏捷性、协同性、集成性与高智能性。首先，每项资源要素都有专属的具备较高智能性及推理能力的资源代理Agent为其服务，掌控着各项资源要素的运行情况，管理其产能信息等，负责代理外部协作事务，并借助互联网、EDl或广域网联络集成，形成大范围的多智能体系统(MAS)。其次，每项加工作业Job也都有唯-的Job Agent与之联系，Job Agent掌控着各项Job对应的生产订单的完整信息等，包括工艺路线、产量、品种、适用加工中心、工时需求、辅助工装(夹具、量具、刀具等)、成本控制、精度及质量要求、其他加工要求等。Job通过其代理Agent在网络化信息系统中公布加工作业Job的需求信息，寻求适当可用且胜任的资源来组建完成Job的AM单元∮着 ，资源代理Agent收集到JobAgent公布的加工需求信息之后，开始对自身的生产能力与外部的生产需求进行平衡 ，作出是否申请承接加工Job的决策。如果经平衡后认为该项资源能够胜任这- Job，则由资源代理Agent向Job Agent发出正式请求或申请加入到侯选资源中，二者(两个Agent)随即展开供需谈判：关于成本、交货期、质量、数量、进度、产成品加工性能要求等 方面 。-般 情况 下 ，加 工作 业代理 JobAgent与资源代理Agent经过多轮次协商，就能够动态选择出胜任Job(即市锄遇提供的加工作业Job任务)的所有候选资源要素体∩以说，资源选择的过程就是面向Job的资源动态优寻重组过程 ，即AW单元动态调度过程。因为，单-的Job Agent不掌握也不必掌握其他 Job的信息，也不必要联系未向其发出申请的其他资源的情况和信息。所以，资源优选过程，即单元动态调度过程 仅由Job Agent据其获取的孤立Job信息和部分相关性资源的有限信息而独立决策完成，这可以看为白下至上的单元调度。然而 ，AW内Job的多变性和不可预知性极易导致有限资源难以全面共用的约束和冲突，甚至引发恶性抢夺，直接威胁着所有 Job的资源供给 ，这是每个 JobAgent和资源Agent所无力解决的问题，也是其固有缺陷。尤其是高效低耗的稀缺性优质资源必然会供不应求，成为面向多Job的AW瓶颈资源。总之，对于整体AW而言 ，单纯依赖Job Agent和资源Agent的车间单元调度方案往往只能取得局部最优 ，而无法得到AW全局最优，并不是车间层面的资源优选方案或单元最优动态调度方案。因此，本文设计了调度代理 Scheduling Agent来协同各个Job Agent在资源优选过程的独立决策，实现AW车间层面的资源全局性优仰策以及单前沿科学(季刊)2013·2第7卷·总第26期l圃衄圃国圜 l元最优调度决策，确立自上至下以及白下至上相结合的动态调度思想。

具体 来说 ，在 AW单 元动态调度 中 ，调度Agent与Job Agent、资源Agent发生联系，三者传递的信息属于协同性信息。首先，Job Agent将其资源优选思路及方法等信息以及Job的加工需求信息发送给调度Agent∮着，调度Agent统计汇集所有资源Agent发来的设备产能等供给方面的信息，并对供求信息作出平衡决策，决策结果会快速反馈给各Job Agent和资源Agent，确保供需方协同运作，有助于实现AW车间层面全局优化的动态调度。

4 AW单元动态调度模型构建综上所述，AW单元动态调度的本质就是资源优寻重组。资源重组可以借助聚类分析法。

AW的资源优焉表述为：给定某时段的车间所有Job、各个Job的候选资源、各种资源的能力信息、各种资源完成各个Job的生产时间定额、运输时间定额、成本信息及期量标准等。求出完成所有Job的资源优询，作为AW单元动态优化调度方案，以使完成Job的综合满意度(完成时间满意度及成本满意度的综合)最优。

设AW承揽了 n个可被分工为若干工序的Job，用 集 合 厂 表 示 ， J -， ，- l，， ， l，， ，d 是 (第i个Job)能被分解的工序数量(子Job)。

令z z ，，Z，'as ，ZA -ZA ，，ZA dS，，其中 l，，d ，Z 表示 (第i个Job的子Job，生产工艺路线上的某个细分工序)的候选资源集，ZA 表示 的候选资源代理集，S 表示工作 的候选资源总数量。根据同类资源可t9 I前沿科学季刊)2013·2第7卷·总第26期l圃墨圆圈圈 互替性，J. 在Z. 中可以选择且只可以选择其中的- 个资源Agent及其对应的资源来完成加工任务。

可 知 ： 若 有 i≠h ， 必 然 有(UzA )n(UzA )≠设 z，的产能是 P，，其中 l，，S，z 到z 的运能是 丁 ，其中g1，，S，且 g≠t，S是AW的可用资源总量。 幽，c ， 分别表示资源 z 用于作业 L， 的单位生产成本定额、实际生产成本、生产时间定额及实际生产时间，其中是1，，S d，易见得：f ，t d 随着资源 z dk产能短 缺 程 度 及 生产 时 间定 额 的变 动 而 变动 。

， ， ， 又各自表示 L， 选择资源 z ，而且 ， 选择资源 z ，两个子Job工序之间要进行运输配送的单位运输成本、实际运输成 本 、运 输 时间定 额 、实 际运输 时间 。其 中e-l， ，d ， -1， ，S ， ≠e，k≠Ⅲ ，易 见得 ： 随着资源 Zidk到 的运能短缺 程 度及 运输 时 间定额 的变动 而 变动 。设SZ SZ小，SZ 指代最终选定的资源组合，SZA SZA ，SZA 指代最终选定的资源Agent集合，那么 SZA 就是工作 最终选定的资源代理，SZA ∈ZA耐。

若 有 SZtl∈SZ1 . SZA ∈SZAt 且SZ， z dk，SZA dZA dk则说明资源 z 被选择，可以令 )， (dk)1；反之 y (dk)0。同时，令(dk，e ))， (dk)y (era)，若 ， 选择资源 z dk，而且 选择资源 z ，则等价于 )， ( )1，而且)， (era)1 ，那 么 就 有 (dk， )1 ；反 之(dk，e；rH)0。

令 ， 相应的Job Agent生产时间满意度指标为 ， (丁 )，权重设为 f，；同样地 ，生产成本满意度。

度的线性加权 ，即 ，1 - (Ti)rI 。(C )rq，其中，瞳毒 季哥蜀 ' ”t - ..∑∑y ( )c ∑∑∑∑ ( ， ) ，Ir ls.t.∑y ( )-l (1)Agent及其对应的资源Agent来完成细分的子加5 AW单元动态调度的演化博弈分析层的自治体，负责信息收集与分析处理，作出资源选择决策、生产订单发布决策、协同运作决策等。

因此，基于Multi-Agent的AW单元动态调度的效率及优劣程度很大程度上依赖于Agent所获取的决策支持信息的数量、质量、关联性及时效性。为了快速响应外部需求变化，适应复杂多变的不确定性制造环境 ，各种Agent必须不断增强独立决策能力，几乎不需要知道其他Agent的决策动机、策略、过程和支付，也无法确切知晓，决策支持信息通常是不完全且不完美的，这也是AW动态复杂系统的典型特性。因此 ，在这样的多代理运行机制下，AW内诸多Agent之间的冲突及其相关资源调度冲突在所难免。为了应对及解决它们之间的频发冲突，Agent之间需要展开协商谈判，即使如此也难以获取其他Agent的所有确定性信息。

总之，基于博弈论视角，各种Agent之间的博弈都存在着结果的不确定性。不确定性是AW的各个Agent参与方行动策略的结果，也正是它们之问博弈本身的特性。

5.2 AW单元动态调度过程中Multi-Agent的有限理性上文已述及 ，各个Job Agent在进行资源优选过程中，基于不完全信息条件下，只能作出独立的非完全理性的决策 ，势必会促发与同类Agent的资源抢夺与冲突。此 时，若冲突各 方的JobAgent不能成功协商并达成资源调用共识，则资源产能供不应求将直接影响完成Job的综合满意度，使之降低 ，结果就是无法实现AW单元调度全局最优化。为了解决这-问题 ，必须引入合理的智能协调机 制和演化遗传机制，引导各个 JobAgent的资源优选策略及决策，使它们克服决策孤立片面性、狭隘自利性及有限理性的缺陷，从而得到面向Job的AW单元动态调度的最大综合满意度。

前沿科学(季刊)2013·2第7卷·总第26期l圃衄盈囡圃 l5.3 AW单元动态调度的ESS解释基于策略博弈视 角 ，上世纪 40年代 。VonNeuman与 O.Morgensterm合作出版《博弈论与经济行为》，首次将博弈论用于分析各经济人基于自身利益考虑的互动决策、理性行为以及均衡解释，之后Nash John将这-建模思想及数学工具拔高到又-个新层面--纳什均衡，指的是博弈中的-个策略组合，每个参与人选择-个相应的策略，在其他参与人都坚守这个策略组合中的策略不变的情况下，没有参与人可以通过改变自己的策略而得到-个更高的支付。因此也没有人愿意改变 自己的策略，从而该策略组合达成稳定态。这-概念显然能适用于 Multi-Agent的策略性行动及协同决策。基于完全理性假设、完全信息及均衡概念的博弈理论固然非常有用，然而，我们并不能完全依赖这样的博弈理论来解决具有复杂性、动态性及不确定性的AW单元动态调度问题。当Agent缺乏其他 Agent的信息，它们在有限理性下的策略选择和结果与完全理性假设下以均衡概念为基础所预测的内容可能产生很大差异。

博弈的演化(evolutionary)分析正是针对有限理性这-点的▲化分析派生于生物学中的演化思想，始于上世纪 60年代，逐渐发展成熟为演化博 弈 论 (Evolutionary Game Theory，简 称EGT)。生物的基因对其行为模式有重大的影响，某些行为在当前环境中显得较为成功，在这种意义上拥有这些行为模式的生物更易繁衍并将其基因遗传给后代。生物学家就称该种群结构极其当前表现型是演化稳定(Evolutionary Stable)的。

经过数代遗传演化后 ，该类较为成功的生物种群在较长时间内所表现的稳定形态，被称为演化均衡(Evolutionary Equilibrium，简称EE)，它们的这种行为模式所对应的策略选择就称为演化稳定策 l前沿科学(季刊)2013·2第7卷·总第26期I匝圆圈匣圈 略(Evolutionary Stable Strategy，简称 ESS)。相应地，演化稳定状态 (Evolutionary Stable State)就是给定环境下经过数代遗传演化过程的最终状况。 目前 ，EGT覆盖了广泛的领域 ，包括经济管理、商业、政治、社会、外交、军事、网络通信等数不尽数的学科。

不难发现 ，AW 单元动态调度过程中各种Agent的策略博弈其实就归属于演化博弈，主要源于Agent的智能性、学习能力、逻辑推理能力及计算能力，因此EGT的假设条件可能更符合及适用各种Agent的情况及行为 。①有限理性，EGT放宽了理性行为的假定 ，参与方Agent有意识地最大化满足自身需求的假设被修改和调整，取而代之的是对它们的策略 、行为及支付 ，可以理解为选择更具适应性的策略的-种演化过程的稳定结果，即多轮次重复博弈的ESS及其均衡；②交互性，几乎所有参与方Agent都会和种群中别的子体发生相互作用，相互影响，向单-的稳定结果或形式发展进化，或者它们可以以-定比例共存，保持形态多元化 ；③异质性，随着时间的推移，偶然的因素会带来新的Agent基因变异；④适应性，在下-代Agent中更具适应性的表现型Agent在数量上比起较不具有适应性的表现型Agent来说就更加多-些，各个Agent的适应度与它和同代或非同代种群子体(其他Agent)博弈(相互作用)时获得的平均支付或总支付呈现正相关；⑤选择，即自然选择的法则：优胜劣汰，适者生存”，但更应该广义地理解自然选择”为：自然环境选择优良子体Agent的最终检验准则是不仅要看其能否成功地适应环境而生存下来，而