冶金3 120t2氧气转炉英文翻译

Productionschedulinginasteelmaking-continuousInthispaperwedescribeanoptimizationprocedurefornningtheproductionofsteelingotsinasteelmakingcontinuouscastingnt.Thestrictrequirementsoftheproductionprocessdefeatedmostoftheearlierapproachestosteelmakingcontinuouscastingproductionscheduling,mainlyduetothelackofinformationintheoptimizationmodels.Ourformulationoftheproblemisbasedonthealternativegraph,whichisageneralizationofthedisjunctivegraphofRoyandSussman.Thealternativegraphformulationallowustodescribeindetailalltheconstraintsthatarerelevantfortheschedulingproblem.Wethensolvetheproblembyusingabeamsearchprocedure,andcompareourresultswithalowerboundoftheoptimalsolutionsandwiththeactualperformanceobtainedinthent.Computationalexperienceshowstheeffectivenessofthisapproach.:Scheduling;ProductionSteelindustryisveryrichintermsofoperationalproblemsthatcanbemodeledandsolvedbyusingcomputerizedtechniques.Infact,duetothecompetitivepressure,manyinternationalironandsteelcorporationsaremovingtothejust-in-time(JIT)productionconcepts.CommonfeaturesoftheJITmanufacturingsystemsarethesmallsizeofthelotsandtherequestsforhighqualityproducts,timingdelivery,increasedproductivityandreducedcosts.Toalargeextent,inthesteelindustry,schedulingandrelatedissuesarestillcarriedoutbyhumanschedulerswhosecomputersupportmainlyconsistsofasimulatorofthent,whichisusedtoevaluateandcomparedifferentscenarios.Ontheotherhand,manycompaniesarenowdeveloandimplementingcomputerizedsystemsforaddressingsuchoperationalproblems,asreflectedinthemeetingsonthesubject.Thesesystemshelptoincreaseproductivityandtimingdelivery,whilereducingenergyconsumptionandproductioncosts.Steelschedulingisknowntobeoneofthemostdifficultindustrialschedulingproblems.Researchersandpractitionershaveapproachedtherelatedschedulingproblemsusingtheformulationsandtoolsofvariousdisciplines,mostlyartificialinligenceDornetal,1996,DornandShams,1996,TürksenandFazelZarandi,1998andSantosetal,2003andmathematicalprogrammingDuttaandFourer,2001,Naphadeetal,2001,Tangetal,2000,MoonandHrymak,1999,HarjunkoskiandGrossmann,2001andTangetInthispaperwedealinparticularwiththeproblemofschedulingtheproductionofstainlesssteelingotsinaproductionlinelocatedincentralItaly.Thentproducesalargevarietyofingots,tobeusedinawidesetofapplications,characterizedbythesizeandchemicalcomposition,or“grade”.Theingotformationprocess,orsteelmakingcontinuouscastingprocess,hasextremelystrictrequirementsofmaterialcontinuityandflowtimetofulfillinordertoachievesuitablepropertiesonthefinalproduct,thusmakingtheproductionschedulingproblemparticularlychallenging.Showthelayoutoftheproductionline.Theproductionisorganizedinlots,eachlotbeingcomposedofagivennumberofladlestobecastconsecutively.Theladlesbelongingtothesamelotareidenticalandareassociatedtoaspecificproductionorder.Theproductionschedulingproblemconsistsofdeterminingtheschedulingofoperationstobeperformedonmoltensteelatthedifferentproductionstagesfromsteelmakingtocontinuouscasting.Inparticular,theprocessingofstainlesssteelconsistsofasequenceofhightemperatureoperationsstartingwiththeloadingofscrapironinanelectricarcfurnace(EAF).Thetimetomeltthescrapironrangesfrom70to80minutes,includingafewminutesforsetupandfurnacemaintenanceoperations.Theliquidsteelispouredintoladlesthatacranetransportstoamachine,calledargonoxygendecarburizationunit(AOD),wherenickel,chromiumandotherelementsareaddedtothesteelinordertomeetthechemicalqualityrequirements.UsuallythedurationoftheoperationontheAODrangesbetween70and80minutes.BetweenEAFandAODthereisroomforstoringuptothreebut,sincethestoredsteelcoolsdown,itmustbereheatedintheAOD.AftertheAODtheladlesaretransportedtoaladlefurnace(LF)whichcanhostatmosttwoladles.EvenifsomeoperationsareexecutedintheLF(nomorethan30minutes),inpracticeitactsasabuffertomaintaintheladlesatthepropertemperaturebeforethelastoperation,tobeexecutedinthecontinuouscaster(CC).BetweentheLFandtheCCthereisabufferthatcanholdatmostoneladle.Aladlecanstayinthebufferatmost10minutes,otherwisetheliquidsteelcouldcooldown.IntheCCtheliquidsteeliscastandcooledtoformslabs,thetimerequiredforcastingoneladlerangesfrom60to70minutes.MoreovertheCCneedstobetooledwithaparticulartool,calledflyingtundish,whichdeterminestheformatofslabs.Iftwosubsequentladlesbelongtothesamelot,theymustbecastwithoutinterruption,otherwisethetundishdeteriorates,andasetupisnecessaryinordertosubstituteit.However,thetundishmustbechangedanywaywhenswitchingfromalottoanother,aswellasafteragivennumberofladles,rangingfromthreetoseven,whichdependsonthesteelquality.Thesizeofalotmayvary,therefore,fromonetosevenladles.Thesetuptimeneedsabout60minutes,duringwhichtheCCisblocked.Theproblemistoscheduletheproductionofagivennumberoflotswiththeobjectiveofminimizingthecompletiontimeofthelastscheduledlot,i.e.minimizingthemakespan.Werefertothisproblemassteelmakingcontinuouscasting(SCC)problem.Thetimehorizonforanningperiodis1week,whichcorrespondstoanaverageof120ladlesand30lotsforatypicalrealsizeproblem.Fig.2showstheGanttchartofascheduleinwhichtwolotsareproduced.Thefirstlotiscomposedofthreeladles,andthesecondiscomposedoftwoladles.Theprocessingtimesarenotrealistic,butareusefultohighlighttheproductionrequirementsofafeasibleschedule.Summarizingtheabovediscussion,theSCCproblemcanbemodeledaspermutationflowshopwithlimitedbuffersandthefollowingadditionalAllpartsinalotmustbesequencedTherearesequenceindependentsetuptimesonthelastmachine(CC)betweentwoconsecutivelots.Thereisano-waitconstraintbetweenanytwoconsecutivecastingoperationsinthesamelot.ThereisaperishabilityconstraintinthebufferbeforethelastmachineThepaperisorganizedasfollows.InSection2webrieflyreviewtheliturerelatedtotheSCCproblem,inSection3weintroducethenotationand,inSection4,wediscusstwomodelsfortheSCCproblem.InSection5,wedescribesomeproceduresforcomputinglowerboundstotheoptimalsolution,InSection6wedescribeourbeamsearchprocedurefortheSCCproblemand,inSection7,weillustratethecomputationalexperience.ConclusionsfollowinSection8.LitureInthissectionwebrieflyreviewtheliturerelatedtothispaper.Inparticular,inthefirstpartofthissectionwediscussthelitureonproblemsarisinginsteelmakingnts.Inthesecondpartwereviewsomegeneralapproachesforsolvingschedulingproblemsthatcanbeappliedtoindustrialcases,includingtheSCCproblemasaspecialcase.Inthelastpartofthissectionwebrieflyreviewsomerelevantpapersdealingwiththebeamsearchtechnique,analgorithmicprocedurethatweuseinthispapertosolvetheSCCproblem.SchedulingprobleminsteelmakingInanextensivesurveypaper,DuttaandFourer(2001)discussseveralproblemsarisinginasteelmakingnt.Theproblemsrangefromproductmixandblendingtoproductionschedulingandcuttingstock.Foralltheseproblems,mathematicalprogrammingapproachesarepresented.Inviewoftheirextensivesurvey,weprovideonlyabriefsummaryofrecentworkshere.Naphadeetal.(2001)formulatetheschedulingprobleminasteelmakingntusingamixedintegerformulationandsolveitusingatwolevelheuristicapproach.Tangetal.(2000)formulatetheSCCproblemusinganon-linearprogrammingmodel,andthenconvertitintoalinearprogrammingmodel,solvableusingstandardsoftwarepackages.InanotherrecentworkofTangetal.(2002),theSCCproblemisformulatedbyusinganintegerprogrammingmodelanditissolvedcombiningLagrangianrelaxation,dynamicprogrammingandheuristics.HarjunkoskiandGrossmann(2001)considertheschedulingproblems,arisingintheproductionofsteel,foralinecomposedoftwoparallelEAFs,anAOD,anLFandaCC.Theydevelopa positionstrategy,whichisabletoreducethecomputationeffortdrastically.Thisstrategyallowstotackleindustrial-sizeproblems,basedon1weektimehorizonand80ladles,obtainingfeasiblesolutionswhicharealwayswithin3%fromalowerboundoftheoptimum.ThemainlayoutdifferencesbetweenoursettingandthesettingconsideredinHarjunkoskiandGrossmann(2001)arethatinourproblemtheladlesaregroupedinlotswhereasinHarjunkoskiandGrossmanneachladleisindependentoftheothers,andanotherdifferenceisduetothepresenceoftwoparallelEAFsintheirproductionline.OtherrelevantworksfocusontheoptimizationoftheCCmachineSantosetal.,2003andSchwindtandTrautmann,2003orfurnaces,coolersandcraneoperations(Moon&Hrymak,1999).MachineschedulingwithcomplicatingAdifferentstreamofresearchrelatedtoSCCproblemdeals,moreingeneral,withothermachineschedulingproblemsexhibitingthesamecomplicatingconstraintsoftheSCCproblem.Forexample,schedulingproblemswithlimitedcapacitybuffersariseintheproductionofconcretewares(Grabowski,Pempera,&Smutnicki,1997),chemicalproductsReklaitis,1982andKimetal.,2000,aswellasintheschedulingoftrains(Şahin,1999)andintheflowcontrolofpacketswitchingcommunicationnetworks(Arbib,Italiano,&Panconesi,1990).Inthiscontext,threedifferentsettingsaretypicallydistinguished(see,forexampleSchwindt&Trautmann,2002)unlimitedintermediatestorage(UIS),finiteintermediatestorage(FIS)andnon-intermediatestorage(NIS).HallandSriskandarajah(1996)modeltheabsenceofintermediatebuffers(NIS)asablockingconstraint.Inthiscaseajob,havingcompletedprocessingonamachine,remainsonituntilthenextmachine esavailableforprocessing.Atwomachineflowshopschedulingproblem,inwhichthecapacityoftheintermediatebufferislimitedandthejobshavetobeproducedinlotsofidenticalparts,isstudiedbyAgnetis,PacciarelliandRossi(1997).Theproblemisprovedto-hard,andanalgorithmisproposedforitssolution.Thealgorithmrunsinpolynomialtimeanditisexactifsomeconditionsonthebatchsizesareotherwiseanapproximationresultholdsingeneral.Pranzo(2004)extendstheseresultstothemoregeneralcasewithsequenceindependentsetupandremovaltimesforthebatches.McCormick,Pinedo,ShenkerandWolf(1989)studyaflowshopschedulingprobleminanassemblylinehavingfinitecapacitybuffersbetweenmachines(FIS).Theymodelthepositionsoftheintermediatebuffersasmachineswithzeroprocessingtime.Theproblemwithlimitedbufferscanbethereforestudiedasablockingproblemwhereallmachineshavenointermediatebuffers.Theyalsoshowthat,onceasequenceforthejobshasbeenfound,thestartingtimeofthejobsonallmachinescanbeeasilycomputedonaprecedenceconstraintsgraph.Theydistinguishtwocategoriesofarcs:processingarcs,havinglengthequaltotheprocessingtimeoftheassociatedoperations,anddummyarcs,ofzerolength,representingtheblockingSanmartí,FriedlerandPuigjaner(1998)studytheproductionschedulingofamultipurposebatchnt.Theyintroducetheschedule-graphrepresentationwhichisabletorepresentbothunlimitedintermediatestorage(UIS)andnon-intermediatestorage(NIS)situations.Onceacompleteschedulegraphisproduced,themakespanonthegraphprovidesthetimingofeachoperation.Theyimplementabranchandboundmethodinwhichthelowerboundonthemakespanisevaluatedonapartialschedulegraph.Computationalexperienceshowsthattheiralgorithmoutperformsastandardmixedintegerprogrammingsolver.Romero,Puigjaner,HolczingerandFriedler(2004)extendtheschedule-graphrepresentation,orS-graph,andcombineitwithafeasibilitycheckbasedonlinearprogrammingtodealwithdifferentintermediatestorage,includingno-wait(orzerowait,ZW)andfiniteintermediatestorage(FIS).Intheirbranchandboundprocedurethelowerboundisbasedonthelongestpathcomputationundertheassumptionofunlimitedwaitingtime.Ifthisisnotthecase,e.g.whenno-waitoccurs,thelowerboundonthemakespaniscalculatedusingalinearprogrammingmodel.Otherrelevantworksariseinthemanagementofperishableitems.Aissaidtobeperishableifsomeofitscharacteristicsaresubjecttodeteriorationrespecttocustomer/producerrequirements.Thecoolingofliquidsteelisthereforeaformofperishing.Theperishabilityissueisapproachedinvariouswaysinthelitureonscheduling,butmostoftheschedulingmodelsinthiscontextsufferfromalackofinformation.Forexample,anapproximationoftenintroducedwhenschedulingperishablegoodswithhighdecayrate,istheintroductionoftightno-waitconstraintsGrabowskietal.,1997,HallandSriskandarajah,1996andPinedo,1995.OthermodelsMcCormicketal.,1989S.T.McCormick,M.L.Pinedo,S.ShenkerandB.Wolf,Sequencinginanassemblylinewithblockingtominimizecycletime,OperationsResearch37(1989)(6),pp.925–935.FullTextviaCrossRefViewRecordinScopusCitedByinScopus(81)McCormicketal.,1989andSanmartíetal.,1998donotexplicitlyconsiderperishabilityconstraints,thusprovidingonlyalowerboundonthemakespanofasequencewhenperishabilityoccurs.MascisandPacciarelli(2002)introducethealternativegraphmodel,whichextendsthedisjunctivegraphformulationofRoyandSussman(1964)inordertorepresentblockingandperishabilityconstraints.Inparticular,thealternativegraphgeneralizestheprecedenceconstraintsgraph(McCormicketal.,1989)andtheS-graphRomeroetal.,2004andSanmartíetal.,1998toincludeperishabilityconstraints.ThemainadvantageofthealternativegraphwithrespecttotheS-graphisthatno-waitandperishabilityconstraintscanberepresenteddirectlywithinthegraph,withouttheneedforadditionalfeasibilitycheckprocedures.Thiscompactrepresentationalsoenablesthecomputationofmoreeffectivelowerbounds,whichcanbeusedtoaccelerateoptimizationprocedures.Pacciarelli(2002)formulatestheSCCproblemwiththealternativegraphandsolvesitwithasimpleandeffectivegreedyheuristic.Inthispaper,weimproveboththeformulationoftheSCCproblemandthesolutionalgorithmpresentedinPacciarelli(2002).Inparticular,wepresentamorecompactformulation,basedonthealternativegraph,andabeamsearchsolutionThebeamsearchThebeamsearchtechniqueisaheuristicsearchstrategy,firstusedinartificialinligenceforthespeechrecognitionproblem(Lowerre,1976),andthenusedFox(1983)forsolvingcomplexschedulingproblems.Itconsistsofatruncatedbranchandbound,inwhichthenodesofthebranchtreearevisitedinbreadthfirstorder,andonlytheβmostpromisingnodesateachlevelareselectedasnodestobranchfrom.Theparameterβiscalledthebeamwidth,andlargervaluesofβusuallyresultinincreasedcomputingtimeandqualityofthesolutions.Thenodeevaluationprocessateachlevelisthekeyissueofanybeamsearch,whereacompromisebetweensolutionqualityandcomputingtimemustbefound.Acommonapproachconsistsofcomputinganupperboundandalowerboundassociatedwiththecandidatenode,andusingthesevaluestoevaluatetheβmostpromisingnodes.ThebeamsearchprocedurehasbeenappliedtotheUISjobshopproblembySabuncuogluandBayiz(1999)usingdispatchingrules,andbyWernerandWinkler(1995)usinganinsertionheuristicandalocalsearchprocedure.ThebeamsearchprocedureproposedinthispaperisbasedonthesameheuristicusedinPacciarelli(2002).InthissectionwedescribethenotationweusethroughoutthepaperandthealternativegraphformulationofMascisandPacciarelli(2002).Intheusualdefinitionofajobshopschedulingproblem,ajobmustbeprocessedonasetofmachines,thesequenceofmachinesforeachjobisprescribed,andtheprocessingofajobonamachinerequiresafixed,non-preemptive,processingtime.Theproblemconsistsofallocatingmachinestocompetingjobsovertime,subjecttotheconstraintthateachmachinecanhandleatmostonejobatatime.Inparticular,theschedulingproblemisaflowshopproblemifthesequenceofmachinesvisitedbyeachjobisthesameforallthejobs.Theprocessingofajobonamachineiscalledanoperation,andthereforeeachjobconsistsofasequenceofoperationsthathavetobeprocessedinaspecifiedorder.Thegoalistominimizethecompletiontimeofthelastoperation.Inthispaperwefocusonthesequencingofoperationsratherthanjobs.Wehavethereforeasetofoperations{o0,o1,…,on}whichhavetobeperformedonmmachines{m1,m2,…,mm}.EachoperationoirequiresaspecifiedamountofprocessingpionaspecifiedmachineM(i),andcannotbeinterruptedfromitsstartingtimetitoitscompletiontimeti+pi.o0andonaredummyoperations,withprocessingtime,thatwecall“start”and“finish”,respectively.Eachmachinecanprocessonlyoneoperationatatime.Thereisasetofprecedencerelationsamongoperations.Aprecedencerelation(i,j)isaconstraintonthestartingtimeofoperationoj,withrespecttoti.Moreprecisely,thestartingtimesofthesuccessorojmustbegreaterorequaltothestartingtimeofthepredecessoroiplusagivendelaydij,whichinourmodelcanbeeitherpositive,nullornegative.Apositivedelaydijmayrepresent,forexample,thefactthatoperationojmaystartprocessingonlyafterthecompletionofitspredecessoroi.Inthiscasedij=pi,i.e.tj≥ti+pi.Adelaysmallerorequaltozerorepresentsasynchronizationbetweenthestartingtimesofthetwooperations.Finally,weassumethato0precedeso1,…,on,andonfollowso0,…,on−1.Precedencerelationsaredividedintotwosets:fixedandalternative.Alternativeprecedencerelationsarepartitionedintopairs.Theyusuallyrepresenttheconstraintsthateachmachinecanprocessonlyoneoperationatatime.Ascheduleisanassignmentofstartingtimest0,t1,…,tntooperationso0,o1,…,onrespectively,suchthatallfixedprecedencerelations,andexactlyoneforeachpairofthealternativeprecedencerelations,aresatisfied.Withoutlossofgeneralityweassumet0=0.Thegoalistominimizethestartingtimeofoperationon.Thisproblemcanbethereforeformulatedasaparticulardisjunctiveprogram(Balas,1979),i.e.alinearprogramwith“exclusiveor”()conditions,calleddisjunctions.ProblemAssociatinganodetoeachoperation,Problem1canbeusefullyrepresentedbythetriple thatwecallalternativegraph.Thealternativegraphisasfollows.ThereisasetofnodesNassociatedtotheoperations,asetofdirectedarcsFandasetofpairsofdirectedarcsAassociatedtoprecedencerelationsbetweenoperations.ArcsinthesetFarefixedanddijisthelengthofarc(i,j)F.ArcsinthesetAarealternative.If((i,j),(h,k))A,wesaythat(i,j)and(h,k)arepairedandthat(i,j)isalternativeof(h,k).Letdijbethelengthofthealternativearc(i,j).Inourmodelthearclengthcouldeitherbepositive,nullornegative.AselectionSisasetofarcsobtainedfromAbychoosingatmostonearcfromeachpair.Theselectioniscompleteifexactlyonearcfromeachpairischosen.Givenapairofalternativearcs((i,j),(h,k))A,wesaythat(i,j)isselectedinSif(i,j)S,whereaswesaythat(i,j)isforbiddeninSif(h,k)S.Finally,thepairisunselectedifneither(i,j)nor(h,k)isselectedinS.GivenaselectionSletindicatethegraph(N,FS).AselectionSisconsistentifthegraphhasnopositivelengthcycles.Aselectionthatisnotconsistentisunfeasible.Infact,acyclewithpositivelengthΔ>0inimpliesthatsomeoperationoiisconstrainedtostartstrictlyafteritsstartingtime,i.e.ti≥ti+Δ,whichisclearlyimpossible.S,acompleteconsistentselectionS′iscalledanextensionofSifSS′.Inotherwords,anextensionS′canbeobtainedfromSbychoosingonearcfromeachunselectedpairwhilepreservingconsistency.NotethatagenericconsistentselectionSmayhavenoextension.Withthisnotation,eachfeasiblescheduleisassociatedwithacompleteconsistentselectiononthecorrespondingalternativegraph.Bydefinition,themakespanofaconsistentselectionSisthelengthofalongestpathfromnode0tonodenin.Themakespanofascheduleisthereforethemakespanoftheassociatedcompleteconsistentselection.Throughoutthepaper,weusethefollowingdefinitions.GivenaselectionS,wedenotethevalueofalongestpathfromItojinbylS(i,j),orsimplyl(i,j).Moreover,weusetheconventionthatifthereisnopathfromitoj,thenl(i,j)=−∞.Finally,foreachnodeiNwesaythatthetyri=l(0,i)istheheadofnodei,andthetyqi=l(i,n)isthetailofnodei.Thealternativegraphgeneralizesseveralothermodelsfromtheschedulingliture,suchasthedisjunctivegraphformulationofRoyandSussman(1964).Infact,inthedisjunctivegraphthepairsofalternativearcs(calleddisjunctivearcs)areallintheform((i,j),(j,i)),whereiandjaretwooperationstobeprocessedonthesamemachine.AlsotheprecedenceconstraintsgraphofMcCormicketal.(1989)andschedule-graphofSanmartíetal.(1998)canbeviewedasgeneralizationsofthedisjunctivegraphmodel,abletorepresenttheblockingconstraints.Thealternativegraphisafurthergeneralizationofboththesemodels,beingabletoincorporatealsotheperishabilityandtheno-waitconstraints,arisinginseveralrealworldproductionenvironmentsand,inparticular,intheproductionofsteel.Fig.3showsthealternativegraphrepresentationoftheperishabilityconstraint.Inthefiguretherearetwopairsofconsecutiveoperationsinajob,namelyoiandoj.Besidestheusualprecedenceconstraintthatojmuststartafterthecompletiontimeofitspredecessoroi,weassumethatojmuststartprocessingwithinγitimeunitsafterthecompletionofoi,i.e.ti+pi≤tj≤ti+pi+γi,withγi≥0.Thisisthecase,forexample,ofliquidsteel,whichcoolsdownanddeterioratesifstoredoveracertaintimelimit.Thetwoinequalitiescanbewrittenintheformtj≥ti+piandti≥tj−pi−γi,respectively,thuscorrespondingtoapairoffixedarcs(i,j)and(j,i)havinglengthpiand−pi−γi,respectively.Ifγi=0wehaveatightno-waitconstraint.3TheformulationoftheSCCInthissectionwerefinethealternativegraphformulationoftheSCCproblempresentedinPacciarelli(2002),andintroduceamorecompactformulation,thatwecallcompressedmodel.ThenaturalIntheSCCproblemduetothepresenceoflimitedbuffersbetweentwoconsecutiveoperationsonlyafiniteintermediatestorage(FIS)isallowed.WemodeltheFISconstraintbyviewingeachpositionofthebufferasamachinewithzeroprocessingtime,asinMcCormicketal.(1989).Hence,theFISconstraintisconvertedintoalargerproblemwithnon-intermediatestorage(NIS),orblockingconstraints.InSection1wedescribedtheLF,whichcanhostuptotwoladlesinparallel,specifyingthat,inpractice,itactsasabufferwithtwopositions.Infact,theprocessingtimeforaladleontheLFisalwayssmallerthantheprocessingtimeontheAODorontheCC.Hence,withoutaffectingthecorrectnessofourmodel,wecanrepresenttheLFasaserialbufferwithtwopositions,bysplittingtheLFprocessingtime(pLF)intwodifferentprocessingtimes,withpLF=pLF1+pLF2.Hence,ladlerequiresfiveoperations(EAF,AOD,LF1,LF2andCC),byaddingotherfourmachineswithzeroprocessingtime,associatedtothefourexistingintermediatestoragepositions,weobtainaflowshopproblemwithnineblockingmachines.Hence,eachladleisrepresentedbynineoperationscorrespondingtoninenodesinthealternativegraphmodel.IntheSCCproblemaperishabilityconstraintarisesinbufferB4,justbeforetheCCmachine,inordertoavoidtheliquidsteeltocooldownanddeteriorateifstoredoveracertaintimelimit.Thealternativepairsbetweenthetwoladlesareusedtorepresenttheschedulingdecision.Giventwoblockingoperationsoiandoj,suchthatM(i)=M(j),letσ(i)andσ(j)bethenextoperationsofoiandoj,respectively.Sinceoiandojcannotbeexecutedatthesametime,weassociatewiththemapairofalternativearcs((σ(i),j),(σ(j),i)).Eacharcrepresentsthefactthatoneoperationmustbeprocessedbeforetheother.Ifoiisprocessedbeforeoj,M(i)canstartprocessingojonlyafterthestartingtimeofoσ(i),whenoileavesM(i).Hence,werepresentthissituationwiththealternativearc(σ(i),j)havinglengthdσ(i)j=0.Ifoiisprocessedafteroj,M(i)canstartprocessingoionlyafterthestartingtimeofoσ(j),whenojleavesM(i).Hence,werepresentthissituationwiththealternativearc(σ(j),i)withlengthdσ(j)i=0.ThealternativegraphmodeltorepresenttwoladlesisshowninFig.4.Herethefixed(alternative)arcsaredepictedwithsolid(dashed)lines.Inparticular,foreachladle,thefirstnodecorrespondstothestartingtimeoftheheatingoperationsintheEAF,thenextthreenodesrepresentthethreepositionsofthesubsequentbuffer(B1,B2andB3),thefifthnodeisassociatedwiththeprocessinginAODunit,thesixthandtheseventhnodesareassociatedwiththeLF,andtheeighthistheinputbufferoftheCC,whereasthelastnodeisthecastingoperation.ThebackwardarcgoingfromtheCCmachinetotheB4bufferrepresentstheperishabilityconstraintontheinputbufferB4.Eightalternativepairsareusedtorepresenttheschedulingdecisionsandtheblockingsettingbetweenthetwoladles.Ifalotofidenticalladlestobeprocessedconsecutivelyisgiven,wegrouptheladlesinablock,asinFig.5,wherethealternativegraphfortwolotsisshown.Here,inthefirstlottherearethreeladlesandinthesecondlottherearetwoladlesThepairofarcsbetweentwoconsecutivecastingoperationsinthesamelotrepresentstheno-waitconstraintontheCC.ThesetuptimeonthecontinuouscasterisrepresentedinFig.5byincreasingthelengthonthearcoutgoingthelastnodeofeachlot.Thezerolengthdiagonalarcsrepresenttheblockingconstraints.Here,allthemachinesbuttheCCareblocking.TheCCmachineisnotblockingsince