合作博弈理論的生產(chǎn)調(diào)度應(yīng)用

1、    合作博弈理論的生產(chǎn)調(diào)度應(yīng)用    王昱文摘 要 通過研究合作博弈理論在生產(chǎn)調(diào)度問題中的應(yīng)用，介紹合作博弈的概念及其均衡解的存在條件，并給出一個(gè)生產(chǎn)調(diào)度模型下的實(shí)際應(yīng)用。該生產(chǎn)調(diào)度模型模擬工序外包給第三方承包商的生產(chǎn)模型，并以在制品庫(kù)存成本和生產(chǎn)窗口的預(yù)訂成本作為復(fù)合目標(biāo)函數(shù)。其中，生產(chǎn)窗口的預(yù)訂成本非線性，通過模擬普通生產(chǎn)窗口和加班生產(chǎn)窗口的不同價(jià)格，將其設(shè)定為已知的分段函數(shù)；在制品庫(kù)存成本使用加權(quán)流水時(shí)間表示，給出了該模型下的合作博弈問題的一組均衡解。關(guān)鍵詞 合作博弈；均衡解；生產(chǎn)調(diào)度；加權(quán)流水時(shí)間；應(yīng)用 th128 b隨著b2b商業(yè)網(wǎng)絡(luò)的日漸

2、成熟，全球供應(yīng)鏈網(wǎng)絡(luò)日漸復(fù)雜，供應(yīng)鏈中各利益方之間競(jìng)爭(zhēng)與合作的機(jī)會(huì)并存。舉例而言，在電子設(shè)備行業(yè)中，常?？梢钥吹蕉鄠€(gè)生產(chǎn)商將某些特定的生產(chǎn)工序，外包給同一個(gè)第三方代工商的情況，如蘋果、三星等電子品牌同代工商富士康之間的關(guān)系?；谠撔袠I(yè)中信息的高效傳遞性及高度共享性，這些生產(chǎn)商與第三方代工商之間可以通過設(shè)定合作機(jī)制，從而使實(shí)現(xiàn)生產(chǎn)調(diào)度的全局優(yōu)化成為可能。在過去四十年中，產(chǎn)生了一些很有趣的關(guān)于生產(chǎn)調(diào)度計(jì)劃中的合作博弈問題的思考和研究。這類研究被稱作調(diào)度博弈問題，是生產(chǎn)調(diào)度問題和合作博弈理論的交叉研究，主要涉及兩個(gè)方面：1）解決生產(chǎn)調(diào)度排序的優(yōu)化問題，通過優(yōu)化排序，實(shí)現(xiàn)成本節(jié)約；2）使用合作博弈理論

3、，尋找成本節(jié)約的均衡分配，研究所有參與者之間的合作機(jī)制設(shè)計(jì)。調(diào)度博弈問題最早由i. curiel等人1在1989年提出，他們給出了標(biāo)準(zhǔn)調(diào)度博弈模型，即單一機(jī)器環(huán)境下，待加工工序不存在約束條件，使用加權(quán)完成時(shí)間作為目標(biāo)函數(shù)的調(diào)度模型，他們證明了此類調(diào)度博弈為凸博弈，因而存在均衡解。之后的研究，主要通過增加對(duì)工序的約束條件，改變工序及生產(chǎn)商之間的對(duì)應(yīng)關(guān)系，增加機(jī)器的數(shù)量等方式，對(duì)調(diào)度博弈模型進(jìn)行了復(fù)雜。如p.borm等人2研究了在工序具有工期（due dates）的約束條件下，針對(duì)三種不同的目標(biāo)函數(shù)：加權(quán)罰金約束（weighted penalty criterion），加權(quán)滯后和（weighted

4、 tardiness criterion）以及完工時(shí)間（completion time criterion），證明了該模型下均衡解的存在性。從1989年以來(lái)所有關(guān)于調(diào)度博弈，核仁分配以及合作博弈凸性問題的研究可以在i.curiel，h.hamer，f.klijn等人3撰寫的文獻(xiàn)綜述中找到。然而，涉及每個(gè)生產(chǎn)商擁有多個(gè)待加工工序的研究相對(duì)有限，p.calleja等人4研究了單一機(jī)器環(huán)境下，每個(gè)參與者有多個(gè)待加工工序，每個(gè)工序有多個(gè)受益方的調(diào)度博弈問題，并證明了在一定條件下均衡解的存在。近年來(lái)，x.cai和g.vairaktarakis5及t.aydinliyim和g.vairaktarakis6

5、研究了考慮外包的調(diào)度博弈問題，研究模型中每個(gè)生產(chǎn)商可以擁有多個(gè)代加工工序。本文的模型在以下兩個(gè)方面區(qū)別于t.aydinliyim等人的研究：1）是給出了一個(gè)更接近生產(chǎn)實(shí)際的合作調(diào)度博弈的生產(chǎn)計(jì)劃模型，其中第三方代工商的可用生產(chǎn)能力被表示為一些不連續(xù)的具有有限生產(chǎn)能力的生產(chǎn)窗口；2）使用了復(fù)合目標(biāo)函數(shù)，我們?cè)谀繕?biāo)成本函數(shù)中，除加權(quán)流水時(shí)間外，還考慮了生產(chǎn)窗口的預(yù)訂成本，并且本文中的預(yù)訂成本函數(shù)不具有隨時(shí)間單調(diào)遞減的線性約束，而是使用分段函數(shù)，模擬普通工時(shí)和加班工時(shí)的預(yù)訂成本。一、研究問題描述本文研究的生產(chǎn)調(diào)度模型主要關(guān)注供應(yīng)鏈中，生產(chǎn)商與第三方代工商之間的外包流程。一組生產(chǎn)商，將某些同質(zhì)性的待加

6、工工序外包給同一個(gè)第三方代工商。每一個(gè)生產(chǎn)商根據(jù)先到先服務(wù)（fcfs）的原則，使自身的目標(biāo)成本函數(shù)最小化，獨(dú)立地預(yù)定第三方代工商的生產(chǎn)能力。第三方代工商在接到所有生產(chǎn)商的待加工訂單和預(yù)訂安排后，將所有待加工工序打亂，以整體目標(biāo)成本函數(shù)最小化為目標(biāo)，重新優(yōu)化，給出最優(yōu)化排序和生產(chǎn)窗口預(yù)訂方案，實(shí)現(xiàn)成本結(jié)余。在這一重新優(yōu)化的過程中，一些生產(chǎn)商的個(gè)體利益得到了優(yōu)化，而另一些生產(chǎn)商的個(gè)體利益受到了損害。因此，需要設(shè)定相應(yīng)的促進(jìn)合作實(shí)現(xiàn)的收益分配機(jī)制，將整體優(yōu)化獲得的成本結(jié)余，按照一定的規(guī)則，分配給所有對(duì)整體優(yōu)化有貢獻(xiàn)的生產(chǎn)商，以促使整體優(yōu)化的實(shí)現(xiàn)。本文的研究模型將給出一個(gè)基于博弈的合作機(jī)制。因?yàn)樗械?/p>

7、生產(chǎn)商依照先到先服務(wù)的原則獨(dú)立地預(yù)訂第三方代工商的生產(chǎn)能力，從而會(huì)產(chǎn)生以下兩種效率損失的情況：1）每個(gè)生產(chǎn)商預(yù)訂的最后一個(gè)生產(chǎn)窗口可能存在空閑時(shí)間（idle time），在這種情況下，所有生產(chǎn)商產(chǎn)生的空閑時(shí)間的總和很有可能會(huì)超過一個(gè)完整的生產(chǎn)窗口的長(zhǎng)度；2）由于依照先到先服務(wù)的原則，某些后到的生產(chǎn)商因?yàn)檩^早的生產(chǎn)窗口都已經(jīng)被預(yù)訂，則不得不將一些優(yōu)先級(jí)較高的工序排在較晚的時(shí)間生產(chǎn)，這將會(huì)帶來(lái)在制品庫(kù)存成本的增加。以上兩點(diǎn)潛在的效率損失，可以通過設(shè)計(jì)合作機(jī)制，從而實(shí)現(xiàn)整體最優(yōu)排序，以帶來(lái)整條供應(yīng)鏈的效率優(yōu)化。除此之外，第三方代工商自身也可以從這一合作機(jī)制中受益。例如，一些之前被預(yù)訂的生產(chǎn)窗口因?yàn)檎?/p>

8、體優(yōu)化排序而空閑下來(lái)。第三方代工商則可以保留一部分的重新空閑窗口的預(yù)訂成本，將剩下的部分以預(yù)訂退款（booking refunds）的形式退還給生產(chǎn)商。此外，第三方代工商還可以通過將這些重新空閑的窗口再次預(yù)訂出去而獲得額外的收益。我們將會(huì)在本文模型中考慮預(yù)訂退款的情況，而將可能存在的重新預(yù)訂成本作為第三方代工商的潛在收益，不列入計(jì)算。二、模型設(shè)計(jì)需要注意的是，我們給出的這一分配原則，僅僅只定義了一組服從假設(shè)1的可能的核仁分配?？梢酝ㄟ^改變不同的限制條件，重新定義對(duì)于？滓0（s）而言可以接受的重新排序，從而得到其他可能的核仁分配。結(jié)語(yǔ)本文對(duì)考慮外包的生產(chǎn)調(diào)度問題及潛在的合作博弈的可能進(jìn)行了建模研

9、究。通過建立了考慮在制品庫(kù)存成本和預(yù)訂成本的生產(chǎn)模型，研究了相應(yīng)的合作博弈問題，給出了一組均衡解的分配原則。 參 考 文 獻(xiàn)1curiel i， pederzoli g， tijs s. sequencing games j. european journal of operational research， 1989， 40（3）： 344-3512borm p， fiestras-janeiro g， hamers h， et al. on the convexity of games corresponding to sequencing situations with due date

10、s j. european journal of operational research， 2002， 136（3）： 616-6343curiel i， hamers h， klijn f. sequencing games： a survey m.chapters in game theory. springer us， 2004： 27-504calleja p， estévez-fernández a， borm p， et al. job scheduling， cooperation， and control j. operations research le

11、tters， 2006， 34（1）： 22-285vairaktarakis g， cai x q. cooperative strategies for manufacturing planning with negotiable third-party capacity r. working paper， 20066aydinliyim t， vairaktarakis g l. coordination of outsourced operations to minimize weighted flow time and capacity booking costs j. manufa

12、cturing & service operations management， 2010， 12（2）： 236-2557owen g. game theorym. academic press，19958shapley l s. cores of convex games j. international journal of game theory， 1971， 1（1）： 11-26責(zé)任編輯：潘洪志 參 考 文 獻(xiàn)1curiel i， pederzoli g， tijs s. sequencing games j. european journal of operational

13、 research， 1989， 40（3）： 344-3512borm 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-6343curiel i， hamers h， klijn f. sequencing games： a survey m.chapters in game t

14、heory. springer us， 2004： 27-504calleja p， estévez-fernández a， borm p， et al. job scheduling， cooperation， and control j. operations research letters， 2006， 34（1）： 22-285vairaktarakis g， cai x q. cooperative strategies for manufacturing planning with negotiable third-party capacity r. wor

15、king paper， 20066aydinliyim 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-2557owen g. game theorym. academic press，19958shapley l s. cores of convex games j.

16、 international journal of game theory， 1971， 1（1）： 11-26責(zé)任編輯：潘洪志 參 考 文 獻(xiàn)1curiel i， pederzoli g， tijs s. sequencing games j. european journal of operational research， 1989， 40（3）： 344-3512borm p， fiestras-janeiro g， hamers h， et al. on the convexity of games corresponding to sequencing situations wit

17、h due dates j. european journal of operational research， 2002， 136（3）： 616-6343curiel i， hamers h， klijn f. sequencing games： a survey m.chapters in game theory. springer us， 2004： 27-504calleja p， estévez-fernández a， borm p， et al. job scheduling， cooperation， and control j. operations research letters， 2006， 34（1）： 22-285vairaktarakis g， cai x q. cooperative strategies for manufacturing planning with negotiable third-party capacity r. working paper， 20066aydinliyim t， vairaktarakis g l. coordination of outsourced operations to minim