一類多代理流水車間調度問題的合作博弈

宮 華, 孫文娟, 劉 鵬, 許 可

(1.沈陽工業大學 管理學院,遼寧 沈陽 110870; 2.沈陽理工大學 理學院,遼寧 沈陽 110159)

0 引言

流水車間調度問題是工業生產領域中研究最廣泛的問題之一,是很多實際流水線生產調度問題的簡化模型,在離散制造工業及流程工業中都有廣泛的應用。多代理生產調度是指擁有不同客戶的多個代理競爭設備資源以加工其客戶的訂單或工件,在生產過程中每個代理可具有各自的需求及優化目標,符合實際生產中多用戶多訂單的生產現狀,引起了許多學者的關注[1,2]。

傳統的多代理生產調度一般以生產企業為主體,考慮最大完工時間、加權完工時間和、提前/拖期懲罰等目標,根據車間生產環境、交貨期、加工能力等約束條件,對代理及其工件統一調度來實現總體目標達到最優。在實際生產中,不同代理的工件可能來源于不同客戶,而客戶生產成本往往依賴于工件的完工時間,代理希望客戶的成本盡可能最低,而企業生產能力有限,難以滿足所有代理需求。在這種資源有限的情況下,代理及客戶愿意通過合作結成聯盟,通過在聯盟內重新調度以減少總成本,并對總成本節省進行合理分配以達到最小化各自成本的目的。因此,利用合作博弈理論來研究多代理生產調度問題具有一定的實際意義。

在生產調度領域,CURIEL等[3]最先將合作排序博弈應用到單機調度問題中,他們考慮有n個代理,每個代理擁有一個待加工工件,各代理的成本為工件完工時間的線性函數,并且證明了該合作博弈核心非空。此后,合作博弈在調度問題中的應用逐漸發展起來。針對單機調度問題,在基本排序博弈模型的基礎上,從加工具有準備時間[4]、惡化效應[5]、學習效應[6,7]、交貨期約束[8,9]等角度進行了研究。針對并行機、流水車間等多機調度問題,也有相關的研究成果[10～13]。針對單機調度問題,CALLEJA等[14]研究了代理具有多個待加工工件的合作排序博弈,證明了在一定條件下合作博弈為平衡博弈。趙曉麗[15]針對單臺批處理機上多代理生產調度問題建立合作博弈模型,證明了多代理合作博弈與工件合作博弈均不是凸博弈,而是平衡博弈。

綜上可知,利用合作博弈理論研究生產調度問題的文獻中,大多考慮客戶或代理只有一個工件,針對代理具有多個工件的調度問題,也只是考慮單機生產環境。本文研究一類多代理流水車間調度問題,考慮擁有多個客戶的代理通過合作結成聯盟,各代理的客戶服從代理調度,建立合作博弈模型優化生產,減少客戶成本,并利用EGS規則分別對代理合作獲得的成本節省以及客戶合作獲得的成本節省進行分配,證明了EGS規則能夠產生合作博弈的一個核分配。最后通過實例驗證了所建立的博弈模型及成本分配方法的有效性。

1 多代理流水車間調度問題的合作博弈模型

1.1問題描述

本文研究的具有多代理的一類流水車間調度問題描述如下:

該問題的調度任務是確定各代理及其工件的加工順序,使得總成本U最小。

對于流水車間調度問題,各道工序上工件的加工順序不必相同,若相同,則稱該調度為置換調度。當工件的加工時間和工序相關時,由于各工件在相同機器上的加工時間也相同,在任意機器上交換兩個相鄰工件的加工順序,對在該機器前后加工工件的完工時間均無影響。若最優調度不是置換調度,那么按照在最后一臺機器上工件的調度順序,對前臺m-1機器的工件重排序,構造出的置換調度也一定是最優調度。因此,加工時間與工序相關的流水車間調度問題一定存在一個置換調度為最優調度。本文考慮工件以置換調度進入各機器完成加工。

1.2 合作博弈模型的建立

合作博弈解決的問題是:一方面在規定所有工件服從其代理按照工件最優調度排序的前提下,針對代理聯盟尋找最優調度,使得代理聯盟內所有工件的總成本節省最大;另一方面通過合理的成本節省分配方案,保證代理聯盟的穩定性,同時保證對客戶的公平性。

在多代理流水車間調度問題中,合作博弈的特征型為有序對(G,v),其中特征函數v是G的所有子集(有2|G|個)上的映射,即v:2G→R且v(?)=0。

式中,v(SA)表示代理聯盟SA通過聯盟間合作,且代理內部工件始終按照最優調度排序加工時得到的最大總成本節省。

易知,對于加工時間和工序相關的流水車間調度問題,在置換調度σ=J→{1,2,…,n}下,各工件的完工時間為:

可見,對于加工時間和工序相關的流水車間調度問題,工件的完工時間只與其在調度排序中的位置有關,而與其它工件的位置無關。因此交換任意兩個相鄰代理加工順序,不會影響其他代理的完工時間和成本。同樣,交換代理內部任意兩個相鄰工件的加工順序,也不會影響其他工件的完工時間和成本。而在一般流水車間調度問題中,由于各工件在各機器上的加工時間不同,交換代理聯盟內相鄰代理加工順序,雖不會影響聯盟前代理的完工時間和成本,但可能會影響其后代理的完工時間和成本。此外,交換某代理內的任意兩個相鄰工件加工順序,同樣也會影響該代理后其他代理工件的完工時間和成本。因此一般流水車間調度問題的合作博弈是具有外部性的。

定理1對于代理At,其工件按成本系數非增序排列的調度為At的工件最優調度。

(6)

定理2對于代理聯盟SA,按照各代理平均成本系數非增序排列得到的調度為代理聯盟最優調度。

=(αJnI-αInJ)pmax

(7)

=v(SA∪TA)

2 成本節省分配方法

本文研究的多代理流水車間調度問題的合作博弈,代理之間通過合作結成聯盟,并在聯盟內交換調度順序達到成本節省,但聯盟能否真正形成,取決于節省的成本分配是否合理。

綜上可知,基于EGS規則得到的成本節省分配是合作博弈(G,v)的一個核分配。

3 實例分析

本節通過例1來說明加工時間和工序相關的多代理流水車間調度問題的合作博弈模型及EGS分配方法。

按照初始工件排序σ0、初始加工排序σ1,以及形成代理聯盟后最優調度排序σ*加工時,各工件及各代理聯盟成本如表1所示,其中工件成本向量按照工件在初始排序σ0中的順序給出。

表1 I件及代理聯盟在不同加工排序下的成本

由表1可知,對于任意代理聯盟SA和TA,均有v(SA)+v(TA)≤v(SA∪TA),因此合作博弈具有超可加性。各代理工件通過內部合作服從代理調度獲得的成本節省為:492-459=33。代理通過合作形成大聯盟時達到最大成本節省v(G)=459-399=60。與初始調度排序σ0相比,最優調度獲得總成本節省為:492-399=93。

由式(8)可計算出各代理獲得的成本節省:

根據式(9)計算各代理工件通過內部重新排序所分配的成本節省,分別為:

由式(10)可計算出各工件的成本節省分配,具體數據如表2所示。

表2 各代理工件的成本節省分配

由表1、表2可知,工件及代理通過合作節省的成本被完全分配,且任一代理聯盟分配得到的成本之和均不小于聯盟的成本節省v(SA),驗證了EGS分配是加工時間與工序相關的多代理流水車間調度問題合作博弈的一個核分配。由于代理A4加入任何代理聯盟都不能使聯盟得到更多的成本節省,因此其代理聯盟節省成本分配為0。而代理A4的工件由于在加工時按照最優調度進行,帶來總成本節省為3,因此每個工件成本節省分配為1.5。

4 結論

本文利用合作博弈理論對具有多個代理的加工時間和工序相關的一類流水車間調度問題進行了研究。以工件完工時間的線性函數為工件的成本,在以最小化客戶成本為目標以及工件服從代理按照最優調度加工的前提下,以代理通過合作重新調度所獲得的最大成本節省為聯盟的特征函數,建立合作博弈模型,證明了EGS規則得到的分配為合作博弈的一個核分配。鑒于在代理內部,工件服從代理調度實際上也可以看成為工件之間形成合作,其合作機制與代理相似,考慮合作的公平性及穩定性,同樣利用EGS規則分配代理工件通過合作而得到的成本節省。最后通過實例驗證了合作博弈模型及成本分配方法的有效性。未來的研究工作可考慮以優化多客戶非線性成本為目標,利用合作博弈理論研究車間環境更為復雜的生產調度問題。