謝 謝, 鄭勇躍, 劉 柳, 李曉麗

(1. 沈陽大學(xué) a. 裝備制造綜合自動化重點實驗室, b. 信息工程學(xué)院, 遼寧 沈陽 110044; 2. 遼寧省檢驗檢測認(rèn)證中心 事業(yè)發(fā)展中心, 遼寧 沈陽 110032; 3. 吉林省雙遼市職業(yè)高級中學(xué), 吉林 雙遼 136400)

鋼鐵生產(chǎn)需要經(jīng)過煉鐵、煉鋼、精煉、連鑄等過程。廢鋼經(jīng)由高爐鐵水的加工過程變成鐵水,經(jīng)由吊機(jī)吊至轉(zhuǎn)爐進(jìn)行煉鋼,煉成的鋼水再由吊機(jī)吊至精煉爐進(jìn)一步提純,精煉結(jié)束后再由吊機(jī)吊至連鑄機(jī)上進(jìn)行連鑄加工,連鑄結(jié)束后經(jīng)由吊機(jī)進(jìn)行熱軋或冷軋等軋制過程。在每個環(huán)節(jié)中都有多臺加工設(shè)備,各環(huán)節(jié)由吊機(jī)進(jìn)行銜接。吊機(jī)是鋼鐵生產(chǎn)企業(yè)中必不可少的運輸設(shè)備,幾乎每個關(guān)鍵生產(chǎn)階段加工工序的過程都由它銜接。這種吊機(jī)頻繁參與生產(chǎn)的加工模式在裝備制造業(yè)中越來越普遍,驅(qū)動著生產(chǎn)者為適應(yīng)個性化定制生產(chǎn)模式努力實現(xiàn)柔性生產(chǎn)。由于吊機(jī)是各階段生產(chǎn)之間必不可少的銜接設(shè)備,而每個生產(chǎn)階段都有多臺相同的加工工具,因此,我們將m臺機(jī)器流水車間調(diào)度問題進(jìn)行擴(kuò)展,將問題擴(kuò)展為帶有吊機(jī)運輸?shù)牧魉囬g作業(yè)的吊機(jī)與多階段生產(chǎn)協(xié)調(diào)調(diào)度問題,目標(biāo)函數(shù)是被加工工件的最小化最大完工時間。

隨著生產(chǎn)與吊機(jī)銜接制造過程的大規(guī)模應(yīng)用,這種多階段且生產(chǎn)與運輸銜接的柔性制造方式正逐漸取代傳統(tǒng)的制造車間,相應(yīng)的優(yōu)化技術(shù)也成為當(dāng)前的研究熱點。傳統(tǒng)的單一生產(chǎn)調(diào)度已經(jīng)不能滿足客戶的大規(guī)模個性化需求,隨著吊機(jī)這樣的大型運輸設(shè)備的廣泛使用,企業(yè)迫切需要設(shè)計新的優(yōu)化方法以降低生產(chǎn)成本、縮短制造周期以提高市場競爭力。本文研究的問題以鋼鐵企業(yè)生產(chǎn)過程中吊機(jī)參與總流程為背景,提煉出一類吊機(jī)與多階段生產(chǎn)協(xié)調(diào)調(diào)度問題。

如果僅對吊機(jī)調(diào)度問題進(jìn)行研究,Philips等[1]提出了電鍍生產(chǎn)線的抓鉤(hoist scheduling problem)調(diào)度,這是關(guān)于吊機(jī)調(diào)度最早的研究。另外兩處頻繁使用吊機(jī)的場景為港口碼頭的岸邊吊機(jī)[2](quay crane scheduling problem)和集裝箱存儲區(qū)域的場地吊機(jī)(yard crane scheduling problem)。Sun等[3]研究了集裝箱終端的岸吊調(diào)度,通過分析工作量的分配結(jié)構(gòu)建立了一個新數(shù)學(xué)模型,并且提出了一個簡單的處理吊機(jī)不交叉約束的方法。所提出的數(shù)學(xué)模型基于邏輯的Benders分解,將問題分解為工作量分配的主問題以及操作順序的子問題,這種基于邏輯的分解保證了算法的收斂,計算結(jié)果表明所提出算法的有效性。Kress等[4]考慮了同一跨上2臺吊機(jī)可中斷的集裝箱運輸過程,也就是允許一臺吊機(jī)將某一集裝箱放置在中轉(zhuǎn)存儲區(qū)域,再由另一臺吊機(jī)運輸?shù)剿哪繕?biāo)位置。比起經(jīng)典算法,該算法在縮短最大完工時間上是有效的,他們提出了一個動態(tài)規(guī)劃算法以及一個相關(guān)的定向搜索算法,動態(tài)規(guī)劃算法使用了定界技術(shù)并應(yīng)用了最優(yōu)解的統(tǒng)治性質(zhì)。計算實驗證明了動態(tài)規(guī)劃算法的性能超過CPLEX可以快速求解問題的實例。定向搜索算法能夠快速地改進(jìn)已有文獻(xiàn)提出的啟發(fā)式算法的解。文獻(xiàn)[5-8]研究了關(guān)于集裝箱碼頭的多吊機(jī)調(diào)度最新的問題及算法,以及吊機(jī)在三維空間上的揀選操作。

在鋼鐵企業(yè)中,由于被吊的是高溫液態(tài)物件,具有溫降等特征,因此鋼鐵企業(yè)吊機(jī)調(diào)度問題相對復(fù)雜、研究結(jié)果比較少,已有的研究主要集中于某個生產(chǎn)環(huán)節(jié)中。有關(guān)冷軋等需要吊機(jī)反復(fù)參與的過程,Zapfel等[9]首次研究了鋼卷倉庫中存、取鋼卷的單吊機(jī)調(diào)度問題。他們將吊機(jī)調(diào)度看作經(jīng)典車間調(diào)度并建立了一個非線性規(guī)劃模型,提出基于局部搜索的啟發(fā)式算法,并通過計算實驗測試了算法的性能。Tang等[10]對優(yōu)化板坯及板卷倒垛和存取順序的吊機(jī)調(diào)度進(jìn)行研究,分別建立線性規(guī)劃模型,提出有效不等式加速模型的求解,對特殊情況提出多項式時間內(nèi)可解的最優(yōu)算法、對一般情況提出貪婪的啟發(fā)式算法并進(jìn)行最壞性能分析。有關(guān)鋼鐵企業(yè)吊機(jī)調(diào)度問題,謝謝等[11-12]就雙吊機(jī)和多吊機(jī)調(diào)度問題進(jìn)行了建模和性質(zhì)分析,并分類討論,他們側(cè)重于研究吊機(jī)間的避讓問題,并沒有考慮吊機(jī)與生產(chǎn)設(shè)備之間的銜接。本文將吊機(jī)調(diào)度與多階段生產(chǎn)調(diào)度問題集成考慮,提出了一類帶有吊機(jī)運輸?shù)牧魉囬g作業(yè)的最小化最大完工時間問題。

1 問題的定義及描述

以實際生產(chǎn)為背景,本文的問題描述如下:問題由吊機(jī)運輸和生產(chǎn)2個階段組成,吊機(jī)運輸階段,位于存儲區(qū)域的工件(通常是鐵水包、鋼包等被吊物件)要由吊機(jī)運輸至生產(chǎn)機(jī)器進(jìn)行生產(chǎn),生產(chǎn)階段共有m臺不同功能的機(jī)器(煉鐵、煉鋼、精煉、連鑄、軋制等)。給定一個需要調(diào)度的n個工件的集合N={1,2,…,n},初始時刻所有工件都位于存儲區(qū)域等待吊機(jī)運輸。由于吊機(jī)只能架設(shè)在固定的軌道上,因此每個生產(chǎn)環(huán)節(jié)都配備一臺吊機(jī)。每臺吊機(jī)一次只能運輸一個工件。這些吊機(jī)初始時刻也位于相應(yīng)的存儲區(qū)域。工件的運輸時間是與工件相關(guān)的,即工件j需要的被吊運輸時間為tj,j=1,2,…,n,吊機(jī)的空移動時間為常數(shù)t,假設(shè)工件的裝載和卸載時間已包含在運輸時間內(nèi)。

數(shù)學(xué)符號定義如下:

N----被吊物件(工件)的集合{1,2,…,n};

m----系統(tǒng)中加工機(jī)器總數(shù)或吊機(jī)數(shù)目;

p(i,j)----工件j(j=1,2,…,n)在機(jī)器i(i=1,2,…,m)上的加工時間;

t(i,j)----吊機(jī)將工件j裝載移動到機(jī)器i的時間;

t----吊機(jī)的空移動時間;

C(i,j)----工件j(j=1,2,…,n)在機(jī)器i(i=1,2,…,m)上的完工時間;

Cmax(H)----啟發(fā)式算法H得到的最大完工時間;

Cmax(H*)----最優(yōu)調(diào)度H*的最大完工時間。

本文研究的問題,如果不考慮吊機(jī)的運輸,則該問題退化為經(jīng)典的m臺機(jī)器流水車間調(diào)度問題中的最小化最大完工時間問題。使用Graham等[13]的三元組表示法,該問題經(jīng)典的調(diào)度問題可以表示為Fm‖Cmax。早在1954年,Johnson[14]研究了2機(jī)流水作業(yè)F2‖Cmax問題,提出并證明使用Johnson規(guī)則在O(nlbn)時間內(nèi)即可求得該問題的最優(yōu)解。當(dāng)機(jī)器數(shù)增加到3臺時,Garey等[15]證明F3‖Cmax問題是強NP-難的。因此即使不考慮吊機(jī)調(diào)度,本文所研究的問題是強NP-難的,也就是當(dāng)問題規(guī)模增大,求解問題的算法不能在合理的時間內(nèi)得出最優(yōu)解。

2 啟發(fā)式算法及漸近性能分析

基于求解經(jīng)典的3機(jī)流水作業(yè)車間調(diào)度問題的算法,提出吊機(jī)與多階段生產(chǎn)協(xié)調(diào)調(diào)度問題的啟發(fā)式算法H。

第1步 將機(jī)器上加工時間與吊機(jī)運輸時間之和排序,選出前m-1個最小的工件,將該工件作為第一個被加工工件,安排在剩余n-1個工件之前加工;

第2步 剩余的n-1個工件的加工順序任意選擇;

第3步 計算該調(diào)度的最大完工時間。

該啟發(fā)式算法的時間復(fù)雜性為O(n)。

以下證明給出,當(dāng)問題規(guī)模充分大時,即n→∞,該啟發(fā)式是漸近最優(yōu)的。

定理1 給定工件加工時間與吊機(jī)運輸時間和為p(i,j)+t(i,j),i=1,2,…,m,j=1,2,…,n,為獨立同分布隨機(jī)變量,定義其連續(xù)分布密度函數(shù)在區(qū)間(0, 1]為φ(·)。在概率為1的情況式(1)成立。

(1)

為證明定理1,首先給出如下引理,該引理由Xia等[16]提出并證明。

引理1 基于定理1給出的參數(shù),對于每個工件j,j=1,2,…,n,有

(2)

式中,a=2, 3, …,m, w.p.1表示在概率為1的情況下成立。

證明(定理1) 將工件按照啟發(fā)式算法生成的序列重新編號,結(jié)合問題下界不等式CLB≤Cmax(H*),有

Cmax(H)-Cmax(H*)≤Cmax(H)-CLB。

(3)

結(jié)合式(1)和引理1,可以得到

由于

|θ1+θ2+…+θn|≤|θ1|+|θ2|+…+|θn|,

(5)

式中,θi為任意數(shù),i=1,2,…,n,則有以下不等式成立:

結(jié)合引理1,有式(7)成立,

(7)

我們有

(8)

根據(jù)大數(shù)定律,結(jié)合式(8),可得定理(1)。

推論1 基于定理1的假設(shè),對于問題Fm‖Cmax,任意給定的排序S,有

(9)

證明 將所有工件按照它們在第1臺機(jī)器上的加工順序重新編號。有

結(jié)合定理1及引理1的證明,可以得到式(9)。

在本文提出的啟發(fā)式算法中,除第一個工件之外,其余工件的順序可以隨機(jī)排列,則該啟發(fā)式算法的漸近最優(yōu)性不會因為剩余n-1個工件排列順序的改變而改變。以下的定理將給出證明。

定理2 啟發(fā)式算法的漸近最優(yōu)性不會受最后n-1個工件排列順序的影響。

(11)

類似地,可以證明

(12)

注意到式(13),

(13)

由式(11)～(13),進(jìn)一步根據(jù)大數(shù)定律,得到如下結(jié)論:

(14)

定理得證。

3 數(shù)值計算實驗

啟發(fā)式算法的計算實驗在Pentium-Ⅳ的PC機(jī)上運行,使用VC++6.0編程,所選擇操作系統(tǒng)為Windows XP,CPU為2.40 GHz,內(nèi)存為1 GB。

由本文理論證明可知,隨著工件數(shù)目的不斷增加,當(dāng)其趨近于無窮大時,啟發(fā)式算法的性能與最優(yōu)調(diào)度等價。為了測試中等規(guī)模的問題實例,將隨機(jī)生成問題所使用的參數(shù),其中取機(jī)器數(shù)、吊機(jī)數(shù)m∈{3, 5, 10},工件數(shù)n∈{100, 200, 500, 1 000}。工件的加工時間以及吊機(jī)的移動時間在[1, 10]之間均勻分布。對于每一種參數(shù)的組合,分別進(jìn)行10次隨機(jī)測試,然后取其平均值。表1中,將啟發(fā)式算法得到的目標(biāo)函數(shù)與問題的下界進(jìn)行了比較。表中結(jié)果為目標(biāo)函數(shù)值Cmax(H)與其下界比值的平均值。

表1 啟發(fā)式仿真實驗結(jié)果

從圖1可以看出,隨著機(jī)器數(shù)的減少啟發(fā)式算法與下界的比值接近于1,也就是說目標(biāo)函數(shù)值隨著機(jī)器數(shù)的減少而越來越接近其下界值。這是因為機(jī)器數(shù)越少,調(diào)度過程中產(chǎn)生的空閑時間越少,從而減小了目標(biāo)函數(shù)值與其相應(yīng)的下界值之間的誤差。對于固定的機(jī)器數(shù),已經(jīng)證明了隨著工件數(shù)的增多,目標(biāo)函數(shù)值越來越接近其下界值。

圖1 比值下降趨勢

4 結(jié) 論

本文研究了鋼鐵企業(yè)生產(chǎn)總流程中有吊機(jī)參與生產(chǎn)的最小化最大完工時間問題,提出了一個啟發(fā)式算法,并進(jìn)一步證明當(dāng)工件數(shù)目趨近于無窮大時,該啟發(fā)式是漸近最優(yōu)的。為了進(jìn)一步驗證該理論結(jié)果,提出了該問題下界,證明了該下界的漸近最優(yōu)性。最后,通過數(shù)值計算實驗驗證了該啟發(fā)式的漸近最優(yōu)性。未來的研究將進(jìn)一步詳細(xì)討論吊機(jī)參與車間加工的具體實施細(xì)節(jié)及多吊機(jī)之間避免相互碰撞的問題性質(zhì)。