鋼鐵企業(yè)中具有柔性分組決策的多吊機集成調(diào)度問題

謝 謝,鄭勇躍,楊文俊

(1.沈陽大學裝備制造綜合自動化重點實驗室,遼寧 沈陽 110044;2.遼寧省標準化研究院,遼寧 沈陽 110004;3.西安交通大學 電子與信息工程學院,陜西 西安 710049)

鋼鐵企業(yè)中具有柔性分組決策的多吊機集成調(diào)度問題

謝 謝1,鄭勇躍2,楊文俊3

(1.沈陽大學裝備制造綜合自動化重點實驗室,遼寧 沈陽 110044;2.遼寧省標準化研究院,遼寧 沈陽 110004;3.西安交通大學 電子與信息工程學院,陜西 西安 710049)

以鋼鐵企業(yè)煉鋼過程為背景,研究了一類具有柔性分組決策的多吊機調(diào)度問題.由于該問題是NP難的,在對該問題性質(zhì)分析的基礎上提出了一個啟發(fā)式算法,對于問題的一個限制情況,證明了啟發(fā)式的最壞性能,對于一般情況,算法的性能通過計算實驗進行了估測.實驗結果表明,所提出的啟發(fā)式算法可以在允許的時間內(nèi)產(chǎn)生高質(zhì)量的解.

吊機調(diào)度;強NP難;啟發(fā)式算法

鋼鐵是迄今為止最廣泛使用的金屬材料,至今對社會的發(fā)展至關重要.自1990年起,中國的鋼鐵工業(yè)取得了實質(zhì)性的改變和驚人的成就.通常每個公司的鋼鐵生產(chǎn)計劃包括鋼包分配、吊機分配以及在生產(chǎn)運輸協(xié)調(diào)調(diào)度過程中的吊機調(diào)度等.在鋼廠的生產(chǎn)實際中,吊機通常和其他運輸工具有聯(lián)系.這些運輸工具彼此相互影響.尤其吊機調(diào)度大大影響了鋼鐵生產(chǎn)的完工時間.

每個鋼包里已經(jīng)融化的鋼水首先被臺車運輸,之后再由假設在臺車軌道上方的吊機吊至平行放置的轉爐中.這個過程對于吊機來說是一個裝載移動.當?shù)鯔C把鋼包的鋼水倒入后,吊機將空鋼包移動到臺車后再執(zhí)行下一次移動.通常鋼鐵企業(yè)生產(chǎn)車間有多個吊機(如圖1).吊機沿著區(qū)域上方的跨移動同時吊鉤沿著跨間的橋移動.這種方法可以使吊鉤到達區(qū)域上方的任何位置.目標函數(shù)為確定吊機的裝載移動順序以最小化所有需求鋼水的最大完工時間.

圖1 煉鋼車間一個區(qū)域的多吊機調(diào)度問題Fig.1 Multiple crane scheduling problem in the area of the steelmaking shop

大多數(shù)關于鋼鐵企業(yè)吊機調(diào)度的文獻集中在倉庫背景中.Zapfel和Wasner[1]首次研究了鋼卷倉庫中存、取鋼卷的單吊機調(diào)度問題.他們將吊機調(diào)度看做經(jīng)典車間調(diào)度,并建立了一個非線性整規(guī)劃模型,提出基于局部搜索的啟發(fā)式算法并通過計算實驗測試了算法的性能.已知板卷的到達和需求時間,Rei等人[2]研究了單吊機存取板卷的調(diào)度問題以最小化吊機移動的次數(shù).Tang等人[3]考慮了鋼卷倉庫中板卷倒垛與搬運集成作業(yè)的單吊機調(diào)度問題,建立混合整數(shù)規(guī)劃模型并分析最優(yōu)性質(zhì),對特殊情況和限制情況分別提出多項式時間最優(yōu)算法和動態(tài)規(guī)劃算法,對于大規(guī)模問題,設計啟發(fā)式算法并證明該算法的最壞性能.Xie等人[4]設計了一個遺傳算法求解該問題,并分析了算法的最壞性能.Xie等人[5]將該問題擴展為多吊機同時調(diào)度的情況,建立混合整數(shù)規(guī)劃模型,分析可行性質(zhì)并給出了下界,設計啟發(fā)式算法并證明算法的最壞性能.Tang等人[6]對優(yōu)化板坯及板卷倒垛和存取順序的吊機調(diào)度進行研究,分別建立線性規(guī)劃模型,提出有效不等式加速模型的求解,對特殊情況提出多項式時間內(nèi)可解的最優(yōu)算法、對一般情況提出貪婪的啟發(fā)式算法并進行最壞性能分析.

對于吊機參與生產(chǎn)的過程,Tanizaki等人[7]研究了煉鋼過程的多吊機調(diào)度問題,建立混合整數(shù)規(guī)劃模型并提出混合了深度優(yōu)先和廣度優(yōu)先的啟發(fā)式算法.Dohn和Clausen[8]研究了板坯計劃和吊機調(diào)度問題,建模為計劃和調(diào)度兩部分,分別產(chǎn)生吊機從當前狀態(tài)到目標狀態(tài)的一系列操作并設計吊機操作開始時間的精確算法.Xie等人[9]以鋼卷包裝過程為背景,研究了基于重入車間建模策略的吊機調(diào)度問題,證明該問題是強NP-難的,分別針對吊機與一臺及多臺機器銜接的情況,給出啟發(fā)式算法并證明算法的最壞性能比.Sun等人[10]對煉鋼連鑄過程的吊機調(diào)度問題建立帶有混合時間的Petri網(wǎng)模型,并轉化為線性模型,使用標準的CPLEX軟件求解小規(guī)模問題.增加有效不等式改進模型加速搜索獲得大規(guī)模問題的近優(yōu)解.針對罩式退火工藝,Moon,Hrymak[11]和Liu等人[12]更注重板卷軋制的過程,幾乎沒有考慮吊機的調(diào)度.Tang等人[13]研究了該過程的單吊機調(diào)度問題,建立混合整數(shù)規(guī)劃模型,證明問題是強NP-難的,分析最優(yōu)性質(zhì)并設計啟發(fā)式算法,對算法的絕對性能進行了理論分析,針對特殊情況,分別給出多項式時間內(nèi)可解的最優(yōu)算法.謝等人[14]與謝和鄭[15]分別針對參與鋼鐵企業(yè)中不同生產(chǎn)活動的多吊機調(diào)度問題進行了研究,不同于本文的研究,他們并沒有將吊機調(diào)度分組決策并調(diào)度.

迄今為止,以上文獻只是將吊機調(diào)度分開考慮,并沒有對其進行分組決策.本文研究了具有柔性分組決策的多吊機集成調(diào)度問題以最小化給定的需求鋼包的最大完工時間.由于吊機都在同一跨上運行,因此需要滿足不交叉約束.

1 問題定義和描述

研究了具有不交叉約束的多吊機調(diào)度問題以最小化需求鋼包的最大完工時間.假設鋼包從左至右依次編號1,2,…,n(見圖1).一臺吊機一次只能服務一個鋼包.本文中,提起一個需求鋼包并移動到指定轉爐稱為一次吊機操作.在這個操作中一個鋼包需要從臺車處被提起,移動到轉爐位置然后將鋼包內(nèi)鋼水傾倒其中.整個過程對于吊機來說稱為一次裝載移動.鋼包內(nèi)鋼水傾倒后吊機將空包移動回臺車處,之后吊機空移動到另一臺車去進行下一個裝載移動.對于給定的需求的鋼包集合,探究了多吊機集成調(diào)度問題以確定每一臺吊機裝載移動的順序.目標函數(shù)為最小化最大完工時間,也就是說,最小化所有鋼包傾倒結束時的完工時間.

令A為區(qū)域內(nèi)所有位置的集合,每個位置q∈A可以由它的行-列-高度坐標獨一無二地表示為(rq,cq,hq).文中的其余部分,用號碼或者坐標便于表示位置.由于位置可以由坐標獨一無二地表示,因此每個移動可以表示為以下兩種方式:toq≡trocoho,rqcqhq,eoq≡erocoho,rqcqhq.

令第j個鋼包的操作時間為pj>0,為方便表達,假設吊機從左至右編號為1,2,…,m(見圖1).注意操作時間包括吊機上提下放的裝載移動或空移動.問題就是確定一個順序以決策每一個鋼包j的開始時間sj.由于吊機的不交叉約束,策略可行是指當且僅當任意兩鋼包j,j′,滿足j

為了便于參閱,將上下文提到的全部符號列表總結如下,一些需要進一步使用的符號將在需要的時候給予定義.

n——鋼包數(shù)量,鋼包從左至右依次編號為1,2,…,n;

A——區(qū)域內(nèi)所有位置的集合;

q∈A——每個位置q的行-列-高度坐標(rq,cq,hq);

toq——位置o和q之間的裝載移動時間,由于每個位置可以用坐標獨一無二地表示,因此toq≡trocoho,rqcqhq;

eoq——位置o和q之間的空移動時間,由于每個位置可以用坐標獨一無二地表示,因此eoq≡erocoho,rqcqhq;

m——吊機數(shù)量,從左至右依次編號為1,2,…,m;

sj——吊機移動鋼包j的開始時間;

σ(j)——操作鋼包j所分配的吊機號;

CA和C*——分別為由算法A產(chǎn)生的函數(shù)值和最優(yōu)目標值.

基于對問題的分析,可得到如下性質(zhì):

性質(zhì)1 任意時刻第i個吊機操作第j個鋼包,既不存在吊機i′,其中i′>i,可以操作鋼包j′滿足j′≤j,也不存在吊機i″,其中i″

為了簡化,令

進一步令CA和C*分別為由算法A產(chǎn)生的函數(shù)值和最優(yōu)目標值.類似于平行機調(diào)度問題,可以得到如下性質(zhì):

性質(zhì)2 最優(yōu)目標值的下界LB為

即使不考慮問題的柔性分組決策,當?shù)鯔C的數(shù)目m≥2時,Lim等[16]證明本文研究的問題已經(jīng)是NP-難的,幾乎不可能在可接受的時間內(nèi)求得實際問題的例子,因此使用啟發(fā)式算法是合適的,不必找到最優(yōu)解,至少可以在可接受的時間內(nèi)找到可行解.提出如下的啟發(fā)式算法.

2 啟發(fā)式算法

提出一個有效的啟發(fā)式算法.該算法將鋼包從左至右劃分為m個子集,每個子集與其中一個吊機相獨立,保證每個集合不太大.算法開始于每個吊機無排序,或已經(jīng)分配了一個鋼包的吊機當時正操作一個鋼包,每次分配鋼包給吊機,一個新的劃分解則產(chǎn)生了.

為了表示如下提出的啟發(fā)式算法,令組Ω1,Ω2,…,Ωm為調(diào)度過程m個不相交的子集.σ=(1,2,…,n)為n個鋼包的順序,將n個鋼包劃分為m個互不相交的子集.(rm0,cm0,hm0)為動態(tài)參數(shù),用來表示吊機m的初始位置以及在任何階段中吊機的當前位置.啟發(fā)式過程如下:

第1步 如果Ω1=?,計算滿足如下條件的鋼包號:

即從最左側鋼包開始,依次作為第一組,該組內(nèi)的鋼包由最左側吊機操作.

第2步 類似地,如果Ω2=?,計算滿足如下條件的鋼包號:

從第k+1個鋼包起,依次作為第二組,該組內(nèi)的鋼包分配給左側第二個吊機.

第3步 在每一組內(nèi),選擇滿足(erm0cm0hm0,rjcjhj+trqcqhq,rjcjhj)為最小的鋼包j,其中trqcqhq,rjcjhj為移動鋼包j到最近的空位q的時間.一旦時間相同,優(yōu)先分配給最左側的吊機.任何相同情況的產(chǎn)生,則選擇erm0cm0hm0,rjcjhj為最小的鋼包.意味著0時刻起從第一個鋼包到最后一個,一旦吊機空閑,則通過盡快將每個鋼包分配給吊機創(chuàng)建一個排序.

第4步 如果Ω1∪Ω2∪…∪Ωm=?,則停止,否則,轉第3步.

第1步、第2步鋼包的劃分需要耗時最多.第3步吊機的調(diào)度過程最多需要O(mnA).因此啟發(fā)式的計算復雜性為O(mn2A).在下一部分中,將進一步分析算法的計算性能.

由于算法將鋼包的子集分配給每個可獲得的吊機,最大完工時間則由其中一個子集決定.更精確地說,可由最大總加工時間決定.如果沒有劃分太多的子集,并且每個子集內(nèi)的總加工時間不太大,則如下的觀察進一步證明了所提出算法的界在2-2/m+1之內(nèi).

性質(zhì)3 如果啟發(fā)式最多劃分m組,則每組的全部調(diào)度時間不超過CH≤max{2P/m+1,pmax},結合C*≥max{P/m,pmax},則CH≤2(1-1/m+1)C*.

3 計算結果

對所提出的啟發(fā)式算法進行實驗以檢驗其有效性.算法采用C# 5.0語言編程,并且根據(jù)鋼鐵企業(yè)生產(chǎn)實際的數(shù)據(jù)求解了一系列問題的實例.這個算法在內(nèi)存為8 192 MB RAM和i7-3770 3.4 GHz的x64位計算機上用Visual C++語言編碼進行了測試.

對于每個實例,滿載移動的時間在[30,180]之間離散平均分布隨機生成;空載移動的時間在[10,60]之間離散平均分布隨機生成;鋼包和吊機的數(shù)目分別在[6,30]和[3,6]之間隨機產(chǎn)生,吊機的裝載移動和空載移動時間分別為v=2和λ=4.吊機上提或下放鋼包的時間為μ=2.5.對每一組例子,偏差率定義為(Cmax-LB)/LB×100%.平均偏差(Avg.ER)和最大偏差(Max.ER)用于評估算法的平均性能.結果見表1,其中最優(yōu)值由性質(zhì)2的下界進行了估測.為了測試吊機上提下放時間與距離無關,將該值增加一倍又測試了各實例.為了進一步測試算法的計算性能,將問題中鋼包和吊機的數(shù)目擴大,估測算法在大規(guī)模試驗中的性能,隨機生成了500個實例,結果見表2.

表1 啟發(fā)式算法與下界比的平均偏差最大偏差Table 1 Average optimality gaps of the lower bounds with respect to the heuristic algorithm

表2 啟發(fā)式算法求解大規(guī)模問題所得下界比的平均偏差最大偏差Table 2 Average optimality gaps of the lower bounds with respect to the heuristic algorithm for solving big instances

計算結果表明算法求解中小規(guī)模實例最多在1.621 4s的CPU時間內(nèi)求得問題的近優(yōu)解,即使求解大規(guī)模問題,平均偏差也不超過25%.因此,所提出的算法可以快速求解任意測試的實例(見表1),隨著鋼包數(shù)目的增加偏差逐漸減小.其中一個原因或許是鋼包的數(shù)目越多,等待時間越短.當?shù)鯔C的上提下放時間變大時,偏差也增大了.當增加時,意味著增加了目標函數(shù)的常數(shù)部分使得目標值與下界的比值變小了(見表2).當鋼包與吊機數(shù)目相同時,算法可以在很短時間內(nèi)求解大規(guī)模問題的實例,一個可能的原因是算法省略了吊機分組,隨著鋼包數(shù)目的增加,吊機的柔性分組過程增加了目標值,從而使算法的偏差逐漸增大.結合表1和表2,當?shù)鯔C的上提下放時間很少時而僅存在移動鋼包的時間,問題的求解就更有效.

4 結 論

研究了鋼鐵企業(yè)煉鋼過程的具有柔性分組決策的多吊機調(diào)度問題.在該過程中吊機將每個裝滿鋼水的鋼包吊至并倒入轉爐開始加工,目標函數(shù)為確定吊機的裝載移動順序以最小化所有需求鋼水的最大完工時間.提出一個啟發(fā)式算法.對于問題的一個限制情況,證明了啟發(fā)式算法最壞性能比,對于一般情況,根據(jù)生產(chǎn)實際數(shù)據(jù),實施計算實驗.計算結果表明,所提出的啟發(fā)式算法可以快速求得問題可接受的解.

[1]ZPFELG,WASNERM.Warehousesequencinginthesteelsupplychainasageneralizedjobshopmodel[J].InternationalJournalofProductionEconomics,2006,104(2):482-501.

[2]RUIJR,KUBOM,PEDROSOJP.Simulation-basedoptimizationforsteelstacking[C]∥Modelling,ComputationandOptimizationinInformationSystemsandManagementSciences,SecondInternationalConference,MCO2008,Metz,France-Luxembourg,September8-10,2008.Proceedings.DBLP,2008:254-263.

[3]TANGLX,XIEX,LIUJY.Craneschedulinginawarehousestoringsteelcoils[J].IieTransactions,2014,46(3):267-282.

[4]XIEX,ZHENGY,LIY.Geneticalgorithmanditsperformanceanalysisforschedulingasinglecrane[J].DiscreteDynamicsinNatureandSociety,2015:1-12.

[5]XIEX,ZHENGY,LIY.Multi-craneschedulinginsteelcoilwarehouse[J].ExpertSystemswithApplications,2014,41(6):2874-2885.

[6]TANGL,ZHAOR,LIUJ.Modelsandalgorithmsforshufflingproblemsinsteelplants[J].NavalResearchLogistics,2012,59(7):502-524.

[7]TANIZAKIT,TAMURAT,SAKAIH,etal.Aheuristicschedulingalgorithmforsteel-makingprocesswithcranehandling[J].JournaloftheOperationsResearchSocietyofJapan,2006,3(3):188-201.

[8]DOHNA,CLAUSENJ.Optimisingtheslabyardplanningandcraneschedulingproblemusingatwo-stageheuristic[J].InternationalJournalofProductionResearch,2010,48(15):4585-4608.

[9]XIEX,TANGL,LIY.Schedulingofahubreentrantjobshoptominimizemakespan[J].InternationalJournalofAdvancedManufacturingTechnology,2011,56(5/6/7/8):743-753.

[10]SUNLL,LIUW,CHAITY,etal.Craneschedulingofsteel-makingandcontinuouscastingprocessusingthemixed-timedpetrinetmodellingviaCPLEXoptimization[C]∥Proceedingsofthe18thIFACWorldCongress,Milano,Italy,2011:9482-9487.

[11]MOONS,HRYMAKAN.Schedulingofthebatchannealingprocess-deterministiccase[J].Computers&ChemicalEngineering,1999,23(9):1193-1208.

[12]LIUQL,WANGW,ZHANHR,etal.Optimalschedulingmethodforabell-typebatchannealingshopanditsapplication[J].ControlEngineeringPractice,2005,13(10):1315-1325.

[13]TANGL,XIEX,LIUJ.Schedulingofasinglecraneinbatchannealingprocess[J].Computers&OperationsResearch,2009,36(10):2853-2865.

[14] 謝謝,鄭勇躍,李彥平.工件和工具混合搬運的多吊機調(diào)度問題[J].沈陽大學學報(自然科學版),2016,28(4):291-295.

XIEX,ZHENGYY,LIYP.Jobandtoolmixedtransportationbasedmulti-craneschedulingproblem[J].JournalofShenyangUniversity(NaturalScience),2016,28(4):291-295.

[15] 謝謝,鄭勇躍.帶有機器卸載不延誤約束的多吊機調(diào)度問題[J].沈陽大學學報(自然科學版),2017,29(2):118-124.

XIEX,ZHENGYY.Multiplecraneschedulingwithno-delayconstraintsformachineunloading[J].JournalofShenyangUniversity(NaturalScience),2017,29(2):118-124.

[16]LIMA,RODRIGUESB,XUZ.Am-parallelcraneschedulingproblemwithanon-crossingconstraint[J].NavalResearchLogistics,2007,54(2):115-127.

Multiple-CraneIntegratedSchedulingProblemwithFlexibleGroupDecisioninaSteelmakingShop

XieXie1,ZhengYongyue2,YangWenjun3

(1.Key Laboratory of Manufacturing Industrial and Integrated Automation,Shenyang University,Shenyang 110044,China;2.Liaoning Institute of standardization,Shenyang 110004,China;3.School of Electronic and Information Engineering,Xi’an Jiaotong University,Xi’an 710049,China)

Based on the steelmaking process of iron and steel enterprises,a class of multiple-crane scheduling problem with flexible packet decision-making was studied.For this demonstrated NP-hard problem,a heuristic algorithm based on some analyzed properties was proposed.For a restrict case,the worst-case performance was analyzed.For the general case,the average performance of the heuristic algorithm was computationally evaluated.The results show that the proposed heuristic algorithm is capable of generating good quality solutions.

crane scheduling;NP-hard;heuristic algorithm

2016-05-23

國家自然科學基金資助項目(71672117);遼寧省自然科學基金資助項目(201602526);遼寧省高等學校杰出青年學者成長計劃資助項目(LJQ2014133).

謝 謝(1981-),女,遼寧沈陽人,沈陽大學副教授,博士.

2095-5456(2017)05-0389-05

TG 338

A

【責任編輯:李艷】