鋼鐵生產(chǎn)中具有不干涉約束的雙吊機(jī)調(diào)度問(wèn)題

謝 謝, 周 莉, 鄭勇躍

(1. 沈陽(yáng)大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽(yáng) 110044; 2. 中國(guó)標(biāo)準(zhǔn)化研究院, 北京 100191; 3. 遼寧省標(biāo)準(zhǔn)化研究院, 遼寧 沈陽(yáng) 110004)

鋼鐵工業(yè)是世界經(jīng)濟(jì)中的核心工業(yè),是工業(yè)化、現(xiàn)代化、經(jīng)濟(jì)發(fā)展的有力象征, 引領(lǐng)著建筑業(yè)、造船業(yè)、機(jī)器制造、家電和汽車業(yè)等其他工業(yè)的發(fā)展.鋼鐵生產(chǎn)是包括煉鐵、煉鋼、連鑄、精煉等多階段的生產(chǎn)模式,有關(guān)鋼鐵生產(chǎn)不同階段的詳細(xì)描述見(jiàn)文獻(xiàn)[1],其中精煉階段是生產(chǎn)中最基本的模式.在精煉階段,鋼包內(nèi)融化的鋼水首先由臺(tái)車運(yùn)輸,再經(jīng)由共享同一空中軌道的,平行的吊機(jī)將鋼包裝載到精煉爐上(見(jiàn)圖1).這個(gè)過(guò)程對(duì)于吊機(jī)來(lái)說(shuō)可以看做裝載移動(dòng).裝載移動(dòng)結(jié)束后,吊機(jī)空載移動(dòng)到臺(tái)車上實(shí)施下一個(gè)裝載移動(dòng).一旦鋼包內(nèi)鋼水精煉結(jié)束,吊機(jī)將鋼包從精煉爐卸載到臺(tái)車上.

圖1 精煉車間中兩臺(tái)吊機(jī)的布局示意圖Fig.1 Layout with two cranes in a refining shop

吊機(jī)是鋼鐵企業(yè)實(shí)際生產(chǎn)中的稀缺資源,通常精煉區(qū)域上方有2臺(tái)吊機(jī)共享同一跨.吊機(jī)移動(dòng)時(shí)它的抓取設(shè)備(吊鉤)不但沿跨方向移動(dòng),同時(shí)可以在跨間移動(dòng),這種方式可以使吊機(jī)移動(dòng)到區(qū)域的各個(gè)位置.吊機(jī)間的工作是同步的,每次最多對(duì)1個(gè)鋼包進(jìn)行操作.精煉過(guò)程不允許任意兩吊機(jī)的交叉或碰撞(吊機(jī)間的不干涉要求).圖1以5臺(tái)精煉爐為例,當(dāng)1臺(tái)吊機(jī)對(duì)1個(gè)精煉爐實(shí)施操作時(shí),另1臺(tái)吊機(jī)不能跨越當(dāng)前的這臺(tái)吊機(jī),也就是吊機(jī)調(diào)度服從不干涉約束.2臺(tái)吊機(jī)的調(diào)度影響著煉鋼過(guò)程的完工時(shí)間.因此,該過(guò)程的主要目的就是確定吊機(jī)的裝載移動(dòng)順序,以最小化需要精煉鋼水的結(jié)束時(shí)間,也就是最小化最后1個(gè)鋼包精煉結(jié)束的時(shí)間.

迄今為止,受到多數(shù)關(guān)注的吊機(jī)調(diào)度問(wèn)題的文獻(xiàn)主要集中在裝箱港口碼頭終端的背景,該類問(wèn)題首先由Daganzo[2]提出,即使是優(yōu)化吊機(jī)調(diào)度以最小化1艘船只的最大完工時(shí)間,問(wèn)題已經(jīng)被Zhu等[3],Lim等[4],Lee等[5]證明為NP完備的.當(dāng)考慮多吊機(jī)同時(shí)調(diào)度時(shí),吊機(jī)在同一跨上彼此不能交叉的約束首先由Kim和Park[6]提出,對(duì)于跨上具有任意數(shù)目的吊機(jī),Lee等[7],Lim等[8]提出并證明了一些最壞性能比為2的算法.Zhang等[9]改進(jìn)了所提出算法的界,并證明了對(duì)于任意m個(gè)吊機(jī),算法的最壞性能比為2-2/m+1<2.

不同于以上的吊機(jī)調(diào)度及經(jīng)典的生產(chǎn)調(diào)度問(wèn)題,本文考慮的吊機(jī)調(diào)度問(wèn)題需要滿足鋼鐵企業(yè)實(shí)際生產(chǎn)的具體要求,問(wèn)題集中在鋼鐵企業(yè)的精煉環(huán)節(jié),而精煉過(guò)程伴隨著大量的物耗和能耗,尤其是吊機(jī)間為避免相互干涉或碰撞,或經(jīng)常出現(xiàn)不必要的等待,或延長(zhǎng)了等待時(shí)間,或額外增加了空載移動(dòng)時(shí)間,一臺(tái)吊機(jī)調(diào)度不好往往造成資源、能源的消耗和環(huán)境的污染.此外,大多數(shù)文獻(xiàn)只是考慮了吊機(jī)的裝載、卸載,忽略了吊機(jī)的移動(dòng)時(shí)間.雖然謝謝等[10-11]考慮了吊機(jī)的移動(dòng)時(shí)間,但與本文研究的問(wèn)題不同,文獻(xiàn)[10-11]只考慮了吊機(jī)作為生產(chǎn)過(guò)程的唯一運(yùn)輸工具,并沒(méi)有考慮與臺(tái)車等工具的協(xié)調(diào).由于吊機(jī)是稀缺資源,一般精煉車間內(nèi)通常有2～3臺(tái)吊機(jī),本文主要研究2臺(tái)吊機(jī)的調(diào)度,考慮吊機(jī)間的干涉時(shí)沒(méi)有忽略吊機(jī)移動(dòng)時(shí)間.此外,從吊機(jī)運(yùn)作角度考慮適合鋼鐵實(shí)際生產(chǎn)的簡(jiǎn)單易行的方法.

1 問(wèn)題定義和描述

本文定義最大完工時(shí)間為需要精煉的鋼水最大完工時(shí)間,為精煉結(jié)束后,最后1個(gè)鋼包從精煉爐卸載到臺(tái)車上的時(shí)間.本文考慮的問(wèn)題是調(diào)度2臺(tái)吊機(jī),且避免交叉最小化需求精煉鋼包的最大完工時(shí)間.

給定L個(gè)鋼包在臺(tái)車上等待精煉.為了方便表達(dá),文中余下的部分定義臺(tái)車的位置就是鋼包的初始位置及最終位置.由于該位置固定,可以預(yù)先計(jì)算出吊機(jī)在任意兩位置間的距離.

給定從左至右沿跨方向有F個(gè)精煉爐, 由于爐子和鋼包的位置預(yù)先已知, 吊機(jī)在任意兩點(diǎn)的距離和時(shí)間都是可以計(jì)算的.每個(gè)吊機(jī)每次只能吊起1個(gè)鋼包, 每個(gè)爐子1次只能加工1個(gè)鋼包.

由于所研究的問(wèn)題是NP-難的,所以不可能在可以接受的時(shí)間內(nèi)求得大規(guī)模問(wèn)題的最優(yōu)解.因此,提出求解問(wèn)題的啟發(fā)式算法,并對(duì)算法進(jìn)行最壞性能分析.

2 啟發(fā)式算法及最壞性能分析

算法首先從左至右將L鋼包平均分成F個(gè)子集.計(jì)算每臺(tái)吊機(jī)當(dāng)前位置空載移動(dòng)到臺(tái)車提起鋼包、裝載移動(dòng)到精煉爐后再放下的時(shí)間.

第1步 從左至右將F個(gè)子集形成列表,將該列表按照每臺(tái)吊機(jī)的總操作時(shí)間平均分成2部分.

將具有相同鋼包數(shù)的2部分共享處于列表中間位置的精煉爐,也就是一些共享精煉爐的鋼包分配給1臺(tái)吊機(jī),剩下的鋼包分配給另1臺(tái)吊機(jī).下文將這些共享的精煉爐稱為交叉精煉爐.

第2步 對(duì)于可交叉部分的精煉爐,將鋼包分配給最早可能空閑的吊機(jī),一旦2臺(tái)吊機(jī)可同時(shí)操作,則將精煉爐分配給另1臺(tái)吊機(jī).

第3步 分配每一個(gè)部分給對(duì)應(yīng)的吊機(jī).

(1)

性質(zhì)1 對(duì)于2臺(tái)吊機(jī)的問(wèn)題,啟發(fā)式算法的最壞性能比為4/3.

證明 討論以下2種情況.

情況1 交叉精煉爐屬于第1部分.

根據(jù)算法第2步,則有

即

(2)

(3)

結(jié)合式(1)、式(2)得:

a

(4)

(5)

情況2 交叉精煉爐屬于第2部分.

根據(jù)算法第2步,有:

因此有:

結(jié)合式(1)和式(6),得

a≥b.

(8)

在這種情況下,根據(jù)式(8)及不交叉約束,則有

(9)

結(jié)合式(1)和式(8),有

根據(jù)式(7)和式(9),

3 計(jì)算結(jié)果

利用數(shù)值計(jì)算實(shí)驗(yàn)驗(yàn)證算法的有效性,表1證明了對(duì)于小規(guī)模實(shí)例算法的最優(yōu)間隙.算法采用C# 5.0語(yǔ)言編程,并且根據(jù)鋼鐵企業(yè)生產(chǎn)實(shí)際的數(shù)據(jù)求解了一系列問(wèn)題的實(shí)例.此算法在內(nèi)存為8 192 MB RAM和i7-3770 3.4 GHz的x64位計(jì)算機(jī)上用Visual C++語(yǔ)言編碼進(jìn)行了測(cè)試.每個(gè)實(shí)例考慮的參數(shù)如下:

(1) 裝載移動(dòng)時(shí)間t在[30, 100]之間離散平均分布隨機(jī)生成;

(2) 空載移動(dòng)時(shí)間et在[10, 50]之間離散平均分布隨機(jī)生成;

(3) 鋼包和精煉爐的數(shù)目分別在[6, 30]和[5, 10]之間離散平均分布隨機(jī)生成.

算法的質(zhì)量由跟下界LB的相對(duì)偏差(Cmax(σA)-LB)/LB*100%來(lái)度量,算法的平均誤差比(Avg.ER)、最大誤差比(Max.ER),以及算法的平均計(jì)算時(shí)間(Avg. CPU)用來(lái)度量測(cè)試實(shí)例的性能.由表1可以看出,隨著問(wèn)題規(guī)模、精煉爐、鋼包數(shù)目的增加,所提出的啟發(fā)式算法的質(zhì)量平均偏差低于22%.對(duì)于一組最小規(guī)模的問(wèn)題,相比加工時(shí)間,吊機(jī)的移動(dòng)時(shí)間很短,可以忽略.因此,該算法可以產(chǎn)生最優(yōu)解.當(dāng)精煉爐的數(shù)目與鋼包數(shù)目不接近時(shí),解的質(zhì)量保持穩(wěn)定.對(duì)于小規(guī)模實(shí)例,算法可以迅速獲得問(wèn)題的解.對(duì)于較大規(guī)模問(wèn)題,算法的計(jì)算時(shí)間也不超過(guò)1 s.

表1 啟發(fā)式算法與下界比的平均最優(yōu)間隙Table 1 Average optimality gaps of the lower bounds with respect to the heuristic algorithm

4 結(jié) 論

本文研究鋼鐵企業(yè)精煉車間的雙吊機(jī)調(diào)度問(wèn)題,考慮吊機(jī)間的不交叉約束,目標(biāo)函數(shù)為最小化給定鋼包的最大完工時(shí)間.探究了問(wèn)題的最優(yōu)性質(zhì),并提出1個(gè)啟發(fā)式算法,進(jìn)一步證明了該算法的最壞性能比為4/3.數(shù)值計(jì)算結(jié)果表明所提出的算法可以產(chǎn)生問(wèn)題的近優(yōu)解,最大偏差不超過(guò)22%,求解的時(shí)間不超過(guò)1s.未來(lái)的研究考慮擴(kuò)展到更多吊機(jī)同時(shí)移動(dòng)的問(wèn)題.