轉(zhuǎn)爐煉鋼外文翻譯

PAGEPAGE1*********學(xué)院*****UNIVERSITY畢業(yè)中英文翻譯（英譯漢）設(shè)計(jì)題目：設(shè)計(jì)一座年產(chǎn)550萬噸良坯的轉(zhuǎn)爐車間，產(chǎn)品以板坯為主學(xué)生姓名：學(xué)號(hào)：專業(yè)班級：學(xué)部：材料化工部指導(dǎo)教師：趙**講師畢業(yè)設(shè)計(jì)翻譯譯文原文Productionschedulinginasteelmaking-continuouscastingplantAbstractInthispaperwedescribeanoptimizationprocedureforplanningtheproductionofsteelingotsinasteelmakingcontinuouscastingplant.Thestrictrequirementsoftheproductionprocessdefeatedmostoftheearlierapproachestosteelmakingcontinuouscastingproductionscheduling,mainlyduetothelackofinformationintheoptimizationmodels.Ourformulationoftheproblemisbasedonthealternativegraph,whichisageneralizationofthedisjunctivegraphofRoyandSussman.Thealternativegraphformulationallowustodescribeindetailalltheconstraintsthatarerelevantfortheschedulingproblem.Wethensolvetheproblembyusingabeamsearchprocedure,andcompareourresultswithalowerboundoftheoptimalsolutionsandwiththeactualperformanceobtainedintheplant.Computationalexperienceshowstheeffectivenessofthisapproach.Keywords:Scheduling;Productionplanning;Steelmaking1.Introduction：Steelindustryisveryrichintermsofoperationalproblemsthatcanbemodeledandsolvedbyusingcomputerizedtechniques.Infact,duetothecompetitivepressure,manyinternationalironandsteelcorporationsaremovingtothejust-in-time(JIT)productionconcepts.CommonfeaturesoftheJITmanufacturingsystemsarethesmallsizeofthelotsandtherequestsforhighqualityproducts,timingdelivery,increasedproductivityandreducedcosts.Toalargeextent,inthesteelindustry,schedulingandrelatedissuesarestillcarriedoutbyhumanschedulerswhosecomputersupportmainlyconsistsofasimulatoroftheplant,whichisusedtoevaluateandcomparedifferentscenarios.Ontheotherhand,manycompaniesarenowdevelopingandimplementingcomputerizedsystemsforaddressingsuchoperationalproblems,asreflectedintheprofessionalmeetingsonthesubject.Thesesystemshelptoincreaseproductivityandtimingdelivery,whilereducingenergyconsumptionandproductioncosts.Steelschedulingisknowntobeoneofthemostdifficultindustrialschedulingproblems.Researchersandpractitionershaveapproachedtherelatedschedulingproblemsusingtheformulationsandtoolsofvariousdisciplines,mostlyartificialintelligenceDornetal,1996,DornandShams,1996,TürksenandFazelZarandi,1998andSantosetal,2003andmathematicalprogrammingDuttaandFourer,2001,Naphadeetal,2001,Tangetal,2000,MoonandHrymak,1999,HarjunkoskiandGrossmann,2001andTangetal,2002.InthispaperwedealinparticularwiththeproblemofschedulingtheproductionofstainlesssteelingotsinaproductionlinelocatedincentralItaly.Theplantproducesalargevarietyofingots,tobeusedinawidesetofapplications,characterizedbythesizeandchemicalcomposition,or“grade”.Theingotformationprocess,orsteelmakingcontinuouscastingprocess,hasextremelystrictrequirementsofmaterialcontinuityandflowtimetofulfillinordertoachievesuitablepropertiesonthefinalproduct,thusmakingtheproductionschedulingproblemparticularlychallenging.Showthelayoutoftheproductionline.Theproductionisorganizedinlots,eachlotbeingcomposedofagivennumberofladlestobecastconsecutively.Theladlesbelongingtothesamelotareidenticalandareassociatedtoaspecificproductionorder.Theproductionschedulingproblemconsistsofdeterminingtheschedulingofoperationstobeperformedonmoltensteelatthedifferentproductionstagesfromsteelmakingtocontinuouscasting.Inparticular,theprocessingofstainlesssteelconsistsofasequenceofhightemperatureoperationsstartingwiththeloadingofscrapironinanelectricarcfurnace(EAF).Thetimetomeltthescrapironrangesfrom70to80

minutes,includingafewminutesforsetupandfurnacemaintenanceoperations.Theliquidsteelispouredintoladlesthatacranetransportstoasubsequentmachine,calledargonoxygendecarburizationunit(AOD),wherenickel,chromiumandotherelementsareaddedtothesteelinordertomeetthechemicalqualityrequirements.UsuallythedurationoftheoperationontheAODrangesbetween70and80

minutes.BetweenEAFandAODthereisroomforstoringuptothreeladlesbut,sincethestoredsteelcoolsdown,itmustbereheatedintheAOD.AftertheAODtheladlesaretransportedtoaladlefurnace(LF)whichcanhostatmosttwoladles.EvenifsomeoperationsareexecutedintheLF(nomorethan30

minutes),inpracticeitactsasabuffertomaintaintheladlesatthepropertemperaturebeforethelastoperation,tobeexecutedinthecontinuouscaster(CC).BetweentheLFandtheCCthereisabufferthatcanholdatmostoneladle.Aladlecanstayinthebufferatmost10

minutes,otherwisetheliquidsteelcouldcooldown.IntheCCtheliquidsteeliscastandcooledtoformslabs,thetimerequiredforcastingoneladlerangesfrom60to70

minutes.MoreovertheCCneedstobetooledwithaparticulartool,calledflyingtundish,whichdeterminestheformatofslabs.Iftwosubsequentladlesbelongtothesamelot,theymustbecastwithoutinterruption,otherwisethetundishdeteriorates,andasetupisnecessaryinordertosubstituteit.However,thetundishmustbechangedanywaywhenswitchingfromalottoanother,aswellasafteragivennumberofladles,rangingfromthreetoseven,whichdependsonthesteelquality.Thesizeofalotmayvary,therefore,fromonetosevenladles.Thesetuptimeneedsabout60

minutes,duringwhichtheCCisblocked.Theproblemistoscheduletheproductionofagivennumberoflotswiththeobjectiveofminimizingthecompletiontimeofthelastscheduledlot,i.e.minimizingthemakespan.Werefertothisproblemassteelmakingcontinuouscasting(SCC)problem.Thetimehorizonforaplanningperiodis1week,whichcorrespondstoanaverageof120ladlesand30lotsforatypicalrealsizeproblem.DuttaandFourer(2001)discussseveralproblemsarisinginasteelmakingplant.Theproblemsrangefromproductmixandblendingtoproductionschedulingandcuttingstock.Foralltheseproblems,mathematicalprogrammingapproachesarepresented.Inviewoftheirextensivesurvey,weprovideonlyabriefsummaryofrecentworkshere.Naphadeetal.(2001)formulatetheschedulingprobleminasteelmakingplantusingamixedintegerformulationandsolveitusingatwolevelheuristicapproach.Tangetal.(2000)formulatetheSCCproblemusinganon-linearprogrammingmodel,andthenconvertitintoalinearprogrammingmodel,solvableusingstandardsoftwarepackages.InanotherrecentworkofTangetal.(2002),theSCCproblemisformulatedbyusinganintegerprogrammingmodelanditissolvedcombiningLagrangianrelaxation,dynamicprogrammingandheuristics.HarjunkoskiandGrossmann(2001)arethatinourproblemtheladlesaregroupedinlotswhereasinHarjunkoskiandGrossmanneachladleisindependentoftheothers,andanotherdifferenceisduetothepresenceoftwoparallelEAFsintheirproductionline.OtherrelevantworksfocusontheoptimizationoftheCCmachineSantosetal.,2003andSchwindtandTrautmann,2003orfurnaces,coolersandcraneoperations(Moon&Hrymak,1999).2.2MachineschedulingwithcomplicatingconstraintsAdifferentstreamofresearchrelatedtoSCCproblemdeals,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,remainsonituntilthenextmachinebecomesavailableforprocessing.Atwomachineflowshopschedulingproblem,inwhichthecapacityoftheintermediatebufferislimitedandthejobshavetobeproducedinlotsofidenticalparts,isstudiedbyAgnetis,PacciarelliandRossi(1997).Theproblemisprovedtobe-hard,andanalgorithmisproposedforitssolution.Thealgorithmrunsinpolynomialtimeanditisexactifsomeconditionsonthebatchsizesaremet,otherwiseanapproximationresultholdsingeneral.Pranzo(2004)extendstheseresultstothemoregeneralcasewithsequenceindependentsetupandremovaltimesforthebatches.McCormick,Pinedo,ShenkerandWolf(1989)studyaflowshopschedulingprobleminanassemblylinehavingfinitecapacitybuffersbetweenmachines(FIS).Theymodelthepositionsoftheintermediatebuffersasmachineswithzeroprocessingtime.Theproblemwithlimitedbufferscanbethereforestudiedasablockingproblemwhereallmachineshavenointermediatebuffers.Theyalsoshowthat,onceasequenceforthejobshasbeenfound,thestartingtimeofthejobsonallmachinescanbeeasilycomputedonaprecedenceconstraintsgraph.Theydistinguishtwocategoriesofarcs:processingarcs,havinglengthequaltotheprocessingtimeoftheassociatedoperations,anddummyarcs,ofzerolength,representingtheblockingconstraints.Sanmartí,FriedlerandPuigjaner(1998)studytheproductionschedulingofamultipurposebatchplant.Theyintroducetheschedule-graphrepresentationwhichisabletorepresentbothunlimitedintermediatestorage(UIS)andnon-intermediatestorage(NIS)situations.Onceacompleteschedulegraphisproduced,themakespanonthegraphprovidesthetimingofeachoperation.Theyimplementabranchandboundmethodinwhichthelowerboundonthemakespanisevaluatedonapartialschedulegraph.Computationalexperienceshowsthattheiralgorithmoutperformsastandardmixedintegerprogrammingsolver.Romero,Puigjaner,HolczingerandFriedler(2004)extendtheschedule-graphrepresentation,orS-graph,andcombineitwithafeasibilitycheckbasedonlinearprogrammingtodealwithdifferentintermediatestoragepolicy,includingno-wait(orzerowait,ZW)andfiniteintermediatestorage(FIS).Intheirbranchandboundprocedurethelowerboundisbasedonthelongestpathcomputationundertheassumptionofunlimitedwaitingtime.Ifthisisnotthecase,e.g.whenno-waitoccurs,thelowerboundonthemakespaniscalculatedusingalinearprogrammingmodel.Otherrelevantworksariseinthemanagementofperishableitems.Acommodityissaidtobeperishableifsomeofitscharacteristicsaresubjecttodeteriorationwithrespecttocustomer/producerrequirements.Thecoolingofliquidsteelisthereforeaformofperishing.Theperishabilityissueisapproachedinvariouswaysintheliteratureonscheduling,butmostoftheschedulingmodelsinthiscontextsufferfromalackofinformation.Forexample,anapproximationoftenintroducedwhenschedulingperishablegoodswithhighdecayrate,istheintroductionoftightno-waitconstraintsGrabowskietal.,1997,HallandSriskandarajah,1996andPinedo,1995.OthermodelsMascisandPacciarelli(2002)introducethealternativegraphmodel,whichextendsthedisjunctivegraphformulationofRoyandSussman(1964)inordertorepresentblockingandperishabilityconstraints.Inparticular,thealternativegraphgeneralizestheprecedenceconstraintsgraphRomeroetal.,2004andPacciarelli(2002)formulatestheSCCproblemwiththealternativegraphandsolvesitwithasimpleandeffectivegreedyheuristic.Inthispaper,weimproveboththeformulationoftheSCCproblemandthesolutionalgorithmpresentedin(Lowerre,1976),andthenusedbyFox(1983)forsolvingcomplexschedulingproblems.Itconsistsofatruncatedbranchandbound,inwhichthenodesofthebranchtreearevisitedinbreadthfirstorder,andonlythe\o"ClicktoviewtheMathMLsource"βmostpromisingnodesateachlevelareselectedasnodestobranchfrom.Theparameter\o"ClicktoviewtheMathMLsource"βiscalledthebeamwidth,andlargervaluesof\o"ClicktoviewtheMathMLsource"βusuallyresultinincreasedcomputingtimeandqualityofthesolutions.Thenodeevaluationprocessateachlevelisthekeyissueofanybeamsearch,whereacompromisebetweensolutionqualityandcomputingtimemustbefound.Acommonapproachconsistsofcomputinganupperboundandalowerboundassociatedwiththecandidatenode,andusingthesevaluestoevaluatethe\o"ClicktoviewtheMathMLsource"βmostpromisingnodes.ThebeamsearchprocedurehasbeenappliedtotheUISjobshopproblembySabuncuogluandBayiz(1999)usingdispatchingrules,andbyWernerandWinkler(1995)usinganinsertionheuristicandalocalsearchprocedure.Thebeamsearchprocedureproposedinthispaperisbasedonthesameheuristicusedin{o0,o1,…,on}whichhavetobeperformedonmmachines\o"ClicktoviewtheMathMLsource"{m1,m2,…,mm}.Eachoperation\o"ClicktoviewtheMathMLsource"oirequiresaspecifiedamountofprocessing\o"ClicktoviewtheMathMLsource"pionaspecifiedmachine\o"ClicktoviewtheMathMLsource"M(i),andcannotbeinterruptedfromitsstartingtime\o"ClicktoviewtheMathMLsource"titoitscompletiontime\o"ClicktoviewtheMathMLsource"ti+pi.\o"ClicktoviewtheMathMLsource"o0and\o"ClicktoviewtheMathMLsource"onaredummyoperations,withzeroprocessingtime,thatwecall“start”and“finish”,respectively.Eachmachinecanprocessonlyoneoperationatatime.Thereisasetofprecedencerelationsamongoperations.Aprecedencerelation\o"ClicktoviewtheMathMLsource"(i,j)isaconstraintonthestartingtimeofoperation\o"ClicktoviewtheMathMLsource"oj,withrespectto\o"ClicktoviewtheMathMLsource"ti.Moreprecisely,thestartingtimesofthesuccessor\o"ClicktoviewtheMathMLsource"ojmustbegreaterorequaltothestartingtimeofthepredecessor\o"ClicktoviewtheMathMLsource"oiplusagivendelay\o"ClicktoviewtheMathMLsource"dij,whichinourmodelcanbeeitherpositive,nullornegative.Apositivedelay\o"ClicktoviewtheMathMLsource"dijmayrepresent,forexample,thefactthatoperation\o"ClicktoviewtheMathMLsource"ojmaystartprocessingonlyafterthecompletionofitspredecessor\o"ClicktoviewtheMathMLsource"oi.Inthiscase\o"ClicktoviewtheMathMLsource"dij=pi,i.e.\o"ClicktoviewtheMathMLsource"tj≥ti+pi.Adelaysmallerorequaltozerorepresentsasynchronizationbetweenthestartingtimesofthetwooperations.Finally,weassumethat\o"ClicktoviewtheMathMLsource"o0precedes\o"ClicktoviewtheMathMLsource"o1,…,on,and\o"ClicktoviewtheMathMLsource"onfollows\o"ClicktoviewtheMathMLsource"o0,…,on?1.Precedencerelationsaredividedintotwosets:fixedandalternative.Alternativeprecedencerelationsarepartitionedintopairs.Theyusuallyrepresenttheconstraintsthateachmachinecanprocessonlyoneoperationatatime.Ascheduleisanassignmentofstartingtimes\o"ClicktoviewtheMathMLsource"t0,t1,…,tntooperations\o"ClicktoviewtheMathMLsource"o0,o1,…,onrespectively,suchthatallfixedprecedencerelations,andexactlyoneforeachpairofthealternativeprecedencerelations,aresatisfied.Withoutlossofgeneralityweassume\o"ClicktoviewtheMathMLsource"t0=0.Thegoalistominimizethestartingtimeofoperation\o"ClicktoviewtheMathMLsource"on.Thisproblemcanbethereforeformulatedasaparticulardisjunctiveprogram(Balas,1979),i.e.alinearprogramwith“exclusiveor”()conditions,calleddisjunctions.

Problem1Associatinganodetoeachoperation,dijisthelengthofarc\o"ClicktoviewtheMathMLsource"(i,j)F.ArcsinthesetAarealternative.If\o"ClicktoviewtheMathMLsource"((i,j),(h,k))A,wesaythat\o"ClicktoviewtheMathMLsource"(i,j)and\o"ClicktoviewtheMathMLsource"(h,k)arepairedandthat\o"ClicktoviewtheMathMLsource"(i,j)isthealternativeof\o"ClicktoviewtheMathMLsource"(h,k).Let\o"ClicktoviewtheMathMLsource"dijbethelengthofthealternativearc\o"ClicktoviewtheMathMLsource"(i,j).Inourmodelthearclengthcouldeitherbepositive,nullornegative.AselectionSisasetofarcsobtainedfromAbychoosingatmostonearcfromeachpair.Theselectioniscompleteifexactlyonearcfromeachpairischosen.Givenapairofalternativearcs\o"ClicktoviewtheMathMLsource"((i,j),(h,k))A,wesaythat\o"ClicktoviewtheMathMLsource"(i,j)isselectedinSif\o"ClicktoviewtheMathMLsource"(i,j)S,whereaswesaythat\o"ClicktoviewtheMathMLsource"(i,j)isforbiddeninSif\o"ClicktoviewtheMathMLsource"(h,k)S.Finally,thepairisunselectedifneither\o"ClicktoviewtheMathMLsource"(i,j)nor\o"ClicktoviewtheMathMLsource"(h,k)isselectedinS.GivenaselectionSletindicatethegraph\o"ClicktoviewtheMathMLsource"(N,FS).AselectionSisconsistentifthegraphhasnopositivelengthcycles.Aselectionthatisnotconsistentisunfeasible.Infact,acyclewithpositivelength\o"ClicktoviewtheMathMLsource"Δ>0inimpliesthatsomeoperation\o"ClicktoviewtheMathMLsource"oiisconstrainedtostartstrictlyafteritsstartingtime,i.e.\o"ClicktoviewtheMathMLsource"ti≥ti+Δ,whichisclearlyimpossible.S,acompleteconsistentselection\o"ClicktoviewtheMathMLsource"S′iscalledanextensionofSif\o"ClicktoviewtheMathMLsource"SS′.Inotherwords,anextension\o"ClicktoviewtheMathMLsource"S′canbeobtainedfromSbychoosingonearcfromeachunselectedpairwhilepreservingconsistency.NotethatagenericconsistentselectionSmayhavenoextension.Withthisnotation,eachfeasiblescheduleisassociatedwithacompleteconsistentselectiononthecorrespondingalternativegraph.Bydefinition,themakespanofaconsistentselectionSisthelengthofalongestpathfromnode0tonodenin.Themakespanofascheduleisthereforethemakespanoftheassociatedcompleteconsistentselection.Throughoutthepaper,weusethefollowingdefinitions.GivenaselectionS,wedenotethevalueofalongestpathfromItojinby\o"ClicktoviewtheMathMLsource"lS(i,j),orsimply\o"ClicktoviewtheMathMLsource"l(i,j).Moreover,weusetheconventionthatifthereisnopathfromitoj,then\o"ClicktoviewtheMathMLsource"l(i,j)=?∞.Finally,foreachnode\o"ClicktoviewtheMathMLsource"iNwesaythatthequantity\o"ClicktoviewtheMathMLsource"ri=l(0,i)istheheadofnodei,andthequantity\o"ClicktoviewtheMathMLsource"qi=l(i,n)isthetailofnodei.Thealternativegraphgeneralizesseveralothermodelsfromtheschedulingliterature,suchasthedisjunctivegraphformulationofRoyandSussman(1964).Infact,inthedisjunctivegraphthepairsofalternativearcs(calleddisjunctivearcs)areallintheform\o"ClicktoviewtheMathMLsource"((i,j),(j,i)),whereiandjaretwooperationstobeprocessedonthesamemachine.AlsotheprecedenceconstraintsgraphofSanmartíetal.(1998)canbeviewedasgeneralizationsofthedisjunctivegraphmodel,abletorepresenttheblockingconstraints.Thealternativegraphisafurthergeneralizationofboththesemodels,beingabletoincorporatealsotheperishabilityandtheno-waitconstraints,arisinginseveralrealworldproductionenvironmentsand,inparticular,intheproductionofsteel.oiand\o"ClicktoviewtheMathMLsource"oj.Besidestheusualprecedenceconstraintthat\o"ClicktoviewtheMathMLsource"ojmuststartafterthecompletiontimeofitspredecessor\o"ClicktoviewtheMathMLsource"oi,weassumethat\o"ClicktoviewtheMathMLsource"ojmuststartprocessingwithin\o"ClicktoviewtheMathMLsource"γitimeunitsafterthecompletionof\o"ClicktoviewtheMathMLsource"oi,i.e.\o"ClicktoviewtheMathMLsource"ti+pi≤tj≤ti+pi+γi,with\o"ClicktoviewtheMathMLsource"γi≥0.Thisisthecase,forexample,ofliquidsteel,whichcoolsdownanddeterioratesifstoredoveracertaintimelimit.Thetwoinequalitiescanbewrittenintheform\o"ClicktoviewtheMathMLsource"tj≥ti+piand\o"ClicktoviewtheMathMLsource"ti≥tj?pi?γi,respectively,thuscorrespondingtoapairoffixedarcs\o"ClicktoviewtheMathMLsource"(i,j)and\o"ClicktoviewtheMathMLsource"(j,i)havinglength\o"ClicktoviewtheMathMLsource"piand\o"ClicktoviewtheMathMLsource"?pi?γi,respectively.If\o"ClicktoviewtheMathMLsource"γi=0wehaveatightno-waitconstraint.3TheformulationoftheSCCproblemInthissectionwerefinethealternativegraphformulationoftheSCCproblempresentedinPacciarelli(2002),andintroduceamorecompactformulation,thatwecallcompressedmodel.3.1ThenaturalformulationIntheSCCproblemduetothepresenceoflimitedbuffersbetweentwoconsecutiveoperationsonlyafiniteintermediatestorage(FIS)isallowed.WemodeltheFISconstraintbyviewingeachpositionofthebufferasamachinewithzeroprocessingtime,asinMcCormicketal.(1989).Hence,theFISconstraintisconvertedintoalargerproblemwithnon-intermediatestorage(NIS),orblockingconstraints.InSectionpLF)intwodifferentprocessingtimes,with\o"ClicktoviewtheMathMLsource"pLF=pLF1+pLF2.Hence,eachladlerequiresfiveoperations(EAF,AOD,LF1,LF2andCC),byaddingotherfourmachineswithzeroprocessingtime,associatedtothefourexistingintermediatestoragepositions,weobtainaflowshopproblemwithnineblockingmachines.Hence,eachladleisrepresentedbynineoperationscorrespondingtoninenodesinthealternativegraphmodel.IntheSCCproblemaperishabilityconstraintarisesinbufferB4,justbeforetheCCmachine,inordertoavoidtheliquidsteeltocooldownanddeteriorateifstoredoveracertaintimelimit.Thealternativepairsbetweenthetwoladlesareusedtorepresenttheschedulingdecision.Giventwoblockingoperations\o"ClicktoviewtheMathMLsource"oiand\o"ClicktoviewtheMathMLsource"oj,suchthat\o"ClicktoviewtheMathMLsource"M(i)=M(j),let\o"ClicktoviewtheMathMLsource"σ(i)and\o"ClicktoviewtheMathMLsource"σ(j)bethenextoperationsof\o"ClicktoviewtheMathMLsource"oiand\o"ClicktoviewtheMathMLsource"oj,respectively.Since\o"ClicktoviewtheMathMLsource"oiand\o"ClicktoviewtheMathMLsource"ojcannotbeexecutedatthesametime,weassociatewiththemapairofalternativearcs\o"ClicktoviewtheMathMLsource"((σ(i),j),(σ(j),i)).Eacharcrepresentsthefactthatoneoperationmustbeprocessedbeforetheother.If\o"ClicktoviewtheMathMLsource"oiisprocessedbefore\o"ClicktoviewtheMathMLsource"oj,M(i)canstartprocessing\o"ClicktoviewtheMathMLsource"ojonlyafterthestartingtimeof\o"ClicktoviewtheMathMLsource"oσ(i),when\o"ClicktoviewtheMathMLsource"oileaves\o"ClicktoviewtheMathMLsource"M(i).Hence,werepresentthissituationwiththealternativearc\o"ClicktoviewtheMathMLsource"(σ(i),j)havinglength\o"ClicktoviewtheMathMLsource"dσ(i)j=0.If\o"ClicktoviewtheMathMLsource"oiisprocessedafter\o"ClicktoviewtheMathMLsource"oj,M(i)canstartprocessing\o"ClicktoviewtheMathMLsource"oionlyafterthestartingtimeof\o"ClicktoviewtheMathMLsource"oσ(j),when\o"ClicktoviewtheMathMLsource"ojleaves\o"ClicktoviewtheMathMLsource"M(i).Hence,werepresentthissituationwiththealternativearc\o"ClicktoviewtheMathMLsource"(σ(j),i)withlength\o"ClicktoviewtheMathMLsource"dσ(j)i=0.Thealternativegraphmodeltorepresenttwoladlesisshownin9bnodesand\o"ClicktoviewtheMathMLsource"9b+10(b?1)+2arcs,thusthenumberofnodesneededtorepresentalotisnotconstantbutitdependsonitsnumberofladles.NoticethatinpLF1+pLF2≤pCC.If\o"ClicktoviewtheMathMLsource"pAOD>pCCor\o"ClicktoviewtheMathMLsource"pEAF>pCCafeasiblesolutioncanexistsonlyifthenumberofladlesinalotissmallenough.Inparticular,if\o"ClicktoviewtheMathMLsource"pAOD>pCCthemaximumnumberofladles(\o"ClicktoviewtheMathMLsource"bmax)mustbesuchthat\o"ClicktoviewtheMathMLsource"max{0,pAOD?pB4}+(bmax?4)pAOD+pLF1+pLF2?(bmax?1)pCC≤0(seepEAF>pCC,then\o"ClicktoviewtheMathMLsource"max{0,pEAF?pB4}+(bmax?8)pEAF+pAOD+pLF1+pLF2?(bmax?1)pCC≤0(seepEAF=7,pAOD=6,pLF1=pLF2=pB4=1,pCC=2,respectively.Accordingtoboundbmax≤3,whereasboundbmax≤8.Hence,themaximumnumberofladlesinafeasiblesolutionisthree.Infact,theGanttchartforfourladlesiniNbeanodesuchthatnoalternativearcsareincidenttonodei.Letbethesetoffixedarcsincidenttonodei,andletbeasetofarcssuchthat.Letthelengthofthesearcs\o"ClicktoviewtheMathMLsource"dhjbeequaltothesumofthetwoarcspassingthroughtheremovednodei:\o"ClicktoviewtheMathMLsource"dhj=dhi+dij.Thenthealternativegraphwith\o"ClicktoviewtheMathMLsource"N′=N{i},F′=F(F?F+),isequivalenttothegraph.N′arethesameasin,andthestartingtimeofthecontractednodescanbeobtainedfromthestartingtimeassociatedtotheremainingnodes.

Proposition2arcdeletion

Considerafixedarc\o"ClicktoviewtheMathMLsource"(i,j)Foflength\o"ClicktoviewtheMathMLsource"dij.Ifthereexistsapath\o"ClicktoviewtheMathMLsource"l(i,j)F,differentfrom\o"ClicktoviewtheMathMLsource"(i,j),suchthat\o"ClicktoviewtheMathMLsource"l(i,j)≥dij,thenarc\o"ClicktoviewtheMathMLsource"(i,j)canberemovedfromthegraph.Theresultinggraphisequivalenttotheoriginalgraph.l(h,j)≥dhjthenthefixedar