合作博弈理論的生產調度應用

王昱文

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

[關鍵詞] 合作博弈；均衡解；生產調度；加權流水時間；應用

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

隨著B2B商業網絡的日漸成熟，全球供應鏈網絡日漸復雜，供應鏈中各利益方之間競爭與合作的機會并存。舉例而言，在電子設備行業中，常常可以看到多個生產商將某些特定的生產工序，外包給同一個第三方代工商的情況，如蘋果、三星等電子品牌同代工商富士康之間的關系。基于該行業中信息的高效傳遞性及高度共享性，這些生產商與第三方代工商之間可以通過設定合作機制，從而使實現生產調度的全局優化成為可能。

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

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

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

一、研究問題描述

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

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

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

二、模型設計

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

結語

本文對考慮外包的生產調度問題及潛在的合作博弈的可能進行了建模研究。通過建立了考慮在制品庫存成本和預訂成本的生產模型，研究了相應的合作博弈問題，給出了一組均衡解的分配原則。

[參 考 文 獻]

[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

[責任編輯：潘洪志]