A branch-and-price algorithm to solve the molten iron alloca

branch-and-price algorithm

Computers&OperationsResearch34(2007)3001–3015

http://doc.guandang.net/locate/cor

Abranch-and-pricealgorithmtosolvethemoltenironallocation

probleminironandsteelindustry

LixinTanga, ,GongshuWanga,JiyinLiub

bBusinessSchool,LoughboroughUniversity,Loughborough,LeicestershireLE113TU,UK

aTheLogisticsInstitute,NortheasternUniversity,Shenyang,China

Availableonline20December2005

Abstract

Themoltenironallocationproblem(MIAP)istoallocatemoltenironfromblastfurnacestosteel-makingfurnaces.Theallocationneedstoobservethereleasetimesofthemoltenironde nedbythedrainingplanoftheblastfurnacesandthetransporttimebetweentheiron-makingandsteel-makingstages.Timewindowconstraintsforprocessingthemoltenironmustbesatis edtoavoidfreezing.Theobjectiveisto ndaschedulewithminimumtotalweightedcompletiontime.Thisobjectivere ectsthepracticalconsiderationofimprovingsteel-makingef ciencyandreducingoperationcostcausedbytheneedforreheating.SuchaproblemcanbeviewedasaparallelmachineschedulingproblemwithtimewindowswhichisknowntobeNP-hard.Inthispaper,we rstformulatethemoltenironallocationproblemasanintegerprogrammingmodelandthenreformulateitasasetpartitioningmodelbyapplyingtheDantzig–Wolfedecomposition.Wesolvetheproblemusingacolumngeneration-basedbranch-and-pricealgorithm.SincethesubproblemofcolumngenerationisstillNP-hard,http://doc.guandang.netputationalexperimentsdemonstratethattheproposedalgorithmiscapableofsolvingproblemswithupto100jobstooptimalitywithinareasonablecomputationtime. 2005ElsevierLtd.Allrightsreserved.

Keywords:Moltenironallocation;Integerprogramming;Columngeneration;Branch-and-price;State-spacerelaxation;Dynamicprogramming

1.Introduction

Inironandsteelproductiontheiron-andsteel-makingstagesmustbewellcoordinatedtoachievehighproductivityandlow-energyconsumption.Intheiron-makingstage,moltenironissmeltedfromironore,limestoneandbituminouscoalinblastfurnacesandthenpouredintopotscarriedontorpedocars.Thesetorpedocarsarehauledbyenginesthrougharail-tracknetworktosteel-makingplantswherethemoltenironisusedforsteel-making.Fig.1showsthelayoutoftherailtracksformoltenirontransportationbetweentheiron-andsteel-makingplantsinShanghaiBaoshanIronandSteelComplex(Baosteel).Beforethemoltenironispuddled,itneedstoundergoapretreatment.TheprocessofmoltenironpretreatmentatBaosteelplantsisshowninFig.2.

Correspondingauthor.Tel./fax:+862483680169.

E-mailaddresses:qhjytlx@http://doc.guandang.net(L.Tang),w-gs@http://doc.guandang.net(G.Wang),j.y.liu@lboro.ac.uk(J.Liu).0305-0548/$-seefrontmatter 2005ElsevierLtd.Allrightsreserved.doi:10.1016/j.cor.2005.11.010

branch-and-price algorithm

3002L.Tangetal./Computers&OperationsResearch34(2007)3001–3015

Slag pouring

Desulphurization

Steel-making work 2#

Post-processing

Iron-pouring

Pre-processing

Removing and cleaning

Iron-pouring

parking

Pre-processing

Steel-making work 1#

Dephosphorization

Blast Furnace #1Blast Furnace #2Blast Furnace #3

http://doc.guandang.netyoutofthemoltenirontransportationtrack.

Fig.2.Flowofmoltenironandtorpedocars.

branch-and-price algorithm

L.Tangetal./Computers&OperationsResearch34(2007)3001–30153003

Moltenironschedulingisconcernedwiththeallocationofmoltenirontosteel-makingfurnacesandschedulingofthetransportationactivitiesbetweentheiron-makingandsteel-makingstages.Thewholeproblemisverycomplexandthereforeoftendecomposedandsolvedinthefollowingthreesteps.First,potsofthemoltenironfromblastfurnacesareallocatedtothesteel-makingfurnaces.Next,enginesareallocatedtothemoltenirontransportationrequestsresultedfromthemoltenironallocation.Finally,transportationroutesfortheenginesandtorpedocarsareestablished.The rststep,moltenironallocation,istodeterminetheallocationofthemoltenironfromtheblastfurnacestothesteel-makingfurnaceswithminimaltotalweightedpretreatmentcompletiontime.Inthemoltenironallocationdecisionseveralpracticalfactorssuchasthetemperaturereductionofmoltenironcausedbywaiting,theavailabilityofsteel-makingequipment,thecontinuousproductionoftheblastfurnacesandthetransporttimesmustbeconsidered.Insuf cientallocationofmoltenironwillcausethesteel-makingoperationtoshutdownandthedownstreamproductionwillbeaf ictedwithsigni cantcostpenalties.Exceedingallocationofmolteniron,ontheotherhand,willresultinfulltorpedocarsqueuingupinfrontofthesteel-makingfurnaces,increasingtheirturnaroundtimesandleavingfewertorpedocarsavailableforthedrainingoftheblastfurnaces.Withtoofewtorpedocarsavailable,theproductionrateoftheblastfurnaceswillhavetobereduced,degradingthemoltenironandintheworstcasecausingcatastrophicdamageandlengthydowntime.Inaddition,ifthetemperatureofthemoltenironisallowedtodropbelowacertainpointduetolongwaiting,itwillneedtobereheated,whichwillincreasecost.Evenworse,ifthedelayexceedsacertainnumberofhours,themoltenironwillfreeze,destroyingthetorpedocar.Thereforeoptimizingtheallocationofthemoltenironfromtheblastfurnacestothesteel-makingfurnacescanimprovetheoverallef ciencyandreduceenergyconsumptionintheintegratedsystem.

AtpresenttheschedulingofmoltenironinBaosteelhasachievedgreatsuccesswiththehelpofcomputer-aidedautomation,whilemoltenironallocation,themostcriticalpartoftheprocess,isstillaccomplishedbymanualoperation.Baosteelisequippedwith3blastfurnacesforiron-making,5convertersand1electricarcfurnaceforsteel-making.Generally,Baosteeldispatchersusethefollowingschemeformoltenironallocation.Moltenirondrainedfromblastfurnaces#1and#2isassignedtoconverters#1,#2and#3;andmoltenirondrainedfromblastfurnace#3isassignedtoconverters#4,#5andtheelectricarcfurnace.Ifblastfurnaces#1and#2cannotsupplyenoughmoltenirontoconverters#1,#2and#3,blastfurnace#3alsosuppliesmoltenirontothem.Whenblastfurnace#3cannotsupplyenoughmoltenirontosatisfytheirdemands,blastfurnaces#1and#2willalsosupplymoltenirontoconverters#4,#5andtheelectricarcfurnace.

…… 此处隐藏：36070字，全部文档内容请下载后查看。喜欢就下载吧 ……