王昱文

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

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

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

隨著B2B商業(yè)網(wǎng)絡(luò)的日漸成熟，全球供應(yīng)鏈網(wǎng)絡(luò)日漸復(fù)雜，供應(yīng)鏈中各利益方之間競爭與合作的機會并存。舉例而言，在電子設(shè)備行業(yè)中，常?？梢钥吹蕉鄠€生產(chǎn)商將某些特定的生產(chǎn)工序，外包給同一個第三方代工商的情況，如蘋果、三星等電子品牌同代工商富士康之間的關(guān)系。基于該行業(yè)中信息的高效傳遞性及高度共享性，這些生產(chǎn)商與第三方代工商之間可以通過設(shè)定合作機制，從而使實現(xiàn)生產(chǎn)調(diào)度的全局優(yōu)化成為可能。

在過去四十年中，產(chǎn)生了一些很有趣的關(guān)于生產(chǎn)調(diào)度計劃中的合作博弈問題的思考和研究。這類研究被稱作調(diào)度博弈問題，是生產(chǎn)調(diào)度問題和合作博弈理論的交叉研究，主要涉及兩個方面：1）解決生產(chǎn)調(diào)度排序的優(yōu)化問題，通過優(yōu)化排序，實現(xiàn)成本節(jié)約；2）使用合作博弈理論，尋找成本節(jié)約的均衡分配，研究所有參與者之間的合作機制設(shè)計。

調(diào)度博弈問題最早由I. Curiel等人[1]在1989年提出，他們給出了標(biāo)準(zhǔn)調(diào)度博弈模型，即單一機器環(huán)境下，待加工工序不存在約束條件，使用加權(quán)完成時間作為目標(biāo)函數(shù)的調(diào)度模型，他們證明了此類調(diào)度博弈為凸博弈，因而存在均衡解。之后的研究，主要通過增加對工序的約束條件，改變工序及生產(chǎn)商之間的對應(yīng)關(guān)系，增加機器的數(shù)量等方式，對調(diào)度博弈模型進(jìn)行了復(fù)雜。如P.Borm等人[2]研究了在工序具有工期（due dates）的約束條件下，針對三種不同的目標(biāo)函數(shù)：加權(quán)罰金約束（weighted penalty criterion），加權(quán)滯后和（weighted tardiness criterion）以及完工時間（completion time criterion），證明了該模型下均衡解的存在性。從1989年以來所有關(guān)于調(diào)度博弈，核仁分配以及合作博弈凸性問題的研究可以在I.Curiel，H.Hamer，F(xiàn).Klijn等人[3]撰寫的文獻(xiàn)綜述中找到。然而，涉及每個生產(chǎn)商擁有多個待加工工序的研究相對有限，P.Calleja等人[4]研究了單一機器環(huán)境下，每個參與者有多個待加工工序，每個工序有多個受益方的調(diào)度博弈問題，并證明了在一定條件下均衡解的存在。近年來，X.Cai和G.Vairaktarakis[5]及T.Aydinliyim和G.Vairaktarakis[6]研究了考慮外包的調(diào)度博弈問題，研究模型中每個生產(chǎn)商可以擁有多個代加工工序。

本文的模型在以下兩個方面區(qū)別于T.Aydinliyim等人的研究：1）是給出了一個更接近生產(chǎn)實際的合作調(diào)度博弈的生產(chǎn)計劃模型，其中第三方代工商的可用生產(chǎn)能力被表示為一些不連續(xù)的具有有限生產(chǎn)能力的生產(chǎn)窗口；2）使用了復(fù)合目標(biāo)函數(shù)，我們在目標(biāo)成本函數(shù)中，除加權(quán)流水時間外，還考慮了生產(chǎn)窗口的預(yù)訂成本，并且本文中的預(yù)訂成本函數(shù)不具有隨時間單調(diào)遞減的線性約束，而是使用分段函數(shù)，模擬普通工時和加班工時的預(yù)訂成本。

一、研究問題描述

本文研究的生產(chǎn)調(diào)度模型主要關(guān)注供應(yīng)鏈中，生產(chǎn)商與第三方代工商之間的外包流程。一組生產(chǎn)商，將某些同質(zhì)性的待加工工序外包給同一個第三方代工商。每一個生產(chǎn)商根據(jù)先到先服務(wù)（FCFS）的原則，使自身的目標(biāo)成本函數(shù)最小化，獨立地預(yù)定第三方代工商的生產(chǎn)能力。第三方代工商在接到所有生產(chǎn)商的待加工訂單和預(yù)訂安排后，將所有待加工工序打亂，以整體目標(biāo)成本函數(shù)最小化為目標(biāo)，重新優(yōu)化，給出最優(yōu)化排序和生產(chǎn)窗口預(yù)訂方案，實現(xiàn)成本結(jié)余。在這一重新優(yōu)化的過程中，一些生產(chǎn)商的個體利益得到了優(yōu)化，而另一些生產(chǎn)商的個體利益受到了損害。因此，需要設(shè)定相應(yīng)的促進(jìn)合作實現(xiàn)的收益分配機制，將整體優(yōu)化獲得的成本結(jié)余，按照一定的規(guī)則，分配給所有對整體優(yōu)化有貢獻(xiàn)的生產(chǎn)商，以促使整體優(yōu)化的實現(xiàn)。

本文的研究模型將給出一個基于博弈的合作機制。因為所有的生產(chǎn)商依照先到先服務(wù)的原則獨立地預(yù)訂第三方代工商的生產(chǎn)能力，從而會產(chǎn)生以下兩種效率損失的情況：1）每個生產(chǎn)商預(yù)訂的最后一個生產(chǎn)窗口可能存在空閑時間（idle time），在這種情況下，所有生產(chǎn)商產(chǎn)生的空閑時間的總和很有可能會超過一個完整的生產(chǎn)窗口的長度；2）由于依照先到先服務(wù)的原則，某些后到的生產(chǎn)商因為較早的生產(chǎn)窗口都已經(jīng)被預(yù)訂，則不得不將一些優(yōu)先級較高的工序排在較晚的時間生產(chǎn)，這將會帶來在制品庫存成本的增加。以上兩點潛在的效率損失，可以通過設(shè)計合作機制，從而實現(xiàn)整體最優(yōu)排序，以帶來整條供應(yīng)鏈的效率優(yōu)化。

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

二、模型設(shè)計

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

結(jié)語

本文對考慮外包的生產(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é)任編輯：潘洪志]