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

王昱文

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

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

[中圖分類號] TH128 [文獻標識碼] B

隨著B2B商業(yè)網(wǎng)絡(luò)的日漸成熟，全球供應鏈網(wǎng)絡(luò)日漸復雜，供應鏈中各利益方之間競爭與合作的機會并存。舉例而言，在電子設(shè)備行業(yè)中，常?？梢钥吹蕉鄠€生產(chǎn)商將某些特定的生產(chǎn)工序，外包給同一個第三方代工商的情況，如蘋果、三星等電子品牌同代工商富士康之間的關(guān)系?；谠撔袠I(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年提出，他們給出了標準調(diào)度博弈模型，即單一機器環(huán)境下，待加工工序不存在約束條件，使用加權(quán)完成時間作為目標函數(shù)的調(diào)度模型，他們證明了此類調(diào)度博弈為凸博弈，因而存在均衡解。之后的研究，主要通過增加對工序的約束條件，改變工序及生產(chǎn)商之間的對應關(guān)系，增加機器的數(shù)量等方式，對調(diào)度博弈模型進行了復雜。如P.Borm等人[2]研究了在工序具有工期（due dates）的約束條件下，針對三種不同的目標函數(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]撰寫的文獻綜述中找到。然而，涉及每個生產(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）使用了復合目標函數(shù)，我們在目標成本函數(shù)中，除加權(quán)流水時間外，還考慮了生產(chǎn)窗口的預訂成本，并且本文中的預訂成本函數(shù)不具有隨時間單調(diào)遞減的線性約束，而是使用分段函數(shù)，模擬普通工時和加班工時的預訂成本。

一、研究問題描述

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

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

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

二、模型設(shè)計

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

結(jié)語

本文對考慮外包的生產(chǎn)調(diào)度問題及潛在的合作博弈的可能進行了建模研究。通過建立了考慮在制品庫存成本和預訂成本的生產(chǎ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

[責任編輯：潘洪志]

[參 考 文 獻]

[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

[責任編輯：潘洪志]