王昱文

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

[關(guān)鍵詞] 合作博弈；均衡解；生產(chǎn)調(diào)度；加權(quán)流水時(shí)間；應(yīng)用

[中圖分類號(hào)] TH128 [文獻(xiàn)標(biāo)識(shí)碼] B

隨著B2B商業(yè)網(wǎng)絡(luò)的日漸成熟，全球供應(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）使用合作博弈理論，尋找成本節(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 tardiness criterion）以及完工時(shí)間（completion time criterion），證明了該模型下均衡解的存在性。從1989年以來所有關(guān)于調(diào)度博弈，核仁分配以及合作博弈凸性問題的研究可以在I.Curiel，H.Hamer，F(xiàn).Klijn等人[3]撰寫的文獻(xiàn)綜述中找到。然而，涉及每個(gè)生產(chǎn)商擁有多個(gè)待加工工序的研究相對(duì)有限，P.Calleja等人[4]研究了單一機(jī)器環(huán)境下，每個(gè)參與者有多個(gè)待加工工序，每個(gè)工序有多個(gè)受益方的調(diào)度博弈問題，并證明了在一定條件下均衡解的存在。近年來，X.Cai和G.Vairaktarakis[5]及T.Aydinliyim和G.Vairaktarakis[6]研究了考慮外包的調(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ì)性的待加工工序外包給同一個(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)樗械纳a(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)窗口的長度；2）由于依照先到先服務(wù)的原則，某些后到的生產(chǎn)商因?yàn)檩^早的生產(chǎn)窗口都已經(jīng)被預(yù)訂，則不得不將一些優(yōu)先級(jí)較高的工序排在較晚的時(shí)間生產(chǎn)，這將會(huì)帶來在制品庫存成本的增加。以上兩點(diǎn)潛在的效率損失，可以通過設(shè)計(jì)合作機(jī)制，從而實(shí)現(xiàn)整體最優(yōu)排序，以帶來整條供應(yīng)鏈的效率優(yōu)化。

除此之外，第三方代工商自身也可以從這一合作機(jī)制中受益。例如，一些之前被預(yù)訂的生產(chǎn)窗口因?yàn)檎w優(yōu)化排序而空閑下來。第三方代工商則可以保留一部分的重新空閑窗口的預(yù)訂成本，將剩下的部分以預(yù)訂退款（booking refunds）的形式退還給生產(chǎn)商。此外，第三方代工商還可以通過將這些重新空閑的窗口再次預(yù)訂出去而獲得額外的收益。我們將會(huì)在本文模型中考慮預(yù)訂退款的情況，而將可能存在的重新預(yù)訂成本作為第三方代工商的潛在收益，不列入計(jì)算。

二、模型設(shè)計(jì)

需要注意的是，我們給出的這一分配原則，僅僅只定義了一組服從假設(shè)1的可能的核仁分配?？梢酝ㄟ^改變不同的限制條件，重新定義對(duì)于？滓0（S）而言可以接受的重新排序，從而得到其他可能的核仁分配。

結(jié)語

本文對(duì)考慮外包的生產(chǎn)調(diào)度問題及潛在的合作博弈的可能進(jìn)行了建模研究。通過建立了考慮在制品庫存成本和預(yù)訂成本的生產(chǎn)模型，研究了相應(yīng)的合作博弈問題，給出了一組均衡解的分配原則。

[參 考 文 獻(xiàn)]

[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

[責(zé)任編輯：潘洪志]

[參 考 文 獻(xiàn)]

[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

[責(zé)任編輯：潘洪志]

[參 考 文 獻(xiàn)]

[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

[責(zé)任編輯：潘洪志]