单件生产系统的动态调度方法.pdf 13页

'中国科技论文在线http://www.paper.edu.cn#Dynamicschedulingofaone-of-a-kindproductionsystem*WANGZheng,HUANGWenjie5(SchoolofAutomation,SoutheastUniversity,Nanjing,Jiangsu210096)Abstract:Inthisresearch,weinvestigatethedynamicschedulingproblemofaone-of-a-kindproduction(OKP)systemwithRFIDdevices.Here,dynamicschedulingmeansthatwescheduleeveryoperationofeveryproductaccordingtoitsreal-timestatetominimizetheaveragesojourntimeofproducts.Tosolvethisproblem,wemodelthedynamicsofanOKPsystembyreconfigurabletimed10Petrinet,andthendevelopthedifferenceequationstocaptureitsdynamics,inwhichtheremainedworkloadofproductsarestatevariablesandtheproductionratesarecontrolvariables.Adynamicproductionschedulingpolicyisconstructedbyconstructingdesiredtrajectoriesoftheremainedworkloadsforalltheproductsanddesigningageneticalgorithm-basedmethodtotrackthedesiredtrajectories.NumericalexperimentsshowthattheaveragesojourntimeoftheproductsintheOKP15systemundertheproposeddynamicschedulingalgorithmismuchshorterthantheaveragesojourntimeundertraditionalschedulingrules.Keywords:One-of-a-kindproduction(OKP);dynamicproductionscheduling;optimalcontrol;Petrinet;radiofrequencyidentification(RFID)200Introduction[1][2]ONE-OF-A-KINDproduction(OKP)isatypeofleanproductionpattern,whichcanfulfillmass-customizationandthereforerequiresaccurateobservationandschedulingoftheproductionprocess,sothatitcanbecompletedontime,withgoodquality,atlowcostandwithhighsatisfactorylevelfromcustomers.Torealizeaccurateproductionscheduling,i.e.,allocate25everyoperationofeveryproductonthemachineitexactlyrequiresatthemostpropertime,wehavetorealizeaccurateobservationoftherealtimestateoftheOKPsystematfirst.Here,accurateobservationofstatemeansthatweareabletoknow(1)whatoperationofagivenproductisbeingconductedonaspecificmachine,(2)whatoperationofagivenproductiswaitingforprocessinginaspecificbuffer,and(3)howmuchpercentageoftheworkloadofeveryoperation30ofeveryproductiscompletedandhowmuchisremainedtoprocess.Radiofrequencyidentification(RFID)isatypeoftechnologythatcanfulfillaccurateobservationofrealtimestateofanOKPsystem.WiththehelpofRFIDtechnology,atanytime,wecanknowexactlythepositionofanindividualoperation,andtheremainedworkloadofanindividualproduct.Thisexactrealtimestatedataisthefoundationofmakingaccuratedynamicschedulingdecision.35Inthispaper,wefocusondynamicschedulinginsteadofstaticschedulingbecauseinaOKPsystem,theorderingoftenarrivesrandomlyandthereforeitisdifficulttoknowinadvancethatwhatproductsaregoingtobeproducedinthecomingperiodoftime.Itisthisstochasticarrivalofproductiontaskthatmakeoff-linestaticschedulingdifficult,evenifnotimpossible.Inthissense,dynamicscheduling,i.e.,makingproductionschedulingdecisionbasedonreal-timestate,isthe40fundamentalfeatureofOKP,andthereforeitisthemainissuetobeinvestigatedinthispaper.Unlikeotherrule-basedschedulingmethods,inthispaper,wedevelopadynamicproductionschedulingpolicybyconstructingdesiredtrajectoriesofthedecreasingofremainedworkloadsforalltheproductsanddesignageneticalgorithm-basedmethodtotracethedesiredtrajectories.Comparisonstudywillbecarriedouttoverifythattheproposedschedulingpolicyoutperforms45otherschedulingrules.Foundations:TheFoundationofDoctoralProgramsinUniversities,MinistryofEducation,P.R.China;Grant(No.20130092110024)Briefauthorintroduction:WANGZheng(1973-),male,professor.Hisresearchareasincludemanufacturingsystemsanalysis,controlanddesign,andinventoryandsupplychainmanagement.E-mail:wangz@seu.edu.cn-1- 中国科技论文在线http://www.paper.edu.cnTheremainderofthispaperisorganizedasfollows:InSectionII,wewillreviewtheliteraturerelevanttothisresearch.InSectionIII,thePetrinetmodelwillbeconstructedtodescribethedynamicsoftheOKPsystem.Basedonthemodel,thedynamicproductionschedulingproblemofanOKPsystemisdefinedinSectionIV.InSectionV,thedynamic50productionschedulingpolicywillbedeveloped.NumericalexperimentsareconductedinSectionVItoexaminetheproposeddynamicschedulingpolicybycomparingwithrule-baseddynamicschedulingmethods.SectionVIIsummarizesthepaperandpresentssomeissuesforfutureresearch.1LiteratureReview55Inthissection,wewillreviewtheliteraturerelatetothisresearchfromthreeperspectives:one-of-a-kindproduction,dynamicproductionschedulingandtheapplicationofRFIDtechnologyinmanufacturingsystems.Basedontheliteraturereview,wewillstatethesignificanceofthisresearch.1.1One-of-a-KindProduction60Sinceone-of-a-kindproduction(OKP)ischaracterizedbyhighlevelofcustomizationandrapidresponse,accurateandtimelyinformationisneededinsuchaproductionprocess.Tothis[3]end,Deanetal.developedaninformationsystemfortheone-of-a-kindproductionmanagementinafactoryproducingcustomizeddoorsandwindows,inwhichtheknowledgeofthestructureandoperationofeveryindividualproductaremanagedandreusedwell.Tosatisfyindividual[4][5]65customerrequirementsontheperformanceandqualityofacustomizedproduct,Hongetal.developeddifferentmethodsofidentifyingoptimalproductconfigurationandparameterstofulfillOKP.Duetotherequirementsofhighcustomization,OKPisofhighflexibilityinproduction[6][7]management.Luoetal.developedbranch-and-boundalgorithmstosolvetheoptimalresourceallocationandoperationallocationproblemsforanOKPsystemtofulfillthisflexibility.The[8]70foundationofone-of-a-kindproductionisone-of-a-kindproductdevelopment.Xieetal.gaveareviewontheresearchofInternet-basedone-of-a-kindproductdevelopment,andalsodeveloped[9]anInternet-basedreconfigurableplatformforrapidone-of-a-kindproductdevelopment.Xieand[10]Tuproposedareferencesystemstructureofrapidone-of-a-kindproductdevelopmentinglobalmanufacturingenvironment.751.2DynamicProductionSchedulingThegreatestdifferencebetweendynamicschedulingandstaticschedulingisthattheformerhavetodealwithrandomarrivalofjobsandthereforecannotscheduleallthejobsinadvancelikewhatthelatterdoes.ZandiehandAdibi[11]proposedavariableneighborhoodsearchtechniqueto[12]solvethedynamicjobshopschedulingproblem.AlpayandYüzügüllüdevelopedanew80dispatchingrulecalledcriticalratioandoperationslack(CR+OSLK)ruletoimprovethemeanabsolutelatenessandthemeansquarelatenessofdynamicjobshopscheduling.Vinodand[13]Sridharantookthesetuptimeintoconsiderationandconstructedseveralsetup-orientedrules[14]fordynamicjobshopscheduling.VinodandSridharanintegratedthedynamicjobshopschedulingruleswiththedynamicdue-dateassignmentrules,andcarriedoutsimulation-based[15]85analysisoftheirimpactontheperformanceofproductioncontrol.Hastudiedtheoptimaldynamicschedulingproblemforamake-to-stockproductionsystembasedontheoptimalcontroltheoryandprovedtheoptimalityofthebasestockpolicycoupledwithaswitchcurve.Somemeta-heuristictechniquessuchasantcolonyoptimizationarealsoappliedtosolvedynamic[16][17][18]productionschedulingproblems.DynamicschedulingisalsoagreatconcernofOKP.Tu-2- 中国科技论文在线http://www.paper.edu.cn90proposedahierarchicalarchitectureofthereal-timeproductionschedulingandcontrolforOKPas[19]wellasthereal-timeproductioncontrolalgorithm,andextendedittoavirtualOKPsystem.[20]ChoiandYoudidasimulation-basedcomparisonstudyonseveraldispatchingrulesfordynamicschedulingofone-of-a-kindproduction,andsummarizedtheirperformancesindifferent[21][22]situations.Lietal.proposedaheuristicrulebasedonaverageprocessingtimeanda95state-spaceheuristicruleintegratedwithclosed-loopfeedbackcontroltodevelopthedynamicandadaptiveschedulingpolicyforone-of-a-kindproduction.1.3RFIDinManufacturingSystemsTocontrolaone-of-a-kindproductionprocessefficiently,thereal-timestateoftheOKPsystemshouldbeobservedintimeandaccurately.Radiofrequencyidentification(RFID)isa100propertechnologythatcanbeappliedtofulfilltheaccurateobservationandcontrolofOKPsystems.Actually,RFIDtechnologyhasbeenappliedtomanufacturingsystemssuccessfully.[23]Ngaietal.analyzedthemainfactorsthatinfluencetheimplementofRFIDtechnologyinmanufacturingprocessmanagementbasedonacasestudyinagarmentfactoryinChina.Brusey[24]andMcFarlanepresentedthetechnologyofapplyingRFIDsystemtoidentifyandtracking105individualobjectsincustomizedproduction(asweknow,OKPisatypeofcustomized[25]production).Kelepourisetal.proposedaBayesianapproachtoestimatingthelocationofasingleobjectinasupplychainbasedonthereal-timedatacollectedbytheRFIDandelectronic[26]productcode(EPC)system.Brintrupetal.providedatoolsettoanalyzewhetherandhow[27]RFIDtechnologycanbeappliedtofulfillleanproductioninenterprises.Huangetal.proposed110theconceptofwirelessmanufacturinganditstechnologicalsystemsarchitecture,inwhichRFID[28]playsanimportantrole.Huangetal.reportedthefundamentaltechnologyofareal-timewirelessmanufacturingsystemwhereRFIDdevicesaredeployedtomachines,keycomponentsandcontainersofwork-in-process(WIP)materials.Basedonthat,theydevelopedthe[29]manufacturingexecutionsystemforwirelessmanufacturingtomanageWIPinventories.To115acquirethereal-timestateofamanufacturingsystemfromdifferenttypesofRFIDdevicesor[30]wirelesssensors,asmartgatewayisdevelopedtoacquiredatafromheterogeneousdatasources.[31]RFIDtechnologyhasbeenappliedtoone-of-a-kindproduction.Forexample,Wangetal.developedanRFID-enabledmanufacturingexecutionsystemforone-of-a-kindproductioninmouldindustry.1201.4SummaryFromtheabovesurveyoftheexistingresearchonOKP,dynamicproductionschedulingandtheapplicationofRFIDinmanufacturingsystems,wecanfindthatdynamicschedulingisagreatconcerninOKPsystemsandRFIDisanimportanttechnologicalfoundationofimplementingOKP.Therefore,studyingthedynamicschedulingproblemforaone-of-a-kindproductionsystem125equippedwithRFIDdevicesisofgreatsignificance.Differentfromexistingresearchondynamicscheduling,whichisoftenrule-basedtechnique,inthispaper,wewilldevelopadynamicschedulingpolicyforone-of-a-kindproductionbyconstructingdesiredtrajectoriesofthedecreasingoftheworkloadsforalltheproductsanddesignageneticalgorithm-basedmethodtotracethedesiredtrajectories,inwhichthereal-timestatedataoftheOKPsystem(i.e.,remained130workload)isacquiredbyRFIDdevices.2Petri-NetModelofAnOKPSystemToimplementthedynamicschedulingofanOKPsystem,itisnecessarytomodelitsdynamicsatfirst.Duetothediscrete-eventnatureofanOKPsystem,wetrytomodelitbyPetri-3- 中国科技论文在线http://www.paper.edu.cnnet.Jiangetal.[32]proposedatypeofcoloredPetrinetwithchangeablestructure(CPN-CS)as135wellastwoalgorithmsforstructurechange(i.e.,thechange-by-modificationalgorithmandthechange-by-compositionalgorithm),andappliedittothemodelingofOKPsystems.However,theirmodelfocusesonthelogicpropertiesofone-of-a-kindproductionprocesses,butdoesnottakethetimefactorsandschedulingdecisionfunctionsintoconsideration.Inthissection,wewillproposeaPetrinetthatcanchangeitsstructureswhenanewproductiontasksenteringtheOKP140systemoracompletedtaskleavesthesystem,cancapturethetimeneededforoperation,andthereforecansupportthedecision-makingofdynamicscheduling.ThisPetrinetisnamedReconfigurableTimedPetriNet(RTPN).2.1DefinitionofReconfigurableTimedPetriNet(RTPN)Inthissubsection,thedefinitionofthereconfigurabletimedPetrinetispresented,basedon145whichwecanmodelthedynamicsofOKPsystems.Definition1.ReconfigurabletimedPetrinet(RTPN).AreconfigurabletimedPetrinetcanbedefinedasan8-tuple:RTPN=(P,T,F,M,X,RT,RS,RW),where150Pisthesetofplaces;Tisthesetoftransitions;Fisthesetofdirectedarcsbetweenplacesandtransitions;MisthesetoftokensthatmarkthecurrentstateofthePetrinet;X=XBXFisthesetoftimeparameterscorrespondingtotransitions,whichincludethe155subsetofthebeginningtimeofthetransitions(XB)andthesubsetoftime-to-finishofthetransitions(XF);RTisthesetoftherulesofenablingtransitions;RSisthesetoftherulesofschedulingthefiringoftransitions;RWisthesetoftherulesofreconfiguringthePetrinet.160IntheRTPNmodeloftheOKPsystem,thedefinitionsoftheplaces,transitions,timeparameters,andtherulesinthesetsRT,RSandRWwillbeexplainedindetails.2.2RTPNmodelofanOKPSystemFortheconvenienceofexpression,wemodelanOKPsystemwith5machinesprocessingtheassemblyofdifferenttypesofproductswithnomorethan5operations.Eachoperationiscarried165outonamachine,andnomorethanoneoperationofthesameproductiscarriedoutonthesamemachine,i.e.,reentrantisnotallowedinthissystem.Everyproducthasitsownprocessingroutes,whichisdifferentfromothers.Theinter-arrivaltimesoftheproductstothesystemisexponentiallydistributed.Oncealltheoperationsoftheproductarecompleted,itleavesthesystem.TheRTPNmodelofsuchanOKPsystemisdefinedasfollows(Fig.1):1702.2.1Thesetofplacesandthedefinitionoftokensp01-p05:theplacesoftheavailabilityofmachines,wherethetokeninaplacerepresentsthatthecorrespondingmachineisavailable.p11-p17:theplacesofthecompletionoftheoperationsofproduct-type1,wherethetokenina175placerepresentsthatanoperationoftheproductoftype1iscompletedandreadyforthenextoperation.-4- 中国科技论文在线http://www.paper.edu.cnp21-p27:theplacesofthecompletionoftheoperationsofproduct-type2,wherethetokeninaplacerepresentsthatanoperationoftheproductoftype2iscompletedandreadyforthenextoperation.1802.2.2Thesetoftransitionsandthedefinitionoftimeparameterst10:arrivaloftheproductoftype1;thetimeparametercorrespondingtothistransitionisthearrivalrate(l1)ofnewproducts,wheretheinter-arrivaltimeisassumedtobeexponentiallydistributed.t11-t14:theoperationsoftheproductoftype1;thetimeparameterscorrespondingtothese185transitionsarebeginningtimesandremainedworkloadsofoperations.t20:arrivaloftheproductoftype2;thetimeparametercorrespondingtothistransitionisthearrivalrate(l2)ofnewproducts,wheretheinter-arrivaltimeisassumedtobeexponentiallydistributed.t21-t25:theoperationsoftheproductoftype2;thetimeparameterscorrespondingtothese190transitionsarebeginningtimesandremainedworkloadsofoperations.2.2.3ThesetoftransitionenablingrulesForatransition,ifeveryoneofitsinputplacehasatleastonetokenandallofitsoutputplacesareempty,thenitcanbeenabled.2.2.4Thesetoftransitionschedulingrules195Foranenabledtransition,ifthetokensinatleastoneofitsinputplacesenableanothertransitionatthesametime,thetransitionschedulingrulesdeterminethesequenceoffiringtheseenabledtransitions.2.2.5ThesetofnetreconfigurationrulesOnceanoperationofaproductisfinished,itscorrespondingtransition,theinputplacesof200thistransition,andthearcsconnectedtothemaredeletefromthePetrinet.Onceanewproductarrivesatthesystem,theplaces,transitions,arcsandtokensthatcaptureitsproductionprocessareaddedtothePetrinet.Forexample,inFig.1,whenthefirsttwooperationsoftheproductoftype1arecompleted,thentheplacesp11andp12,thetransitionst10,t11andt12,andthedirectedarcs(t10,p11),(t10,p12),(t10,p15),(p11,t11),(p12,t12),(t11,p13),(t12,p14),(p01,t11),(t11,p01),(p02,t12),and(t12,205p02)aredeletedfromthePetrinet(theyaredepictedbydashlinesinFigure1).Whentheproductoftype2arrivesattheOKPsystem,theplacesp12,p22,p23,p24,p25,p26,p27,thetransitionst20,t21,t22,t23,t24,t25,andthedirectedarcs(t20,p21),(t20,p22),(p21,t21),(p22,t22),(t21,p23),(t22,p24),(p23,t23),(p24,t24),(t23,p25),(t24,p26),(p25,t25),(p26,t25),(t25,p27),(p01,t22),(t22,p01),(p02,t23),(t23,p02),(p03,t21),(t21,p03),(p04,t24),(t24,p04),(p05,t25)and(t25,p05)areaddedtothePetrinet.210TheRTPNmodelofanOKPsystemcanbeappliedtorealizethediscreteeventsimulationoftheproductionprocess,sothattheperformancesofproductionschedulingpoliciescanbeevaluated.Basedonthismodel,wecandefinethedynamicschedulingproblemforanOKPsystemandconstructthedynamicschedulingpolicy.-5- 中国科技论文在线http://www.paper.edu.cn215Fig.1.ThereconfigurabletimedPetrinetmodelofaone-of-a-kindproductionsystem3DefinitionoftheDynamicSchedulingProblemEveryproductproducedinanOKPsystemisconsideredtobeunique,i.e.,itsprocessrouteisdifferentfromothers’.Weneedtomakedecisionsonthesequenceofalltheoperationsofalltheproductsoneverymachineoncethestateoftheone-of-a-kindproductionprocesschangesdueto220theoccurrenceofevents,e.g.,arrivalordepartureofproducts,beginningorfinishingofoperations,andbreak-downorrepairofmachines.Theaimofdecision-makingistominimizetheaveragesojourntime(i.e.,thelengthofthetimeintervalbetweenarrivalanddeparture)ofaproductinthesystem.Sincetheschedulingdecisionismadebasedonthereal-timestateoftheone-of-a-kindproductionprocessatthetimeoftheoccurrenceofanevent,wecallitdynamicscheduling,which225distinguishesitfromstaticschedulingthatdeterminestheprocessingsequenceofalltheoperationonallthemachinesatatimeinanintegrativeway.BeforegivingthemathematicalformulationofthedynamicschedulingproblemforanOKPsystem,welistthenotationstobeusedasfollows:t:theindexoftime;I:thenumberofproductsproducedintheOKPsystem;230i:theindexofproduct,i=1,…,I;Ni:thenumberofoperationsofproductj;j:theindexofoperation,j=1,…,Ni;Pi:thesetoftheprecedencerelationshipbetweentheoperationsofproducti;apairofoperations(j,k)Pimeansthatoperationjofproductiistheimmediateprecedentoperationof235operationkofproducti;ai:thearrivaltimeofproducti;pij:thetotalworkloadofoperationjofproducti;xij(t):theremainedworkloadofoperationjofproductiattimet,fortai;xij(ai)=pij;xi(t):theremainedworkloadofproductiattimet;240uij(t):theprocessingrateofoperationjofproductiattimet;uij(t){0,1};M:thenumberofmachinesintheOKPsystem;m:theindexofmachines,m=1,…,M;ij:themachineonwhichoperationjofproductiisconducted.ThenthemathematicalformulationofthedynamicschedulingproblemofanOKPsystemis245givenby-6- 中国科技论文在线http://www.paper.edu.cnI1Minmintxi(t)0ai(1)Ii1s.t.x(t1)x(t)u(t),fori=1,…I;j=1,…,Ni;(2)ijijijNx(t)ix(t)ij1ij,fori=1,…I;(3)mintxij(t)0maxtxik(t)pik0,for(j,k)Pi,i=1,…,I;(4)250uij(t)1,form=1,…,M;(5)mijx(a)p,fori=1,…I;j=1,…,Ni;(6)ijiiju(t){0,1},fori=1,…I;j=1,…,Ni;(7)ijEq.(1)istheaveragesojourntimeofalltheproducts,wheremin{t|xi(t)=0}isthetimewhenproductiiscompleted.Eq.(2)isthedynamicequationoftheOKPprocess,whichmeansthatthe255remainedworkloadoftheoperationjofproductiattimet+1isitsremainedworkloadattimetminustheprocessingrateofthisoperationattimet.Eq.(3)meansthattheremainedworkloadofproductiattimetisequaltothesumoftheremainedworkloadsofalltheoperationsofthisproduct.Eq.(4)istheprecedenceconstraintontheoperationsofaproduct.Eq.(5)istheproductioncapacityconstraint,i.e.,atanytimet,nomorethanoneoperationcanbeconductedon260aspecificmachine.Eq.(6)meansthattheremainedworkloadofanoperationwhenitarrivesatthesystemisequaltoitstotalworkload,anditistheinitialremainedworkload.Eq.(7)meansthattheprocessingrateofanoperationiseither1or0,whichcapturesthetwostatesofanoperation,i.e.,beingprocessedornotbeingprocessed.FromEqs.(1)-(7),weknowthatweneedtocontroltheprocessingrateofeveryoperationto265maketheremainedworkloadsofalltheproductdecreaseuntilarrivingat0sothattheaveragesojourntimeisminimized.Tosolvethisproblem,wewillgointwosteps:First,weconstructthedesiredtrajectoriesofthedecreasingoftheremainedworkloadsforalltheproductsinthesystems.Second,wedevelopamethodtoschedulingtheoperationssothattheactualremainedworkloadsofeveryproductcantraceitsdesiredtrajectory.2704DynamicSchedulingAlgorithmThemainideaofthedynamicschedulingalgorithmforanOKPsystemcanbesummarizedasfollows:(1)Supposethattheproductionsarriveatthesystemconsecutivelywithexponentiallydistributedinter-arrivaltime.275(2)Foraproducti,onceitarrivesattheOKPsystem,calculatethefastestdecreasingitrajectory,whichisdenotedbyxmin(t)),andslowestdecreasingtrajectory,whichisdenotedbyixmax(t),ofitsremainedworkloadasfollows:First,onceproductiarrivesatthesystem,giveitthehighestpriority.Namely,amongtheoperationsoneverymachine,theoperationsofproductiwillbeprocessedbeforetheoperationsof280otherproductsalreadyinthesystem.Inthiscase,productiwillnotbedelayedbyotherproducts,iiiandthereforexi(t)willdecreasefastest.Sowedenoteitbyxmin(t)fort[ai,fmin].Here,fministheiiiiearliestfinishingtimeofproducti.Obviously,xmin(t)=0fortfmin.xmin(t)andfmincanbeobtainedbydiscreteeventsimulationbasedontheRTPNmodel.Second,onceproductiarrivesatthesystem,giveitthelowestpriority.Namely,amongthe285operationsoneverymachine,theoperationsofproductiwillbeprocessedaftertheoperationsofotherproductsalreadyinthesystem.Inthiscase,otherproductswillnotbedelayedbyproducti,-7- 中国科技论文在线http://www.paper.edu.cniiiandthereforexi(t)willdecreasemostslowly.Wedenoteitbyxmax(t)fort[ai,fmax].Here,fmaxiiiiisthelatestfinishingtimeofproducti.Obviously,xmax(t)=0fortfmax.xmax(t)andfmaxcanbeobtainedbydiscreteeventsimulationtechniquebasedontheRTPNmodel.iii290(4)Accordingtothetrajectoriesxmin(t)andxmax(t),constructafunctionri(t)satisfyingxmin(t)iiiii0fort[ai,fmin);andxmin(t)=0fortfimin.315(2)Assignthelowestprioritytoproducti.Namely,amongtheoperationsoneverymachine,theoperationsofproductiwillbeprocessedaftertheoperationsofotherproductsalreadyinthesystem.Inthiscase,otherproductswillnotbedelayedbyproducti,thecompletiontimeofthisiproductwillbethelatest(whichisdenotedbyfmax),andtheremainedworkloadofproducti-8- 中国科技论文在线http://www.paper.edu.cniiiidecreasesmostslowly(whichisdenotedbyxmax(t)).xmax(t)>0fort[ai,fmax);andxmax(t)=0iiii320fortfmax.Obviously,xmax(t)>xmin(t)holdsfort[ai,fmax).iiiStep2.Constructafunctionri(t)satisfyingxmin(t)0,thenrepeatStep3.1.Ifxi(t)=0,thenupdatethesetQtbydeletingproductifromitandrepeatStep3.1untilthesetQtbecomesempty.Step4.RegulatethedesiredtrajectoriesofremainedworkloadstominimizetheaveragesojourntimeoftheOKPsystem.FromEq.(8),weknowthatthedesiredtrajectoriesofremained360workloadsri(t)arecompletelydeterminedbytheparametersI,fori=1,…,I.Therefore,thefinalproblem(P2)tobesolvedcanbedefinedasfollows:I1Minfiiai(12)Ii1wherefiistheactualcompletiontimeofproducti,whichisdeterminedbytheparametersi.TheproblemP2canbesolvedbygeneticalgorithm(GA).Foreachtimeofevaluatingthevalueoffi365(i),runfromStep1throughStep3.Oncetheterminationconditionofthegeneticalgorithmissatisfied,terminatethealgorithm.ThestructureofthedynamicschedulingalgorithmofanOKPsystemisillustratedinFig.4.Fig.4.StructureofthedynamicschedulingalgorithmofanOKPsystem-10- 中国科技论文在线http://www.paper.edu.cn3705NumericalExperimentsInthissection,numericalexperimentsareconductedtoexaminetheperformanceoftheproposeddynamicschedulingalgorithmofanOKPsystem,andtocompareitwithtwoclassicaldynamicschedulingrules,i.e.,thefist-come-first-service(FCFS)ruleandtheleast-remained-workload(LRW)rule(namely,theproductwiththeleastremainedworkloadis375processfirst).Numericalexperimentsandcomparisonstudiesaremadefordifferentscenariosdefinedbythenumberofproducts,thenumberofoperationsinaproduct(whichisarandomvariableuniformlydistributedinagiveninterval),andtheinter-arrivaltimebetweenproducts(whichisassumedtobeexponentiallydistributedwithaknownmeanvalue).TheaveragesojourntimesoftheproductsintheproductionsystemindifferentscenariosareshowninTableI.From380TableI,weknowthattheaveragesojourntimeundertheproposeddynamicschedulingalgorithmisobviouslyshorterthanthesojourntimeundertheFCFSruleandtheLRWrule,ineveryscenario.TableI.AverageSojournTimesinDifferentScenariosandUnderDifferentSchedulingRules(i.e.,theproposeddynamicschedulingalgorithm,theFCFSrule,andtheLRWrule)Case1:Operationnumberisuniformlydistributedin[7,10].Meanofinter-arrivaltimeis10.352515ProductQty.71.472160.546157.2193ProposedAlg.107.132191.534681.0044FCFSrule96.783169.084662.7442LRWruleCase2:Operationnumberisuniformlydistributedin[7,10].Meanofinter-arrivaltimeis5.ProductQty.352515ProposedAlg.78.331369.187465.9221FCFSrule121.7329102.137577.5431LRWrule107.580977.174269.0468Case3:Operationnumberisuniformlydistributedin[10,13].Meanofinter-arrivaltimeis10.ProductQty.352515ProposedAlg.83.062468.862666.8142FCFSrule122.2820107.169481.0044LRWrule105.933781.237572.4651Case4:Operationnumberisuniformlydistributedin[10,13].Meanofinter-arrivaltimeis5.ProductQty.352515ProposedAlg.94.526381.729477.2931FCFSrule146.7812129.9345106.6683LRWrule122.931795.061583.5215385Note:“ProductQty.”meansthequantityofproductsprocessedintheOKPsystem.“ProposedAlg.”referstotheproposeddynamicschedulingalgorithm.6ConclusionInthispaper,thedynamicschedulingproblemofaone-of-a-kindproductionsystemisinvestigated.Atfirst,areconfigurabletimedPetrinet-basedmodelisconstructedforOKPsystems-11- 中国科技论文在线http://www.paper.edu.cn390soastorealizeitsdiscreteeventsimulationofdynamicproductionschedulingandtheevaluationoftheperformanceofscheduling,i.e.,theaveragesojourntimeofproducts.Afterthat,themathematicalmodelofthedynamicproductionschedulingproblemisconstructedandadynamicproductionschedulingalgorithmisdeveloped.Unliketraditionalschedulingrulesandalgorithms,theproposedalgorithmisbasedonthereal-timestatusoftheremainedworkloadofeveryproduct395thatisprocessedintheOKPsystem.Onceanewproductarrivesatthesystem,adesireddecreasingtrajectoryofremainedworkloadisdesignedandtheproposedalgorithmtendstoscheduletheoperationsofeveryin-processproductsothattheirremainedworkloadscantrackthedesiredtrajectories.Numericalexperimentsareconductedtoevaluateperformanceoftheproposedalgorithmandcompareitwiththetraditionalfirst-in-first-outruleandthe400least-remained-workloadrule,andtheresultstellusthattheaveragesojourntimeundertheproposeddynamicschedulingalgorithmisshorterthantheaveragesojourntimeundertheFCFSruleortheLRWrule,indifferentscenariosdefinedbythenumberofproducts,numberoftheoperationsinaproduct,andtheinter-arrivaltimeofproducts.Infutureresearch,wewillextendtheworkinthispapertotheOKPsystemunderuncertainties(e.g.randomprocessingtimeof405everyoperation,unreliablemachineavailability,anddisturbancecausedbyurgentjobs)anddevelopdynamicschedulingalgorithmswithgoodrobustness.References[1]J.C.Wortmann,D.R.MuntslagandP.J.M.Timmermans,Customer-DrivenManufacturing.London:410Chapman&Hall,1997.[2]Y.TuandP.Dean,One-of-a-KindProduction,London:SpringerVerlag,2011.[3]P.R.Dean,Y.L.TuandD.Xue,"Aninformationsystemforone-of-a-kindproduction,"InternationalJournalofProductionResearch,vol.47,no.4,pp.1071-1087,2009.[4]G.Hong,L.Hu,D.Xue,Y.L.TuandY.L.Xiong,"Identificationoftheoptimalproductconfigurationand415parametersbasedonindividualcustomerrequirementsonperformanceandcostsinone-of-a-kindproduction,"InternationalJournalofProductionResearch,vol.46,no.12,pp.3297-3326,2008.[5]G.Hong,D.XueandY.Tu,"Rapididentificationoftheoptimalproductconfigurationanditsparametersbasedoncustomer-centricproductmodelingforone-of-a-kindproduction,"ComputersinIndustry,vol.61,no.3,pp.270-279,2010.420[6]X.Luo,W.Li,Y.Tu,D.XueandJ.Tang,"Optimalresourceallocationforhybridflowshopinone-of-a-kindproduction,"InternationalJournalofComputerIntegratedManufacturing,vol.23,no.2,pp.146-154,2010.[7]X.Luo,W.Li,Y.Tu,D.XueandJ.Tang,"Operatorallocationplanningforreconfigurableproductionlineinone-of-a-kindproduction,"InternationalJournalofProductionResearch,vol.49,no.3,pp.689-705,2011.[8]S.Q.Xie,Y.L.Tu,R.Y.K.FungandZ.D.Zhou,"Rapidone-of-a-kindproductdevelopmentviatheInternet:425aliteraturereviewofthestate-of-the-artandaproposedplatform,"InternationalJournalofProductionResearch,vol.41,no.18,pp.4257-4298,2003.[9]S.Q.Xie,X.XuandY.L.Tu,"Areconfigurableplatforminsupportofone-of-a-kindproductdevelopment,"InternationalJournalofProductionResearch,vol.43,no.9,pp.1889-1910,2005.[10]S.Q.Xie,andY.L.Tu,"Rapidone-of-a-kindproductdevelopment,"InternationalJournalofAdvanced430ManufacturingTechnology,vol.27,no.5-6,pp.421-430,2006.[11]M.ZandiehandM.A.Adibi,"Dynamicjobshopschedulingusingvariableneighbourhoodsearch,"InternationalJournalofProductionResearch,vol.48,no.8,pp.2449-2458,2010.[12]S.AlpayandN.Yüzügüllü,"Dynamicjobshopschedulingformissedduedateperformance,"InternationalJournalofProductionResearch,vol.47,no.15,pp.4047-4062,2009.435[13]V.VinodandR.Sridharan,"Schedulingadynamicjobshopproductionsystemwithsequence-dependentsetups:Anexperimentalstudy,"RoboticsandComputer-IntegratedManufacturing,vol.24,no.3,pp.435-449,2008.[14]V.VinodandR.Sridharan,"Simulationmodelingandanalysisofdue-dateassignmentmethodsandschedulingdecisionrulesinadynamicjobshopproductionsystem,"InternationalJournalofProduction440Economics,vol.129,no.1,pp.127-146,2011.[15]A.Y.Ha,"Optimaldynamicschedulingpolicyforamake-to-stockproductionsystem,"OperationsResearch,vol.45,no.1,pp.42-53,1997.[16]W.XiangandH.P.Lee,"Antcolonyintelligenceinmulti-agentdynamicmanufacturingscheduling,"EngineeringApplicationsofArtificialIntelligence,vol.21,no.1,pp.73-85,2008.445[17]R.Zhou,A.Y.C.Nee,andH.P.Lee,"Performanceofanantcolonyoptimisationalgorithmindynamicjobshopschedulingproblems,"InternationalJournalofProductionResearch,vol.47,no.11,pp.2903-2920,2009.-12- 中国科技论文在线http://www.paper.edu.cn[18]Y.Tu,"Real-timeschedulingandcontrolofone-of-akindproduction,"ProductionPlanning&Control:TheManagementofOperations,vol.8,no.7,701-710,1997.[19]Y.Tu,"Productionplanningandcontrolinavirtualone-of-a-kindproductioncompany,"Computersin450Industry,vol.34,no.3,pp.271-283,1997.[20]B.K.ChoiandN.K.You,"Dispatchingrulesfordynamicschedulingofone-of-a-kindproduction,"InternationalJournalofComputerIntegratedManufacturing,vol.19,no.4,pp.383-392,2006.[21]W.Li,X.Luo,D.XueandY.Tu,"Aheuristicforadaptiveproductionschedulingandcontrolinflowshopproduction,"InternationalJournalofProductionResearch,vol.49,no.11,pp.3151-3170,2011.455[22]W.Li,B.R.Nault,D.XueandY.Tu,"Anefficientheuristicforadaptiveproductionschedulingandcontrolinone-of-a-kindproduction,"Computers&OperationsResearch,vol.38,no.1,pp.267-276,2011.[23]E.W.TNgai,D.C.K.Chau,J.K.L.Poon,A.Y.M.Chan,B.C.M.ChanandW.W.S.Wu,"ImplementinganRFID-basedmanufacturingprocessmanagementsystem:Lessonslearnedandsuccessfactors,"JournalofEngineeringandTechnologyManagement,vol.29,no.1,pp.112-130,2012.460[24]J.BruseyandD.C.McFarlane,"EffectiveRFID-basedobjecttrackingformanufacturing,"InternationalJournalofComputerIntegratedManufacturing,vol.22,no.7,pp.638-647,2009.[25]T.Kelepouris,M.HarrisonandD.McFarlane,"Bayesiansupplychaintrackingusingserial-levelinformation,"IEEETransactionsonSystems,Man,andCybernetics-PartC:ApplicationsandReviews,vol.41,no.5,pp.733-742,2011.465[26]A.Brintrup,D.RanasingheandD.McFarlane,"RFIDopportunityanalysisforleanermanufacturing,"InternationalJournalofProductionResearch,vol.48,no.9,pp.2745-2764,2010.[27]G.Q.Huang,P.K.WrightandS.T.Newman,"Wirelessmanufacturing:aliteraturereview,recentdevelopments,andcasestudies,"InternationalJournalofComputerIntegratedManufacturing,vol.22,no.7,579-594,2009.470[28]G.Q.Huang,Y.F.Zhang,X.ChenandS.T.Newman,"RFID-enabledreal-timewirelessmanufacturingforadaptiveassemblyplanningandcontrol,"JournalofIntelligentManufacturing,vol.19,no.6,pp.701-713,2008.[29]G.Q.Huang,Y.F.ZhangandP.Y.Jiang,"RFID-basedwirelessmanufacturingforreal-timemanagementofjobshopWIPinventories.InternationalJournalofAdvancedManufacturingTechnology,"vol.36,no.7-8,pp.752-764,2008.475[30]Y.F.Zhang,T.Qu,O.K.HoandG.Q.Huang,"Agent-basedsmartgatewayforRFID-enabledreal-timewirelessmanufacturing,"InternationalJournalofProductionResearch,vol.49,no.5,1337-1352,2011.[31]M.L.Wang,T.Qu,R.Y.Zhong,Q.Y.Dai,X.W.ZhangandJ.B.He,"Aradiofrequencyidentification-enabledreal-timemanufacturingexecutionsystemforone-of-a-kindproductionmanufacturing:acasestudyinmouldindustry,"InternationalJournalofComputerIntegratedManufacturing,vol.25,no.1,pp.48020-34,2012.[32]Z.Jiang,M.J.Zuo,R.Y.K.FungandP.Y.L.Tu,“ColoredPetriNetswithchangeablestructures(CPN-CS)andtheirapplicationsinmodelingone-of-a-kindproduction(OKP)systems,”Computers&IndustrialEngineering,vol.41,no.3,pp.279-308,2001.485单件生产系统的动态调度方法汪峥，黄文杰（东南大学自动化学院，南京210096）摘要：本文对单件生产系统的动态调度问题进行研究，这里的动态调度指的是我们根据每个490产品的实时状态如何决定它的具体操坐从而达到产品平均逗留时间最短的目的。为了解决这个问题，我们为这个动态单件生产系统建立了一个可重构赋时Petri网模型并且建立了微分方程去刻画捕捉系统的动态特性，模型中剩余工作量是状态变量，产品生产率是控制变量。本文提出了一个动态生产调度策略，该策略通过建立所有产品的剩余工作量的期望轨迹并且使用基于遗传算法的方法跟踪该期望轨迹。实验表明文中所提出的动态调度算法求解出的平495均逗留时间远短于传统调度规则获得的结果。关键词：单件生产；动态生产调度；最优控制；Petri网；无线射频识别中图分类号：TP11-13-'