外文翻译 - 车间作业调度(JSSP)技术问题简明综述

外文原文Concisereviewjobshopschedulingproblem(JSSP)technologyLintroductionProductionschedulingisthecorecontentofCIMSresearchfieldproductionmanagementandkeytechnology,jobshopschedulingproblem(JSSP)isthemostdifficultconstraintcombinatorialoptimizationproblemandatypicalnp-hardproblem,itscharacteristicisnotaneffectivealgorithmtofindouttheoptimalsolutioninpolynomialtime.Moderneconomyincreasinglyintensivecompetitiontrendandchanginguserrequirementsforproducerstorevaluatethemanufacturingstrategy,suchasshorterproductioncycleandjust-in-timeinventorysystems,suchastheJSSPproductionenvironmentisthemostsuitableformeettheneedsofeconomicandexistingusers.Useoflimitedresourcestosatisfytheprocessingofvariousconstraints,anddeterminetheworkpieceontherelatedequipmenttoprocesstheorderandtime,toensuretheperformanceoftheselectedoptimum,canpotentiallyimprovetheeconomicbenefitsofenterprises,theJSSPhasanumberofpracticalapplicationbackground,development,preciseschedulingalgorithmisaneffectiveschedulingandoptimizationareaimportanttopic.TheJSSPproblemsinitiallyusingoptimizationmethod,butcalculationcantbeverybig,andpractical.Inrecentyears,basedonbiology,physics,artificialintelligence,neuralnetworks,therapiddevelopmentofcomputertechnologyandsimulationtechnology,hasopenedupanewtrainofthoughtfortheresearchofschedulingproblem.Inthispaper,accordingtotheJSSPproblemofalargenumberofliterature,theclassificationofthetheoryandmethodofstudyonthesystemandintroducestherecentdevelopmentsinthisfield,discussthedirectionoffurtherresearch.2thegeneralframeworkofJSSPproblem2.1problemdescriptionJSSPproblemcanbedescribedas:machinesetin()addaworkpieceset|in(),eachartifactcontainsaprocesssetcomposedofmulti-channelprocess.Artifactshaveapredeterminedsequence,eachworkingprocedureofprocessingtimetatagiventimeeachmachinecanonlybeaworkpieces,andeachpiececanonlybehandledbyamachine.Differentworkpiecemachiningsequenceisunrestricted,processesarenotallowedtointerrupt;ForthebeginningtimeofeachworkingprocedureinthefeasibleschedulingMinimizethetotalcompletiontime,namelyWorkpiecemachiningsequenceofsolvingsatisfiestheconditionsthatconstitutetheJSSPschedulingproblem.Lineproductionschedulingproblem(FSSP)isaspecialformofJSSPproblemshavethesameprocessingoperations(i.e.,allartifacts).Inadditiontheobjectivefunctioncanselectwaitingtime,processtimeanddelaytimeaverageandmaximum,ormultipletargetcombinationformofmulti-objectiveproblem.2.2JSSPmodelrepresentation2.2.1integerprogramming(IP)modelIntegerprogrammingmodelisputforwardbytheBaker,needtoconsidertwokindsofconstraints:workpiecebeforeandaftertheprocessofconstraintsandworkingprocedureofcongestionconstraints.Saidtheworkpieceonthemachinekj,eachinandtheprocessingtimeandcompletiontime.Ifthemachinetheworkpiecemachiningprocessonthehkbeforemachine(use),hastherelation;Ontheotherhand,if,thereis.Defineinstructionscoefficient,toalargenumber,thentheprocessconstraintisexpressedasbeforeandafter;Processnon-blockingconstraintsareexpressedas:totargettheIPmodelcanbeexpressedas:Iftheaverageprocesstimeasobjectivefunction,whichcanbechanged.MwithinthescopeofthefeasibleregionoflargenumberofvaluesgivenbyVanHulle:.2.2.3graphmodelJSSPofconnectiondiagrammodelisputforwardbyBalas,N,containingalltheworkingprocedureoftherepresentativenodecontainsAlinkadjacentprocesswiththesameworkpieceedge,Econtainslinksonthesamemachineprocessingprocessoftheconnection,theconnectioncanhavetwopossibledirection.Theschedulingprocessconnectfixedallofthedirectionoftheedge,todeterminetheorderofthesamemachineworkingprocedure,andUSEStheconnectionwithpreferredarrowwhilereplacingtheconnection.3JSSPresearchmethodsThroughtheanalysisofalargenumberofliteratureresearchmethodsofJSSPareclassifiedintotwocategories:optimizationmethodandtheapproximate/heuristicmethod.Optimizationmethodsmainlyincludemixedintegerlinearprogramming(MILP),branchandbound(B&B)methodandLaplacerelaxationmethod,etc.Approximate/heuristicwasoriginallyduetosmallamountofcalculationandthealgorithmiseasytoimplementandintroducingtheJSSPproblems,mainlyincludingprioritydispatchingrules(PDRs),artificialintelligence(AI),neuralnetwork(NN)andadjacentdomainsearchmethod(NS).Theneighborhoodsearchmethodandtabusearch(TS),geneticalgorithm(GA)andsimulatedannealing(SA),etc.CanbesaidAstheheuristic(Meta-heuristic)approximationoptimizationmethod3.1optimizationmethodOptimizationmethodisabletogenerateanaccuratemethodoftheoptimalsolution.JohnsonwasoriginallyproposedinviewoftheproblemsJohnsonrules,althoughitisaccordingtothemethodofcalculatingtheflowprocess,butithasagreatinfluenceonthelaterresearch.SincethenhaveapolynomialtimealgorithmtosolvethespecialJSSPproblems,suchastheresearchlaidthefoundationoftheclassicalschedulingtheory.In6osofthe20thcentury,inviewofsolvingintegerprogrammingproblems,putforwardusingmoresophisticatedmathematicalstructuretoeliminateimpliedthesearchingspaceoftheoptimalsolutioninordertoimprovethesearchingefficiencyofenumerationalgorithm,branchandboundmethod(B&B)hasgreatachievementsintheoreticalresearch.TheJSSPproblemofapossiblesolution,solarge-scaleproblemswithcompleteenumerationmethodoncalculationisnotpossible.7osemphasisonresearchincomputationalcomplexity,Lenstraprovesthatthreeconditionsaresuchasanp-hardproblem.BalasJSSPB8algorithm,thisproblemistheearliestthenCarlieretcbasedonJacksonslongesttotalprocessingtimeremaining(MWR)rulesofscheduling(JPS),advancehandhaveachievedgoodresults.ToovercomethelimitationsofmathematicalrepresentationandsoftwaremethodsandrecentDavisdecompositionstrategybasedonmathematicalprogrammingisputforward,suchastheschedulingproblemdecompositionmultiplesubproblems,considereachsubproblemrespectivelyanditslimit,toimprovetheabilitytocalculate.3.2approximate/heuristicmethod3.2.1prioritydispatchingrulesTheearliestdispatchrulesputforwardbyJacksonandSmith.DistributionrulesoftheJSSPSPT(theshortestprocessingtime),LPT(thelongestprocessingtime),MWR(thelongestremainingtotalprocessingtime),IWRresidualtotalprocessingtime(minimum),MOR(surplus)isthemaximumnumberofprocesses,LOR(minimumresidualprocessnumber),EDD(theearliestdeliverydate)andFCFS(choosethefirststeponthesamemachinetheworkpieceinthequeue),etc.Panwalkarthroughperformanceindexessuchasclassifiedtotalabout113dispatchingrules.Wu.Theschedulingrulescanbedividedintothreecategories,namely,jobinformationrelatedwiththecombinationofthepriorityrules,priorityrulesandswitchingandweighted.Prioritydispatchingrulesofapproximateoptimizationmethod,thekeyliesinhowtoperformanceforagivenproblem,choosethebestrules.Lookfromtheruleofoptimizationresults,SPTcanreducealltheaverageflowtimeofoperation,EDDtooptimizethemaximumextensionrelatedgoal.Therulesbetweentheswitchandtheresultingproblems(suchaserrorrepair)isrecentlyactiveareaofresearch.3.2.2artificialintelligencetechnologyInartificialintelligenceandexpertsysteminthe80shasanimportantroleinthestudyofscheduling,canproducemorecomplexthanprecedencerulesbasedontheheuristicschedulingsystem,andcangetalotofinformationfromthespecialdatastructure,thecalculationcomparisonisweakness.ISISistheearliestoneoftheexpertsystembasedonAItechnologytosolvespecificJSSP,useconstraintstoguidethesearchmethod,thegoalconstraintsbasedonthedateofdeliveryandtheproducts,theprocessingcapabilityasaphysicalconstraintsofresources.ISISisdividedintothreelayersstructure,respectivelychooseorder,capacityanalysis,executionscheduling,whileaddingarefactoringandmodifytheschedulingfunctionoflearning.Forlarge-scaleproblemislimitedtoasingleexpertsystemoflimitedknowledgeandability,addresourceagent,taskagentandagentcollaborationmechanism,recentlyappeareddistributedschedulingsystem.TheAItechnologyofhowtocoordinatetheproxymechanism,thereisnouniformdesignandguidingideas,centralizationanddecentralizationofjobschedulingideasarestillinthediscussion.3.2.3neuralnetworkmethodNeuralnetworkisappliedtotheschedulingproblemhasahistoryofmorethantenyears,theuseofguidinglearningneuralnetworktofindtherelationshipbetweenthesysteminput,outputandinputcharacteristicsincludejobcharacteristics(suchasquantity,paths,deliverytimeandprocessingtime,etc.),theoutputisrelatedtosortingandperformancemetrics.AppliedatpresentmostistheBPnetwork,Rabelarriveaccordingtodifferentpattern,thesortingprocessplansandproceduresafterusingvalue-addedJSSPneuralnetworkstosolvetheproblem,accordingtotheenergyfunctionofneuralnetworksisproposedbasedonrelaxationmodeldefinedHopfieldnetworktosolvetheproblemforaclassofclassicalscheduling.Duetoproducealargenumberofinfeasiblesolutionandcalculationtimeislonger,solvetheschedulingproblemofinefficientNN,andguidethelearningneuralnetworkbytrainingtypeistryingtofindtherelationshipbetweentheinputandoutput,astheproblemsizeincreases,thesizeofthenetworkalsoincreasessharply3.2.4neighborhoodsearchmethodSolvingJSSPandheuristicmethodisdevelopedbasedontheneighborhoodsearchstrategy,heuristicdonotattempttogettheoptimalsolutioninpolynomialtime,buttocompromiseincomputingtimeandschedulingresults.Herearethreekindsofrepresentativeofheuristic:1.Thesimulatedannealing(SA)SAisbasedontheMenteCarloiterativesolutionofakindofglobalprobabilitysearchalgorithm,isakindofserialoptimizationalgorithmanditsconvergencerequirestheinitialtemperatureshouldbehighenough,thesolutionspaceofeachstatecanappearinalmostthesameprobability.VanLaarhoovenforjssPproblemisputforward,suchasneighborhoodfunctionisanimportantsymbolofadjacentkeyprocessingorderoperationprocessofchange,andmustobeytheprocessconditionsofprocessingonthesamemachine.KolonkoprovestandardjssPneighborhoodisasymmetry,andbecauseoftheweakconvergenceofSA,putforwardonthebasisofSAcombinationofGAhybridheuristic.Literature28useSAacceptthenatureofthepoorindividualsatacertainprobability,combininggeneticalgorithmandimprovedtheselectionmechanismtoimproveconvergencespeed.Therecenttrendintheresearchfieldofschedulingproblemisabigistocombinedifferentneighborhoodsearchmethodtoformhybridheuristic.2.Thetabusearch(TS)TSisGloverproposedintelligentprocessofagraduallywithmemoryfunctioninglobaloptimizationalgorithm,tochangethesortofsearchinallthefeasiblesolutionspace.Bysettingthetaboolist,avoidfallingintolocaloptimalsearchorrepeatthepast,usingthemediumandlongtermstoragemechanismforstrengtheninganddiversityofthesearch,theJSSPproblemssuchastheLagunathreeTSschedulingstrategybasedonsimplemoving.Taillardcombiningacceleratedthestarttimeofsearchstrategytopreventrepeatedcalculationprocessandputsforwardafastvaluationstrategy,butonlyhalf-and-halfactivityschedulingeffectively.WhileNowickiconsideringthesolutionqualityandcomputationtime,suchascombinationofTaillardTSalgorithm,onthebasisoftheVanLaarhooven1neighborhood,applyasinglecriticalpathisdividedintodifferentblockstostrictlylimittheneighboringdomain,greatlyimprovethecomputationalefficiency.3.Geneticalgorithm(GA)3.2.5othertheoriesandtechnologies.FromthepointoftheresearchanddevelopmentofJSSP,hasmadecertainprogressontheoryandapplication,somenewresearchmethodsandtechniques:1)whenthesystemwithuncertainprocessingtimeoradjusttime,throughmodelingandfuzzysettheorytosolvethefuzzylogicapproach.Grabotofmulti-objectiveproblems,suchascombinationofdispatchingrulesusingfuzzylogicrule,andKruckyputforwardtoadjustproductmixofproductionlinetominimizethefuzzylogicofthetime.2)ReactiveScheduling(ReactiveScheduling)wasduetotheemergencysystemsabilitytorepairacompletedScheduling.Emergenciesincludingemergencyordersandinterruptresources,suchasasuddenemergenciestoScheduling(rescheduling).ReactiveSchedulinghasbecomeahottopicinthestudyofproductionScheduling,butitstechnologyisnotmatureenough.3)consideringtheinformalperformanceindexofthehomeworkinadvance/tardinesscostsjobsortingbasedonjust-in-time(JIT)productionmanagementtechnology,forjssPtheoryopensupanewresearchfield.4)inschedulingTheorycombinedwiththeactualproductionapplication,Eliyahul4isputforwardbasedontheTheoryofsynchronousmanufacturinglimited(goingofConstraints),isassociatedwiththemarketdemandtorapidlyandflexiblyintheproductionoftransfersystemmethodofmaterials,thereareafewkeylimit,itscoreschedulingistosorttheserestrictionsoperationplan.LimitTheoryissuccessfullyappliedtotheschedulingsystemasanexample.4discussionandprospectJSSPschedulingproblemnearly4oyearsofapplicationanddevelopmentstatusquo,withfruitfulresults,therearealsomanyproblemswhichremaintobesolvetheproblemComparedwiththeoptimizationalgorithms,approximation/heuristicalgorithmisofobviousadvantageliesin:heuristicalgorithmisrelativelysimple;Highcomputationalefficiency,thealgorithmisflexible.Buttheapproximate/heuristicalgorithmhasobviousdeficiency,whichlikelyproducedthantheglobaloptimalsolutionsofXieChaalot,andthedifferencedegreeisnotclearenough.Therefore,reasonablecalculationtimeandbegtheoptimalityofthesolutionbecamethestandardtomeasuretheperformanceoftheheuristicalgorithm.Aheuristicthanusedalonetwoheuristiccombininghybridheuristicalgorithmtoachievegoodresults.Neighborhoodsearchparetosolutionstocertainprobabilityofacceptance,soastoescapefromlocaloptimum,butitsmaindrawbackisthatneedmorestepstoimplement,howtochoosefromlocaltoglobaloptimalneighborhoodstructure,makeitshaveimprovedsexualanddiversityofthesearchmechanism,itisveryimportant.StopconditionissettoalargenumberofGA,willreachtheoptimalandthealgorithmcantstoptheproblem,thekeyishowtocoordinatetherelationshipbetween.TheAItechnologyandneuralnetwork,howtothroughtheinternaldistributionofparallelprocessingcapabilitiestoquicklyfindthesearchspaceanddecreasetheamountofcalculationofmassproblemneedsfurtherresearch.Theauthorthinksthatcanexpandtheresearchfromthefollowingseveralaspects:algorithmoftechnologyapplication.Theauthorthinksthatinallkindsofalgorithmtheoryandapplicationresearchinthefutureatthesametime,shouldpayattentiontothestructureofaunifiedframeworkandresearchsystem,absorbingachievementsofinterdisciplinary,theheuristicthanusedalonetwoheuristiccombininghybridheuristicalgorithmtoachievegoodresults.Neighborhoodsearchparetosolutionstocertainprobabilityofacceptance,soastoescapefromlocaloptimum,butitsmaindrawbackisthatneedmorestepstoimplement,how1.TheproblemofJSSP,thegeneralframework,modelandresearchmethodforsolvingproductionschedulingandothercomplexcombinatorialoptimizationproblemisareference,shouldexpandtomoregeneralJSSPproblemundertheconditionofresearch.2.Theconstraintsoflocalsearchalgorithmandenhancethefurtherstudyoftheconvergenceandcomputationspeed.3.Theproblemoflarge-scaleoptimizationproblemsasrestrictiveJSSPremainsachallenge,althoughheuristicalgorithmcanbettersolvelarge-scaleaskedProblem,butmustbemorein-depthstudyitsconvergenceanditslimitedtimelinessproblem.4.Theactualproductionenvironmentisdynamic,withchangingstructureandgoals,thereisalsotheschedulingoftheinterrupt.Ifuseofflineschedulingtoguidetheproductionprocess,makethewaittimeandanincreaseinquantityofproducts,equipmentutilization,productqualityandbatchprocessingperformance.Sotheinteractivescheduling(interactivescheduling)andonlineschedulingresearchistheresearchdirectioninthefuture.algorithmoftechnologyapplication.Theauthorthinksthatinallkindsofalgorithmtheoryandapplicationresearchinthefutureatthesametime,shouldpayattentiontothestructureofaunifiedframeworkandresearchsystem,absorbingachievementsofinterdisciplinary,the5.Seekingnewmathematicaltoolsandanalysismethods,establishingJSSPalgorithmcomplexityandconvergenceanalysisoftheresearchtheory,theconvergencespeedofthealgorithmEstimateandoptimizethedegrees.5conclusionJSSPprobleminthepast40yearsoftheoryandtechnicalmethods,andconcludestheexistingdecentralizedresultsinthisfieldandtheadvantagesanddisadvantagesofeachalgorithmoftechnologyapplication.Theauthorthinksthatinallkindsofalgorithmtheoryandapplicationresearchinthefutureatthesametime,shouldpayattentiontothestructureofaunifiedframeworkandresearchsystem,absorbingachievementsofinterdisciplinary,theintroductionofnewresearchtools,andthedevelopmentofnewhybridstrategyoralgorithm.Thefutureresearchshouldbefocusedondispatchingsystemcanbeused,maketheresearchtowardstherealdevelopmentisadvantageoustotheactualproductionofthefinalgoal.中文翻译车间作业调度(JSSP)技术问题简明综述l引言生产调度是CIMS研究领域生产管理的核心内容和关键技术，车间作业调度问题(JSSP)是最困难的约束组合优化问题和典型的NP难问题，其特点是没有一个有效的算法能在多项式时间内求出其最优解现代经济日益强化的竞争趋势和不断变化的用户需求要求生产者要重新估价生产制造策略，如更短的产品生产周期和零库存系统等，而JSSP生产环境最适宜满足现有经济和用户的需求利用有限的资源满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和时间，以保证所选择的性能指标最优，能够潜在地提高企业的经济效益，JSSP具有很多实际应用背景，开发有效而精确的调度算法是调度和优化领域重要的课题研究JSSP问题最初主要采用最优化方法，但计算规模不可能很大，且实用性差近年来，基于生物学、物理学、人工智能、神经网络、计算机技术及仿真技术的迅速发展，为调度问题的研究开辟了新的思路本文根据JSSP问题的大量文献，对研究理论与方法进行系统的分类并介绍这一领域的最新进展，讨论进一步的研究方向2JSSP问题的一般框架21问题描述JSSP问题可描述为：台机器(用集合表示)加个工件(用集合|表示)，每个工mn件包含由多道工序组成的一个工序集合工件有预先确定的加工顺序，每道工序的加工时间t在给定的时间每个机器只能加工一个工件，并且每个工件只能由一台机器处理不同工件的加工顺序无限制，工序不允许中断；要求在可行调度中确定每个工序的开始时间使总完工时间最小，即ijsmaxC求解满足以上条件的工件加工顺序即构成JSSP调度问题流水作业调度问题(FSSP)是JSSP问题的特殊形式(即所有工件有相同的加工工序)此外目标函数可选取等待时间、流程时间和延期时间的平均值或者最大值等，或多个目标组合形成的多目标问题22JSSP的模型表示221整数规划(IP)模型整数规划模型由Baker提出，需要考虑两类约束：工件工序的前后约束和工序的非堵塞约束用和分别表示工件j在机器k上的加工时间和完工时间如果机器h上jktc的工件加工工序先于机器K（用表示），则有关系式；反之，如果，有。定义指示系数，为一个大数，则工序的前后约束表示为；工序的非阻塞约束表示为：，以为目MmaxC标的IP模型可以表示为：如果以平均流程时间为目标函数，可以改成。大数M在可行区域范围内的取值由VanHulle给出：223图模型JSSP的非连接图模型由Balas提出，N包含代表所有工序的节点，A包含连接同一工件的邻接工序的边，E包含连接同一机器上加工工序的非连接边，非连接边可以有两个可能方向调度过程将固定所有非连接边的方向，以确定同一机器上工序的顺序，并采用带有优先箭头的连接边取代非连接边3JSSP的研究方法通过对大量文献的分析将JSSP的研究方法分为两大类：最优化方法和近似启发式方法最优化方法主要包括混合整数线性规划(MILP)、分枝定界(B&B)法以及拉氏松弛法等；近似启发式最初是由于计算量小并且算法易实现而引入JSSP问题的，主要包括优先分派规则(PDRs)、人工智能(AI)、神经网络(NN)及邻域搜索法(NS)邻域搜索法又包括禁忌搜索(TS)、遗传算法(GA)和模拟退火(SA)等可以称之为亚启发式(Metaheuristic)的近似优化方法31最优化方法最优化方法是能够产生一个精确最优解的方法。Johnson最早提出的针对问题的Johnson规则，虽然是针对流水作业的求解方法，但它对以后的研究有很大的影响此后相继有利用多项式时间算法求解等特殊的JSSP问题，这些研究奠定了经典调度理论的基础在20世纪6O年代，针对整数规划问题的求解，提出利用更加复杂的数学结构消除隐含非最优解的搜索空间以提高搜索效率的枚举算法，分枝定界法(BB)在理论研究上有很大成果对一个的JSSP问题有种可能的解，因此大规模问题用完全枚举法mnmn!在计算上是不可能的7O年代后侧重计算复杂性方面的研究，Lenstra等证明了三种情况都是NP难问题Balas最早提出JSSP问题的B8出算法，此后Carlier等基于Jackson的剩余总加工时间最长(MWR)规则提出预占先调度(JPS)，取得了较好的结果为克服数学表示和软件方法的局限性，近期Davis等提出基于数学规划的分解策略，将调度问题分解为多个子问题，分别考虑各子问题及其限制，提高了计算能力32近似启发式方法321优先分派规则最早的分派规则由Jackson和Smith等提出。JSSP的分配规则有SPT(最短加工时间)、LPT(最长加工时间)、MWR(剩余总加工时间最长)、IWR(剩余总加工时间最小)、MOR(剩余工序数最多)、LOR(剩余工序数最小)、EDD(最早交货期)和FCFS(选择同一机器上工件队列中的第一道工序)等Panwalkar等通过性能指标对113个分派规则归类总。wu。把调度规则分为三大类，即同作业信息相关的优先级规则、优