合作博弈理论的生产调度应用

王昱文

[摘 要] 通过研究合作博弈理论在生产调度问题中的应用，介绍合作博弈的概念及其均衡解的存在条件，并给出一个生产调度模型下的实际应用。该生产调度模型模拟工序外包给第三方承包商的生产模型，并以在制品库存成本和生产窗口的预订成本作为复合目标函数。其中，生产窗口的预订成本非线性，通过模拟普通生产窗口和加班生产窗口的不同价格，将其设定为已知的分段函数；在制品库存成本使用加权流水时间表示，给出了该模型下的合作博弈问题的一组均衡解。

[关键词] 合作博弈；均衡解；生产调度；加权流水时间；应用

[中图分类号] TH128 [文献标识码] B

随着B2B商业网络的日渐成熟，全球供应链网络日渐复杂，供应链中各利益方之间竞争与合作的机会并存。举例而言，在电子设备行业中，常常可以看到多个生产商将某些特定的生产工序，外包给同一个第三方代工商的情况，如苹果、三星等电子品牌同代工商富士康之间的关系。基于该行业中信息的高效传递性及高度共享性，这些生产商与第三方代工商之间可以通过设定合作机制，从而使实现生产调度的全局优化成为可能。

在过去四十年中，产生了一些很有趣的关于生产调度计划中的合作博弈问题的思考和研究。这类研究被称作调度博弈问题，是生产调度问题和合作博弈理论的交叉研究，主要涉及两个方面：1）解决生产调度排序的优化问题，通过优化排序，实现成本节约；2）使用合作博弈理论，寻找成本节约的均衡分配，研究所有参与者之间的合作机制设计。

调度博弈问题最早由I. Curiel等人[1]在1989年提出，他们给出了标准调度博弈模型，即单一机器环境下，待加工工序不存在约束条件，使用加权完成时间作为目标函数的调度模型，他们证明了此类调度博弈为凸博弈，因而存在均衡解。之后的研究，主要通过增加对工序的约束条件，改变工序及生产商之间的对应关系，增加机器的数量等方式，对调度博弈模型进行了复杂。如P.Borm等人[2]研究了在工序具有工期（due dates）的约束条件下，针对三种不同的目标函数：加权罚金约束（weighted penalty criterion），加权滞后和（weighted tardiness criterion）以及完工时间（completion time criterion），证明了该模型下均衡解的存在性。从1989年以来所有关于调度博弈，核仁分配以及合作博弈凸性问题的研究可以在I.Curiel，H.Hamer，F.Klijn等人[3]撰写的文献综述中找到。然而，涉及每个生产商拥有多个待加工工序的研究相对有限，P.Calleja等人[4]研究了单一机器环境下，每个参与者有多个待加工工序，每个工序有多个受益方的调度博弈问题，并证明了在一定条件下均衡解的存在。近年来，X.Cai和G.Vairaktarakis[5]及T.Aydinliyim和G.Vairaktarakis[6]研究了考虑外包的调度博弈问题，研究模型中每个生产商可以拥有多个代加工工序。

本文的模型在以下两个方面区别于T.Aydinliyim等人的研究：1）是给出了一个更接近生产实际的合作调度博弈的生产计划模型，其中第三方代工商的可用生产能力被表示为一些不连续的具有有限生产能力的生产窗口；2）使用了复合目标函数，我们在目标成本函数中，除加权流水时间外，还考虑了生产窗口的预订成本，并且本文中的预订成本函数不具有随时间单调递减的线性约束，而是使用分段函数，模拟普通工时和加班工时的预订成本。

一、研究问题描述

本文研究的生产调度模型主要关注供应链中，生产商与第三方代工商之间的外包流程。一组生产商，将某些同质性的待加工工序外包给同一个第三方代工商。每一个生产商根据先到先服务（FCFS）的原则，使自身的目标成本函数最小化，独立地预定第三方代工商的生产能力。第三方代工商在接到所有生产商的待加工订单和预订安排后，将所有待加工工序打乱，以整体目标成本函数最小化为目标，重新优化，给出最优化排序和生产窗口预订方案，实现成本结余。在这一重新优化的过程中，一些生产商的个体利益得到了优化，而另一些生产商的个体利益受到了损害。因此，需要设定相应的促进合作实现的收益分配机制，将整体优化获得的成本结余，按照一定的规则，分配给所有对整体优化有贡献的生产商，以促使整体优化的实现。

本文的研究模型将给出一个基于博弈的合作机制。因为所有的生产商依照先到先服务的原则独立地预订第三方代工商的生产能力，从而会产生以下两种效率损失的情况：1）每个生产商预订的最后一个生产窗口可能存在空闲时间（idle time），在这种情况下，所有生产商产生的空闲时间的总和很有可能会超过一个完整的生产窗口的长度；2）由于依照先到先服务的原则，某些后到的生产商因为较早的生产窗口都已经被预订，则不得不将一些优先级较高的工序排在较晚的时间生产，这将会带来在制品库存成本的增加。以上两点潜在的效率损失，可以通过设计合作机制，从而实现整体最优排序，以带来整条供应链的效率优化。

除此之外，第三方代工商自身也可以从这一合作机制中受益。例如，一些之前被预订的生产窗口因为整体优化排序而空闲下来。第三方代工商则可以保留一部分的重新空闲窗口的预订成本，将剩下的部分以预订退款（booking refunds）的形式退还给生产商。此外，第三方代工商还可以通过将这些重新空闲的窗口再次预订出去而获得额外的收益。我们将会在本文模型中考虑预订退款的情况，而将可能存在的重新预订成本作为第三方代工商的潜在收益，不列入计算。

二、模型设计

需要注意的是，我们给出的这一分配原则，仅仅只定义了一组服从假设1的可能的核仁分配。可以通过改变不同的限制条件，重新定义对于？滓0（S）而言可以接受的重新排序，从而得到其他可能的核仁分配。

结语

本文对考虑外包的生产调度问题及潜在的合作博弈的可能进行了建模研究。通过建立了考虑在制品库存成本和预订成本的生产模型，研究了相应的合作博弈问题，给出了一组均衡解的分配原则。

[参 考 文 献]

[1]Curiel I， Pederzoli G， Tijs S. Sequencing games [J]. European Journal of Operational Research， 1989， 40（3）： 344-351

[2]Borm P， Fiestras-Janeiro G， Hamers H， et al. On the convexity of games corresponding to sequencing situations with due dates [J]. European Journal of Operational Research， 2002， 136（3）： 616-634

[3]Curiel I， Hamers H， Klijn F. Sequencing games： a survey [M].Chapters in Game Theory. Springer US， 2004： 27-50

[4]Calleja P， Estévez-Fernández A， Borm P， et al. Job scheduling， cooperation， and control [J]. Operations Research Letters， 2006， 34（1）： 22-28

[5]Vairaktarakis G， Cai X Q. Cooperative strategies for manufacturing planning with negotiable third-party capacity [R]. Working paper， 2006

[6]Aydinliyim T， Vairaktarakis G L. Coordination of outsourced operations to minimize weighted flow time and capacity booking costs [J]. Manufacturing & Service Operations Management， 2010， 12（2）： 236-255

[7]Owen G. Game theory[M]. Academic Press，1995

[8]Shapley L S. Cores of convex games [J]. International Journal of Game Theory， 1971， 1（1）： 11-26

[责任编辑：潘洪志]

[参 考 文 献]

[1]Curiel I， Pederzoli G， Tijs S. Sequencing games [J]. European Journal of Operational Research， 1989， 40（3）： 344-351

[2]Borm P， Fiestras-Janeiro G， Hamers H， et al. On the convexity of games corresponding to sequencing situations with due dates [J]. European Journal of Operational Research， 2002， 136（3）： 616-634

[3]Curiel I， Hamers H， Klijn F. Sequencing games： a survey [M].Chapters in Game Theory. Springer US， 2004： 27-50

[4]Calleja P， Estévez-Fernández A， Borm P， et al. Job scheduling， cooperation， and control [J]. Operations Research Letters， 2006， 34（1）： 22-28

[5]Vairaktarakis G， Cai X Q. Cooperative strategies for manufacturing planning with negotiable third-party capacity [R]. Working paper， 2006

[6]Aydinliyim T， Vairaktarakis G L. Coordination of outsourced operations to minimize weighted flow time and capacity booking costs [J]. Manufacturing & Service Operations Management， 2010， 12（2）： 236-255

[7]Owen G. Game theory[M]. Academic Press，1995

[8]Shapley L S. Cores of convex games [J]. International Journal of Game Theory， 1971， 1（1）： 11-26

[责任编辑：潘洪志]

[参 考 文 献]

[1]Curiel I， Pederzoli G， Tijs S. Sequencing games [J]. European Journal of Operational Research， 1989， 40（3）： 344-351

[2]Borm P， Fiestras-Janeiro G， Hamers H， et al. On the convexity of games corresponding to sequencing situations with due dates [J]. European Journal of Operational Research， 2002， 136（3）： 616-634

[3]Curiel I， Hamers H， Klijn F. Sequencing games： a survey [M].Chapters in Game Theory. Springer US， 2004： 27-50

[4]Calleja P， Estévez-Fernández A， Borm P， et al. Job scheduling， cooperation， and control [J]. Operations Research Letters， 2006， 34（1）： 22-28

[5]Vairaktarakis G， Cai X Q. Cooperative strategies for manufacturing planning with negotiable third-party capacity [R]. Working paper， 2006

[6]Aydinliyim T， Vairaktarakis G L. Coordination of outsourced operations to minimize weighted flow time and capacity booking costs [J]. Manufacturing & Service Operations Management， 2010， 12（2）： 236-255

[7]Owen G. Game theory[M]. Academic Press，1995

[8]Shapley L S. Cores of convex games [J]. International Journal of Game Theory， 1971， 1（1）： 11-26

[责任编辑：潘洪志]