【正文】 37]在非合作博弈在調(diào)度中的應(yīng)用問題進(jìn)行了有益的探索，結(jié)果均驗(yàn)證了非合作博弈理論在調(diào)度中應(yīng)用的有效性。文獻(xiàn)[38]介紹了具有多客戶的分布式機(jī)器調(diào)度問題，多客戶可對應(yīng)到多個(gè)代理集，根據(jù)代理集的全局表現(xiàn)，分析了使用博弈理論設(shè)計(jì)調(diào)度機(jī)制的方法。綜述了主要設(shè)計(jì)方法和近年來取得的成果，已有成果和應(yīng)用情況表明該方法對多目標(biāo)調(diào)度問題有良好的發(fā)展前景。文獻(xiàn)[3940]針對具有不同交貨期的流水車間調(diào)度問題，具備完全信息條件下的非合作博弈生產(chǎn)調(diào)度建模方面做了一定的研究工作，將來源于不同客戶的制造任務(wù)映射為博弈模型中的局中人，將與制造任務(wù)包含的工序集對應(yīng)的可選加工設(shè)備映射為可行方案集，將各制造任務(wù)加工時(shí)間的映射為收益函數(shù)，將多目標(biāo)生產(chǎn)調(diào)度模型的求解轉(zhuǎn)化為尋求非合作博弈模型的 Nash 均衡點(diǎn)，在該均衡點(diǎn)處可得到滿足各客戶利益均衡的調(diào)度結(jié)果。作者采用遺傳算法獲得了博弈調(diào)度模型的均衡解，并對結(jié)果做了驗(yàn)證。文獻(xiàn)[41]中分析了利用進(jìn)化算法求解博弈調(diào)度模型均衡解的可能性，并驗(yàn)證了求解的收斂性。文獻(xiàn)[42]中研究了利用混沌雙變異合作粒子群求解博弈調(diào)度均衡解的方法，并將該方法利用到輪胎硫化生產(chǎn)調(diào)度中，取得了良好的效果，為該理論的應(yīng)用前景做了有益的嘗試。文獻(xiàn)[43]中研究了基于合作博弈的流水車間調(diào)度問題，針對調(diào)度過程中帶來的成本節(jié)省，利用合作博弈理論對成本節(jié)省進(jìn)行合理的分配。目前來看，博弈理論在多目標(biāo)生產(chǎn)調(diào)度中的研究與應(yīng)用目前還剛剛開始，大多針對單機(jī)調(diào)度問題，使用進(jìn)化計(jì)算方法求解博弈均衡解的研究也較少，缺乏系統(tǒng)的方法研究和性能研究，這將是一個(gè)有相當(dāng)學(xué)術(shù)價(jià)值和應(yīng)用前景的新的研究方向。15 / 70硫化車間生產(chǎn)調(diào)度是對生產(chǎn)硫化車間中硫化機(jī)器資源分配的一種數(shù)學(xué)描述，由于硫化車間生產(chǎn)調(diào)度對輪胎生產(chǎn)企業(yè)來說具有重要的實(shí)用價(jià)值，建模求解相當(dāng)復(fù)雜，所以長期受到輪胎制造企業(yè)以及國內(nèi)學(xué)者的高度的重視。隨著經(jīng)濟(jì)全球化和市場競爭的加劇，現(xiàn)代輪胎制造企業(yè)正面臨著前所未有的競爭壓力。企業(yè)為爭奪市場，必須把滿足客戶的不同需求提到首要地位。硫化車間生產(chǎn)調(diào)度中蘊(yùn)含的不同用戶的需求對有效生產(chǎn)資源的爭奪這一特點(diǎn)越來越突出，所以在硫化車間生產(chǎn)調(diào)度中更應(yīng)強(qiáng)調(diào)用戶個(gè)體的優(yōu)化需求出發(fā)。 本論文根據(jù)客戶對有限制造資源的競爭和輪胎制造方對自身利益的需求，引入非合作博弈理論來解決硫化車間多目標(biāo)生產(chǎn)調(diào)度問題。本文研究內(nèi)容切合實(shí)際，研究方法較新穎，研究結(jié)果若利用到生產(chǎn)實(shí)際中對提高制造資源的利用率、提高客戶滿意度、提高制造商的效益都具有積極的意義。因此該論文適應(yīng)了當(dāng)前企業(yè)對生產(chǎn)調(diào)度問題的實(shí)際需求，具有相當(dāng)?shù)膶W(xué)術(shù)價(jià)值，在輪胎制造企業(yè)和相關(guān)行業(yè)具有廣泛的應(yīng)用前景。針對目前異構(gòu)多目標(biāo)硫化車間生產(chǎn)調(diào)度存在的問題，本文將提出并構(gòu)建基于非合作博弈的硫化車間多目標(biāo)調(diào)度模型，將制造任務(wù)和加工完成時(shí)間映射到博弈模型中，研究使用遺傳算法進(jìn)行非合作博弈模型的 Nash 均衡點(diǎn)求解；本文還將從生產(chǎn)方全局目標(biāo)出發(fā)，尋求相應(yīng)的最優(yōu)調(diào)度，構(gòu)建生產(chǎn)方驅(qū)動的硫化車間非合作博弈模型。根據(jù)前面的研究成果繼續(xù)深入研究博弈調(diào)度框架設(shè)計(jì)方法，針對多目標(biāo)生產(chǎn)調(diào)度的其他復(fù)雜問題需求，靈活的尋求解決方案和納什均衡調(diào)度求解方法。該方法將工件看作具有獨(dú)立決策能力的個(gè)體，從而將復(fù)雜的全局決策轉(zhuǎn)化為個(gè)體優(yōu)化，簡化復(fù)雜多目標(biāo)調(diào)度問題的求解。第三章 客戶驅(qū)動的硫化車間非合作博弈研究 傳統(tǒng)的硫化車間調(diào)度任務(wù)通常綜合考慮訂單任務(wù)的需求（完工時(shí)間，加工成本等） ，來安排硫化車間的生產(chǎn)調(diào)度任務(wù)，以達(dá)到總體上利益的最優(yōu)目標(biāo)。傳統(tǒng)的生產(chǎn)調(diào)度關(guān)注調(diào)度的總體目標(biāo)的最優(yōu)值，而忽略了客戶的制造任務(wù)之間的利益沖突。傳統(tǒng)的調(diào)度很容易，導(dǎo)致某些客戶的利益得不到保證，甚至出現(xiàn)客戶不滿情況，最終導(dǎo)致企業(yè)失去客戶，從而給企業(yè)造成重大損失?？蛻趄?qū)動是指生產(chǎn)調(diào)度的安排以客戶的利益為目標(biāo)，生產(chǎn)任務(wù)的安排以客戶為核心，調(diào)度的目標(biāo)是使得客戶的每個(gè)制造任務(wù)達(dá)到最優(yōu)值，并且使得客戶的利益均衡化。本章將運(yùn)用非合作博弈理論，在完全信息下建立一種硫化車間的調(diào)度模型，通過傳統(tǒng)遺傳算法對模型進(jìn)行求解，通過求解結(jié)果驗(yàn)證模型的正確性。本章安排如下： 介紹客戶競爭驅(qū)動的硫化車間非合作博弈研究的背景以及建模的思路 對客戶驅(qū)動的硫化車間的任務(wù)進(jìn)行描述。 背景及建模思路 研究背景 隨著當(dāng)今信息技術(shù)的快速發(fā)展，科技的不斷進(jìn)步，輪胎生產(chǎn)企業(yè)之間的競爭越來越激烈。輪胎生產(chǎn)企業(yè)要想在全球化的市場競爭下生存，必須面向市場推出高性價(jià)比的產(chǎn)品，并且交貨期也已經(jīng)成為衡量一個(gè)輪胎企業(yè)的信譽(yù)的一個(gè)重要指標(biāo)，客戶總是會選擇性價(jià)比高，且信譽(yù)好的輪胎企業(yè)來提交訂單。由于輪胎訂單來自于不同的客戶，且每個(gè)客戶都想自己的訂單的加工時(shí)間最短，輪胎企業(yè)能夠按時(shí)交貨。但是輪胎企業(yè)的生產(chǎn)能力有限，經(jīng)常會出現(xiàn)顧此失彼的現(xiàn)象，于是致使客戶之間發(fā)生了競爭。傳統(tǒng)的調(diào)度并不考慮客戶之間的競爭，總是從企業(yè)自身的角度出發(fā)，安排生產(chǎn)調(diào)度，這就導(dǎo)致某些客戶訂單的交貨得不到保證，損害了企業(yè)的信譽(yù)。傳統(tǒng)調(diào)度的最大缺點(diǎn)在于忽略了客戶之間存在的競爭，因此尋求一種新的調(diào)度策略和模型，使得每個(gè)客戶都能接受訂單的完工時(shí)間，調(diào)度的目標(biāo)就是要每個(gè)客戶之間的獲得利益均衡化。輪胎企業(yè)的生產(chǎn)車間包括五個(gè)工序：煉膠、壓延、成型、硫化、檢測，如17 / 70圖 31，輪胎生產(chǎn)過程中既包含連續(xù)的生產(chǎn)過程又包含離散的生產(chǎn)過程，是一種相對復(fù)雜的生產(chǎn)過程。其中煉膠屬于間歇生產(chǎn)過程，半制品階段中如鋼絲簾布、鋼包布和零度帶束層等部件的生產(chǎn)是連續(xù)的，而其他部件的生產(chǎn)則為離散的。裁斷、成型和硫化都屬于離散生產(chǎn)過程，煉膠、半制品由于是中間包含有間歇生產(chǎn)過程或者連續(xù)生產(chǎn)過程 [44]。五個(gè)工序中硫化工序是整個(gè)輪胎生產(chǎn)中最重要環(huán)節(jié)，總結(jié)輪胎硫化工序的特點(diǎn)如下：簾線 簾布層原料胎面 、胎側(cè)膠料生胎 輪胎鋼絲圈 鋼圈簾線處理工程粘膠（ 成型工程 ）成型( 硫化工程 )加熱 、 加壓（ 壓出工程 ）（ 胎圈工程 ）刮膠（ 精煉工程 ）天然橡膠合成橡膠硫化劑等混煉圖 31 輪胎生產(chǎn)的工藝流程圖Figure 31 The sketch map of tyre basic manufacturing procedure（1）非可逆性。輪胎生產(chǎn)的最后一個(gè)工序是硫化工序，硫化工序發(fā)生的是化學(xué)反應(yīng)，是在加熱的情況下橡膠大分子與交聯(lián)劑硫磺發(fā)，交聯(lián)形成立體網(wǎng)狀結(jié)構(gòu)的過程。因此硫化工序決定著輪胎制作的成敗，輪胎一旦硫化完畢如果硫化過程出現(xiàn)了問題，輪胎是不能夠再回收利用的，因此硫化過程具有不可逆性。（2）工序時(shí)間長硫化車間的硫化工序是輪胎生產(chǎn)的五個(gè)工序中耗時(shí)最長的一個(gè)工序，硫化一條輪胎，平均要 12 個(gè)小時(shí)的時(shí)間，因此輪胎生產(chǎn)中，硫化工序是輪胎生產(chǎn)過程中的主要瓶頸。如何對硫化車間進(jìn)行合理的調(diào)度，安排生產(chǎn)計(jì)劃，是提高輪胎生產(chǎn)企業(yè)經(jīng)濟(jì)效益的關(guān)鍵所在。（3）多個(gè)優(yōu)化的目標(biāo)硫化車間的調(diào)度問題直接關(guān)系到輪胎生產(chǎn)企業(yè)的生產(chǎn)成本，硫化車間調(diào)度中存在多種要優(yōu)化的目標(biāo)，而且這些目標(biāo)之間存在沖突。輪胎生產(chǎn)企業(yè)的調(diào)度優(yōu)化的目標(biāo)分為一下三類：基于作業(yè)交貨期的目標(biāo)，基于作業(yè)完成時(shí)間的目標(biāo)和基于生產(chǎn)成本的目標(biāo) [45]。（4）輪胎的規(guī)格多客戶的訂單往往包含多種型號的輪胎，因此訂單到達(dá)硫化車間時(shí)，包含了多種多樣規(guī)格的輪胎，不同的規(guī)格的輪胎有著不同的硫化時(shí)間，訂單的多樣性決定了輪胎型號的多樣性。 （5）批次性強(qiáng)客戶提交的訂單是分牌子的，根據(jù)硫化車間的實(shí)際情況，將訂單劃分成不同的批次，分批生產(chǎn)，可以很好地利用硫化車間的硫化機(jī)，節(jié)約生產(chǎn)成本。一般硫化都是將輪胎按批次生產(chǎn)。（6）單工序、并行機(jī)本文研究的硫化車間生產(chǎn)是輪胎生產(chǎn)的最重要環(huán)節(jié)，硫化車間的生產(chǎn)直接決定著輪胎的生產(chǎn)。只有保證了硫化工序順利進(jìn)行，才能保證輪胎的交貨期，和輪胎質(zhì)量。本文只研究輪胎的硫化工序，不研究其他工序。一般每個(gè)硫化車間有多臺硫化機(jī)，所以硫化機(jī)是并行機(jī)。（7）復(fù)雜性實(shí)際生產(chǎn)中硫化機(jī)可能會出現(xiàn)故障，有許多不可控制的因素，比如緊急訂單的加入，機(jī)器意外停機(jī)，等等，許多因素人為不可控。實(shí)際的硫化車間生產(chǎn)比理論的模型復(fù)雜的多，為了研究的簡化，本文只考慮可控因素，對不可控因素不予以考慮。因此本文研究的硫化車間是一個(gè)并行的，單工序的，多個(gè)優(yōu)化目標(biāo)的模型。由于上述的特性，輪胎生產(chǎn)過程中的調(diào)度都是從后往前進(jìn)行，先確定硫化車間的調(diào)度，再根據(jù)硫化車間調(diào)度依次確定其他三個(gè)車間的調(diào)度，采取逆向調(diào)度的原則安排車間生產(chǎn)計(jì)劃。 博弈論通?？梢悦枋鰹槲鍌€(gè)方面，G=P,S,I,U,N即博弈的參與者，博弈策略，信息，參與者的收益，以及博弈的均衡等五個(gè)要素，這些要素確定一個(gè)博弈時(shí)所必須要設(shè)定的。博弈論就是利用上述因素來系統(tǒng)地研究各類的博弈問題,并尋求各博弈參與者在選擇最優(yōu)策略情況下博弈的解,即是均衡。本文將采用非合作博弈理論對硫化車間進(jìn)行多目標(biāo)調(diào)度建模。首先對硫化車間的博弈要素進(jìn)行分析如表 31。 19 / 70表 31 硫化車間博弈要素Table 31 Vulcanization workshop game elements博弈要素 博弈論的解釋 硫化車間解釋局中人（Player）指一個(gè)博弈中的決策主體，它的目的是通過選擇行動（或戰(zhàn)略）來最大化自己的支付（效用）水平。客戶提交訂單中帶加工的輪胎。策略集（Strategy）指參與人在給定信息集的情況下的行為規(guī)則，規(guī)定參與人在什么時(shí)候選擇什么行動，戰(zhàn)略告訴參與人如何對其他參與人的行為做出反應(yīng)。將可選的硫化機(jī)機(jī)器設(shè)備映射為可行性方案集合。信息（Information）指參與人有關(guān)博弈的知識?！肮餐R”指的是“所有參與人知道，所有參與的人知道所有參與人知道，所有參與人知道所有參與人知道所有參與人知道……的知識” 。各種型號的輪胎的硫化時(shí)間已知。收益（Payoff）每個(gè)主題的盈利函數(shù)。 把各型號的指標(biāo)函數(shù)看做是收益函數(shù)。均衡（Equilibrium）指所有參與人選取的最佳策略所組成的策略組合。每個(gè)客戶都采取最佳策略的組合?；谝陨系姆治霰疚牡慕Ｋ悸肥牵簩⒖蛻籼峤坏挠唵稳蝿?wù)映射為非合作博弈的局中人（P） ，并將可選的機(jī)器設(shè)備映射為可行性方案集合（S） ，使各訂單任務(wù)的加工完成時(shí)間和完成成本組合形成多目標(biāo)的綜合指標(biāo)函數(shù)映射為收益函數(shù)（U） ，把各客戶訂單任務(wù)的性能指標(biāo)加權(quán)組合形成的多目標(biāo)函數(shù)。（1）在某硫化車間中，客戶提交了 張訂單，要生產(chǎn) n 條輪胎；l（2）硫化車間有 m 臺硫化機(jī),； （3）每條輪胎的硫化時(shí)間 P={p1，p 2，…，p n}； （4） 為 在硫化機(jī)上的硫化加工時(shí)間（min）。pitiJ（5） 為 在硫化機(jī)上的硫化開始時(shí)間（min）。)(,jsimi（6） 為 在硫化機(jī)上結(jié)束時(shí)間（min） ；citiJ（7） 為輪胎半成品輪胎 i 在 輪胎上的加工費(fèi)費(fèi)用（元 /min） ；pirjm（8） 為 未按時(shí)交貨一次性的罰款金額(元)；iaiJ（9）拖期時(shí)間越長硫化成本越高， 為拖期所交罰款（元/min ） ；air（10）庫存的成本，費(fèi)用為 存放時(shí)間越長費(fèi)用越高（元/min） ；bi（11） 為 的交貨期；ditiJ（12）提前時(shí)間 ；),0max(cidiei tt??（13）拖期時(shí)間 ；lili可以將硫化車間的調(diào)度模型描述為非合作博弈的戰(zhàn)略表示： (31)),.。,.(11nnUSG?三元組表示： (32)),(1iN(33)}|{m??其中：N 為帶硫化的輪胎半成品構(gòu)成的局中人， ；,.{1nJ?Si 為 Ji 可選的硫化機(jī)策略集合，Si 可選集合{m 1， m2，… ，m n}；Ui 為 Ji 的選擇 Si 策略時(shí)的收益函數(shù)；由以上定義的 的加工成本推知：iJ (34)piitrsf?)(1,本文假設(shè)拖期費(fèi)用，以及提前完工的費(fèi)用與時(shí)間成線性關(guān)系，可以得21 / 70 （35）eibliaii trsf??)(2,總的成本由 ， 構(gòu)成.)(1,isf,ii 由于目標(biāo)函數(shù)存由 ， 部分構(gòu)成，必須對時(shí)間和成本的取值進(jìn)行)(1,isf)(2,if歸一化處理，根據(jù)客戶需求對目標(biāo)函數(shù)進(jìn)行歸一化處理，即確定響應(yīng)的權(quán)重后求和， 分別為 和 的權(quán)重且滿足 綜合以上論述給出 1?2)(1,if)(2,iif 121???（36）)(2,1, iii sfssU??約束條件：（1） 任務(wù)不能被中斷；（2） 所有輪胎半成品具有相同的優(yōu)先級；（3） 各種型號的輪胎型號已知；（4） 開始時(shí)刻，所有硫化機(jī)均可以進(jìn)行生產(chǎn)；（5） 硫化工序開始時(shí)刻為零時(shí)刻；（6） 硫化機(jī)只能同時(shí)完成一條輪胎的加工；（7） 硫化只能由一臺機(jī)器完成，不能由兩臺機(jī)器完成；（8） 硫化一旦開始到結(jié)束，不允許硫化機(jī)中斷去執(zhí)行其他任務(wù)；綜上，可以將約束歸結(jié)為 （37）pijsijsji tmtt ,1, )()(??? 非合作博弈模型的納什均衡 當(dāng)每條輪胎單獨(dú)改變策略時(shí)，都不能得到更好的收益，此時(shí)認(rèn)為達(dá)到納什均衡。 （38）),(),(**iiii sUs???公式中 。iiSs??),.,.(*1*1*niis????i,.? 根據(jù)上一小節(jié)的模型，硫化車間的調(diào)度問題就轉(zhuǎn)化為如圖 31，基于相對約束的納什均衡的點(diǎn)的求解，下一小節(jié)將涉及相應(yīng)的遺傳算法，求解納什均衡；局中人 1 :半成品輪胎 1局中人 2 :