合作博弈在硫化車間生產(chǎn)調(diào)度中的應(yīng)用研究*

胡乃平　張立英

(青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院　青島　266042)

?

合作博弈在硫化車間生產(chǎn)調(diào)度中的應(yīng)用研究*

胡乃平張立英

(青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院青島266042)

摘要針對輪胎加工生產(chǎn)過程中硫化車間的生產(chǎn)調(diào)度成本問題,基于客戶成本需求,建立基于合作博弈的生產(chǎn)調(diào)度模型,設(shè)計采用自適應(yīng)遺傳算法對模型進行求解,達(dá)到降低硫化車間生產(chǎn)成本的目的。實驗仿真結(jié)果證明了該模型的有效性和可行性。該方法的應(yīng)用相對于普通生產(chǎn)調(diào)度,能夠更有效地減少車間成本。

關(guān)鍵詞合作博弈; 硫化車間; 生產(chǎn)調(diào)度; 生產(chǎn)成本

Production Scheduling of Vulcanization Workshop Based on Cooperative Game

HU NaipingZHANG Liying

(School of Information Science & Technology, Qingdao University of Science and Technology, Qingdao266042)

AbstractFor costs of production scheduling in tire curing workshop production processes based on customers’ demands, a cooperative model based on lowering production costs vulcanization workshop is built. Adaptive genetic algorithm is adopted to solve this model to reduce production costs. Simulation experiments show that this model is effective and feasible. Application of this method for production scheduling, can more effectively reduce costs than other methods.

Key Wordscooperative game, curing workshop, production scheduling, production costs

Class NumberTP272

1引言

硫化車間生產(chǎn)調(diào)度問題是一類經(jīng)典的有多約束條件和多優(yōu)化指標(biāo)要求的、關(guān)于稀少的生產(chǎn)資源能否合理分配的問題,它是一類復(fù)雜的生產(chǎn)調(diào)度問題[1~2]。在硫化車間中生產(chǎn)資源的有限性使得傳統(tǒng)的硫化車間調(diào)度方法通常只考慮客戶之間競爭有限資源的問題,很少有考慮客戶之間以合作的方式來解決調(diào)度中的問題[3]。目前國內(nèi)外對生產(chǎn)調(diào)度的研究日益關(guān)注,博弈也逐漸被用來解決生產(chǎn)調(diào)度問題[4~6]。合作博弈也因此逐漸被用在生產(chǎn)調(diào)度中解決調(diào)度問題[7~8]。

本文基于硫化車間的生產(chǎn)調(diào)度問題,針對輪胎硫化車間生產(chǎn)的現(xiàn)狀以及輪胎加工生產(chǎn)過程中硫化車間的生產(chǎn)調(diào)度,擬從合作博弈理論的基本原理入手,研究客戶之間以合作的方式建立聯(lián)盟,構(gòu)建硫化車間相關(guān)的生產(chǎn)調(diào)度合作博弈模型,將成型車間看作是需要硫化半成品輪胎的客戶,基于客戶的成本需求,將多個客戶的待硫化任務(wù)映射成博弈中的局中人,待硫化任務(wù)可選的硫化機編號排序映射為可行策略集,將硫化車間的成本映射成硫化車間成本函數(shù),以滿足客戶方的成本需求。將硫化車間的設(shè)計采用自適應(yīng)遺傳算法求解該模型,通過實驗仿真證明該模型的正確性和有效性。

2基于合作博弈的硫化車間生產(chǎn)調(diào)度建模

2.1硫化車間調(diào)度問題

基于成本的需求,一個簡單的硫化車間調(diào)度問題可描述為一個六元組,(Ni,Si,Pi,Ui,σ0,d,e),其中:

1)Ni為帶硫化的輪胎半成品構(gòu)成的局中人,N={J1,…,Jn};

2)Si為Ji可選的硫化機策略集合,Si可選集合{m1,m2,…,mk};

3)Pi是加工任務(wù)的加工時間向量,p=(pij)i∈Ni,j∈Si,且pij>0;

4)Ui為Ji的選擇Si策略時的成本函數(shù),若客戶在交貨期限內(nèi)完成,則客戶支出成本與完工時間成線性關(guān)系;若客戶拖期,則客戶支出成本需要在線性成本基礎(chǔ)上增加拖期懲罰;

5)σ0為初始任務(wù)排序;

6)d表示加工任務(wù)的交貨期集,d=(di)，i∈Ni;

7)e表示加工任務(wù)延遲交貨的拖期懲罰,e=(ei),i∈Ni;

G=(S1,…,Sn;U1,…,Un)

(1)

因此硫化車間的調(diào)度問題的合作博弈模型的數(shù)學(xué)表述為

G=(Ni,Si,Pi,Ui,σ0,d,e)

N={N|1≤i≤m}

(2)

由以上定義的Ji的加工成本推知:

(3)

在本文中,拖期不交貨的懲罰額度和提前完成交貨任務(wù)的成本與半成品輪胎硫化的加工完工時間呈線性關(guān)系,因此可以得到拖期成本為

(4)

整個硫化任務(wù)的成本函數(shù)由Ui,1(si),Ui,2(si)構(gòu)成。

由于總成本函數(shù)由Ui,1(si),Ui,2(si)兩部分構(gòu)成,因此歸一化處理后才能簡化計算。確定兩部分成本的相應(yīng)權(quán)重,且ω1+ω2=1,總成本函數(shù)就簡化為

Ui(si)=ω1Ui,1(si)+ω1Ui,2(si)

(5)

2.2合作博弈模型的建立

硫化車間的客戶采用合作機制,相互之間轉(zhuǎn)讓加工任務(wù)的優(yōu)先權(quán),則所有任務(wù)排序中有一個最佳排序,是合作聯(lián)盟的最小加工成本[9]。所有排序為ΠN,最佳排序為σn。在上面模型描述中,最佳生產(chǎn)任務(wù)排序下,客戶的總加工成本為由式(5)可給出。

所有客戶的總加工成本為

UN=∑i∈NUi(si)(1≤i≤N)

(6)

所有客戶的初始加工總成本為UN=∑i∈NUi(si)。該調(diào)度下,所有客戶都有與加工時間和完工時間相關(guān)的加工成本。從全局角度看,必然有一個使所有客戶的總加工成本最低的調(diào)度排序使得所有客戶最終的加工成本達(dá)到最低。

各客戶如果想要減少成本支出通過合作機制進行排序調(diào)整,找到全局最優(yōu)的調(diào)度方案,然后再分?jǐn)側(cè)肿顑?yōu)調(diào)度方案帶來的成本節(jié)省,因此能夠使得客戶自身的加工成本下降。根據(jù)上面的定義,生產(chǎn)調(diào)度的合作博弈模型可以定義為

(7)

V(N)表示通過客戶的合作,所有客戶的總成本節(jié)省。

通過定義,基于客戶成本需求的硫化車間生產(chǎn)調(diào)度問題就轉(zhuǎn)換為最大化合作博弈調(diào)度聯(lián)盟的成本節(jié)省問題,能夠使合作博弈調(diào)度聯(lián)盟總成本節(jié)省最大的調(diào)度方案就是基于成本需求的硫化車間生產(chǎn)調(diào)度的最優(yōu)解。

3合作博弈模型的求解

遺傳算法作為一種迭代算法,經(jīng)常用來求解最優(yōu)問題[10]。本文為了驗證所提出硫化車間合作博弈模型正確性、合理性,設(shè)計使用自適應(yīng)遺傳算法進行求解。由于遺傳算法中影響算法行為和性能關(guān)鍵的是交叉概率和變異概率,而標(biāo)準(zhǔn)遺傳算法中,交叉概率和變異概率是固定不變的,這直接影響算法收斂性[11]。因此本文基于自適應(yīng)遺傳算法能夠根據(jù)每一代的結(jié)果自適應(yīng)產(chǎn)生動態(tài)交叉概率和變異概率,從而快速地收斂的優(yōu)點,設(shè)計交叉概率和變異概率參數(shù)自適應(yīng)的遺傳算法求解該模型。

硫化車間的合作博弈的調(diào)度模型目標(biāo)是得到使硫化成本最低的調(diào)度排序,與以往的目標(biāo)有所不同,因此為了滿足客戶和加工方的各自需要,滿足客戶間相互合作的新需求,需要重新設(shè)計一個新的適應(yīng)度函數(shù),設(shè)計如下

(8)

(9)

(10)

3.1實驗初始化條件和參數(shù)

本文使用如下數(shù)據(jù)進行仿真實驗驗證。實驗中假設(shè)所有客戶訂購了16條輪胎,有4臺硫化機,相關(guān)的初始化參數(shù)如表1和表2所示。本文中,為降低后續(xù)合作博弈成本節(jié)省的分配的難度,不允許待硫化輪胎跨硫化機調(diào)整加工順序。

表1　硫化任務(wù)初始相關(guān)參數(shù)

表2　遺傳算法輸入?yún)?shù)

3.2結(jié)果與分析

仿真結(jié)果如表3、表4、表5所示,表3表示遺傳算法部分后代的調(diào)度結(jié)果,表4為遺傳算法調(diào)度的部分代成本比較,表5為遺傳算法部分代的成本節(jié)省。

表3　調(diào)度結(jié)果

表4　調(diào)度結(jié)果成本比較

表5　調(diào)度結(jié)果成本節(jié)省

仿真結(jié)果表明,在800代時候算法達(dá)到穩(wěn)定的成本節(jié)省,以后各代結(jié)果與800代的結(jié)果相同,表明該算法,每個客戶達(dá)到成本節(jié)省的最大值,結(jié)果表明硫化車間調(diào)度模型和求解算法的有效性。

4結(jié)語

本文結(jié)合合作博弈的特點和硫化車間生產(chǎn)調(diào)度問題的實際情況,針對客戶成本需求問題,建立了基于合作博弈的硫化車間生產(chǎn)調(diào)度模型。設(shè)計采用遺傳算法對模型進行求解,對實驗進行仿真后得出的實驗結(jié)果符合預(yù)期結(jié)果,以此證明基于合作博弈的硫化車間調(diào)度模型是合理、可行的。但是對于合作博弈模型的解的分析和合作聯(lián)盟成立后的總節(jié)省成本的分配等還需進一步研究。

參 考 文 獻

[1] 李臣星.基于非合作博弈的多目標(biāo)硫化車間生產(chǎn)調(diào)度研究[D].青島:青島科技大學(xué),2013:1-65.

LI Chenxing. Study on vulcanization workshop production scheduling based on non-cooperative game[D]. Qingdao: Qingdao University of Science and Technology,2013:1-65.

[2] 劉丹,陳亮,王偉.一種基于合作博弈的多目標(biāo)設(shè)計問題求解方法[J].機械設(shè)計,2014,(8):3.

LIU Dan, CHEN Liang, WANG Wei. Solving methods of multi-objective problems based on cooperative game,2014,(8):3.

[3] 李臣星.客戶驅(qū)動的硫化車間非合作博弈生產(chǎn)調(diào)度研究[J].科技信息,2013,(13):452-452.

LI Chenxing. Study on vulcanization workshop Production Scheduling based on non-cooperative game for customers’ cost demand[J]. Technology Information,2013,(13):452-452.

[4] 周艷平.基于博弈理論的多目標(biāo)生產(chǎn)調(diào)度問題研究[D].上海:華東理工大學(xué),2012:1-78.

ZHOU Yanping. Research of Production Scheduling Problem based on Game theory[D]. Shanghai: East China University of Science and Technology,2012:1-78.

[5] Zhou Yanping, Gu Xingsheng. Research on Flow Shop Scheduling Problem with Multi-customer and Fuzzy Due Date Based on Non-cooperative Games, 2008 IEEE International Symposium on Knowledge Acquisition and Modeling Workshop Proceedings,2008:968-976.

[6] Zhou Yanping, Gu Xingsheng. Research on No-wait Flow Shop Scheduling Problem with Fuzzy Due Date Based on Evolution Games, 2009 2nd IEEE International Conference on Computer Science and Information Technology,2009:490-494.

[7] 王昱文.合作博弈理論的生產(chǎn)調(diào)度應(yīng)用[J].商業(yè)經(jīng)濟,2014,(3):21-25.

WANG Yuwen. Application of Cooperative game theory in Production Scheduling[J]. Business Economics,2014,(3):21-25.

[8] 周艷平,顧幸生.一類流水車間調(diào)度的合作博弈[J].化工學(xué)報,2010,61(8):1983-1987.

ZHOU Yanping, GU Xingsheng. Flow Shop Scheduling based on cooperative game[J]. Chemical Technology,2010,61(8):1983-1987.

[9] Curiel I, Pederzoli G, Tijs S. Sequencing games[J]. European Journal of Operational Research,1989,40(3):344-351.

[10] 郭海東.遺傳算法及其在生產(chǎn)調(diào)度中的應(yīng)用研究[D].杭州:浙江工業(yè)大學(xué),2004:18-74.

GUO Haidong. Genetic Algorithm and Its Application in Production Scheduling[D]. Hangzhou: Zhejiang University of Technology,2004:18-74.

[11] 李敏強.遺傳算法的基本理論與應(yīng)用[M].第一版.北京:科學(xué)出版社,2002:16-69.

LI Minqiang. Basic theory and application of Genetic algorithms[M]. First Edtion. Beijing: Science Press,2002:16-69.

中圖分類號TP272

DOI:10.3969/j.issn.1672-9722.2016.02.003

作者簡介:胡乃平,男,博士,教授,碩士生導(dǎo)師,研究方向:工業(yè)信息化。張立英,女,碩士研究生,研究方向:工業(yè)信息化。

基金項目:山東省高等學(xué)?？萍加媱濏椖?編號:J09LG16,J14LN31);山東省自然科學(xué)基金項目(編號:ZR2011FL001)資助。

*收稿日期:2015年8月11日,修回日期:2015年9月26日