合作博弈理论在生产调度问题中的应用.ppt

1、合作博弈理论在生产调度问题中的应用,by 08014420孙豪,参考文献,目,录,1,2,3,4,5,6,合作博弈理论简介,背景及摘要,主要研究方向,核心思想,部分重要概念及问题解决,模型总结与评价,合作博弈理论简介,合作博弈是指博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害，因而整个社会的利益有所增加。 合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。 合作博弈采取的是一种合作的方式，能够增进合作双方的利益以及整个社会的利益，就是因为合作博弈能够产生一种合作剩余。 合作博弈强调的团体理性(collective rationality)，是效率、公

2、平、公正；,背景,随着B2B商业网络的日渐成熟，全球供应链网络日渐复杂，供应链中各利益方之间竞争与合作的机会并存。 举例而言，在电子设备行业中，常常可以看到多个生产商将某些特定的生产工序，外包给同一个第三方代工商的情况，如苹果、三星等电子品牌同代工商富士康之间的关系。基于该行业中信息的高效传递性及高度共享性，这些生产商与第三方代工商之间可以通过设定合作机制，从而使实现生产调度的全局优化成为可能。,摘要,通过研究合作博弈理论在生产调度问题中的应用，介绍合作博弈的概念及其均衡解的存在条件，并给出一个生产调度模型下的实际应用。 该生产调度模型模拟工序外包给第三方承包商的生产模型，并以在制品库存成本和

3、生产窗口的预订成本作为复合目标函数。 其中，生产窗口的预订成本非线性，通过模拟普通生产窗口和加班生产窗口的不同价格，将其设定为已知的分段函数；在制品库存成本使用加权流水时间表示，给出了该模型下的合作博弈问题的一组均衡解。,主要研究方向,1）解决生产调度排序的优化问题，通过优化排序，实现成本节约； 2）使用合作博弈理论，寻找成本节约的均衡分配，研究所有参与者之间的合作机制设计。,核心思想,本文研究的生产调度模型主要关注供应链中，生产商与第三方代工商之间的外包流程。一组生产商，将某些同质性的待加工工序外包给同一个第三方代工商。每一个生产商根据先到先服务(FCFS)的原则，使自身的目标成本函数最小化

4、，独立地预定第三方代工商的生产能力。第三方代工商在接到所有生产商的待加工订单和预订安排后，将所有待加工工序打乱，以整体目标成本函数最小化为目标，重新优化。给出最优化排序和生产窗口预订方案，实现成本结余。在这一重新优化的过程中，一些生产商的个体利益得到了优化，而另一些生产商的个体利益受到了损害。因此，需要设定相应的促进合作实现的收益分配机制，将整体优化获得的成本结余，按照一定的规则，分配给所有对整体优化有贡献的生产商，以促使整体优化的实现。,全局收益观,除生产商收益之外，第三方代工商也可以从这一合作机制中受益。例如，一些之前被预订的生产窗口因为整体优化排序而空闲下来。第三方代工商则可以保留一部分

5、的重新空闲窗口的预订成本，将剩下的部分以预订退款(booking refunds)的形式退还给生产商。 此外，第三方代工商还可以通过将这些重新空闲的窗口再次预订出去而获得额外的收益。,模型示意图,部分主要问题及解决,因为所有的生产商依照先到先服务的原则独立地预订第三方代工商的生产能力，从而会产生以下两种效率损失的情况： 1)每个生产商预订的最后一个生产窗口可能存在空闲时间，浪费资源，提高了成本。 2)由于依照先到先服务的原则，某些后到的生产商则不得不将一些优先级较高的工序排在较晚的时间生产，这将会带来在制品库存成本的增加。 以上两点潜在的效率损失，作者通过设计合作机制，从而实现整体最优排序，以

6、带来整条供应链的效率优化。,合作博弈生产调度模型优点,1：本模型给出了一个更接近生产实际的合作调度博弈的生产计划模型，其中第三方代工商的可用生产能力被表示为一些不连续的具有有限生产能力的生产窗口。 2：使用了复合目标函数，该模型在目标成本函数中，除加权流水时间外，还考虑了生产窗口的预订成本，并且本模型中的预订成本函数不具有随时间单调递减的线性约束，而是使用分段函数，模拟普通工时和加班工时的预订成本。 3：最终实现的是全局优化，采用核仁分配，使整体利益最优，容易使每一方都信任此模型，从而更好合作。,合作博弈生产调度模型缺点及建议,1：考虑的东西虽然比较多，但仍然嫌不够完善，而且做得假设比较理想化

7、，整个模型几乎只能处于一种被参考的状态。 建议：再多考虑一些东西，假设的情形后备注若无此假设会怎么样，提高实用价值。 2：应该将此模型与三星，苹果等大公司的生产调度全局优化实际应用的模型进行对比，从而或可更加完善与改进此模型。,合作博弈生产调度模型问题及改进方法,1：模型的推广。本模型几乎没有任何图表，不利于其他人简洁直观的了解这个模型。 改进：以那个生产窗口模型为例子，再多弄几个小的模型，如成本结余模型，集中优化模型，便于他人了解此模型,合作博弈生产调度模型问题及改进方法,本模型由生产窗口，成本结余，集中优化三个小模型一起构成的，但最终没有整合到一起。而且看这些模型的函数，都是比较难计算的。

8、再分开，再整合，恐怕就更难计算了。若是出了意外情况，又得重新来计算。 改进：将三个函数模型整合成一个大的模型。通过编程实现模型算法的计算。同时跟生产商签订合约，减少出现意外情况的概率。,谢谢观赏,thankyou,6.18,核仁分配,核仁（Nucleolus）的概念的确要繁琐一些。 简单地说是使得最大的不满最小化。对于利益分配联盟博弈（N,v）来说，设N是参与者的集合, v是价值函数,即v(S)为联盟S的值， N和v 都是给定值。设x(S) 为联盟S得到的分配结果。 定义联盟 S 在分配值为x(S)时的不满为：e(S,x)=v(S)-x(S)； 那么对所有N的纯子集S(不含N本身)都有相对应的e(S), 所有e(S)的最大值 e*(S)即为最大不满。 核仁分配x*=(x1*,.,xN*)既是使得e*(S)最小的那个分配(如果使得e*(S)最小的分配是唯一的)。如果有两个或以上分配有一样最小的e*(S),则继续找其中使得第二大不满最小的那个分配，直到得到唯一解，既核仁。,成本结余,项目成本节余=成本降低额=目标成本(1+A%)-实际成本其中,目标成本由计划