A New General Continuous-Time State Task Network F

ANewGeneralContinuous-TimeStateTaskNetworkFormulationforShort-TermSchedulingofMultipurposeBatchPlantsChristosT.Maravelias,IgnacioE.Grossmann∗DepartmentofChemicalEngineering,CarnegieMellonUniversityPittsburgh,PA15213,USANovember2002/Rev.March2003AbstractAnewcontinuoustimeMILPmodelfortheshort-termschedulingofmultipurposebatchplantsispresented.TheproposedmodelreliesontheStateTaskNetwork(STN)andaddressesthegeneralproblemofbatchscheduling,accountingforresource(utility)constraints,variablebatchsizesandprocessingtimes,variousstoragepolicies(UIS/FIS/NIS/ZW),batchmixing/splitting,andsequence-dependentchangeovertimes.Thekeyfeaturesoftheproposedmodelarethefollowing:(a)acontinuoustimerepresentationisused,commonforallunits,(b)assignmentconstraintsareexpressedusingbinaryvariablesthataredefinedonlyfortasks,notforunits,(c)starttimesoftasksareeliminated;thus,timematchingconstraintsareusedonlyforthefinishtimesoftasks,and(d)anewclassofvalidinequalitiesthatimprovestheLPrelaxationisaddedtotheMILPformulation.ComparedtoothergeneralcontinuousSTNformulations,theproposedmodelissignificantlyfaster.Comparedtoevent-drivenformulations,itismoregeneralasitaccountsforresourcesotherthanequipmentandoftengivesbettersolutionsbeingequallyfast.Theapplicationofthemodelisillustratedthroughfourexampleproblems.1.IntroductionTheproblemofshort-termschedulingofmultipurposebatchplantshasreceivedconsiderableattentionduringthelastdecade.Kondilietal.(1993)introducedtheStateTaskNetwork(STN)andproposedadiscrete-timeMILPmodel,wherethetimehorizonisdividedintotimeperiodsofequalduration.Sincetheresultingmodelshavemanybinaryvariables,Shahetal.(1993)developedareformulationandspecifictechniquestoreducethecomputationaltimesfordiscrete-timeSTNmodels.Pantelides(1995)proposedthealternativerepresentationandformulationoftheResourceTaskNetwork(RTN);SchillingandPantelides(1996)developedacontinuous-timeMILPmodel,basedontheRTNrepresentation,andanovelbranch-and-boundalgorithmthatbranchesonbothcontinuousanddiscretevariables.ZhangandSargent(1996)andMockusandReklaitis(1999)proposedMINLPcontinuous-timerepresentationsfor∗Towhomallcorrespondenceshouldbeaddressed.Tel:[phone],Fax:[phone],E-mail:[e-mail],2theschedulingofbatchandcontinuousprocesses.IerapetritouandFloudas(1998a)proposedanewMILPformulationbasedoneventpointsfortheschedulingofbatchandcontinuousmultipurposeplants.Despitetheimprovedformulations,thespecializedalgorithmsandtherecentimprovementsincomputerhardwareandoptimizationsoftware,theshort-termschedulingofSTNmultipurposebatchplantsincontinuoustimeremainsadifficultproblemtosolve.Inanefforttoreduceproblemsizeandcomputationaltime,severalauthorshaveproposedvariousapproachesduringthelasttwoyears(Rodriguezetal.2001;Mendezetal.,2000;Leeetal.2001;GiannelosandGeorgiadis,2002).Inmostoftheseapproaches,however,theauthorsmakespecificassumptionsthatontheonehandleadtomorecompactformulations,but,ontheotherhandaddressonlyspecificcasesofthegeneralshort-termschedulingproblem.Someofthemostcommonassumptionsthatresultinsignificantreductionsinproblemsizeare(a)nobatchsplittingand(b)noresourceconstraintsotherthanthoseonequipmentunits.Aswillbeillustratedlater,evenweakerassumptionsgiverisetoformulationsthatcannotaccountforalltheinstancesthatmayappearinamultipurposebatchplant.Inthiswork,weproposeanewgeneralStateTaskNetworkMILPmodelfortheshort-termschedulingofmultipurposebatchplantsincontinuoustimethataccountsforresourceconstraintsotherthanequipment(utilities),variablebatchsizesandprocessingtimes,variousstoragepolicies(UIS/FIS/NIS/ZW)includingsharedstorage,sequencedependentchangeovertimesandallowsforbatchmixing/splitting.Thepaperisstructuredasfollows.Insection2,webrieflydiscussthedifferenttimerepresentationapproachesproposedintheliteratureandweoutlinetheproposedapproach.Theproblemstatementispresentedinsection3.Themathematicalformulationanditsderivationaredescribedinsection4andsomeremarksarepresentedinsection5.Fourexamplesarepresentedinthelastsection.2.OutlineofProposedApproachSeveraltimerepresentationschemeshavebeenproposedfortheschedulingofmultipurposebatchplants.Kondilietal(1993)introducedtheSTNformulationusingadiscrete-timerepresentation(Figure1a),wherethetimehorizonisdividedintoHintervalsofequalduration,commonforallunits,andwherethetasksmustbeginandfinishexactlyatatimepoint.Thismeansthatthediscrete-timerepresentationcanbeusedonlywhentheprocessingtimesareconstantand,furthermorethatthedurationoftheintervalsmustbeequaltothegreatestcommonfactoroftheprocessingtimes.Theassumptionofconstantprocessingtimesisnotalwaysrealistic,whilethelengthoftheintervalsmaybesosmallthatiteitherleadstoaprohibitivenumberofintervalsrenderingtheresultingmodelunsolvable,orelseitrequiresapproximationswhichmaycompromisethefeasibilityandoptimalityofthesolution.Tocircumventtheaboveciteddifficulties,twodifferentcontinuoustimerepresentationswereproposedinwhichthetimehorizonisdividedintotimeintervalsofunequalandunknownduration,commonforallunits.Inthecontinuous-timerepresentationI(Figure1b),eachtaskmuststartandfinis