Scheduling调度和规划专题知识讲座

BeniAsllani

UniversityofTennesseeatChattanoogaSchedulingOperationsManagement-5thEditionChapter16RobertaRussell&BernardW.Taylor,IIILectureOutlineObjectivesinSchedulingLoadingSequencingMonitoringAdvancedPlanningandSchedulingSystemsTheoryofConstraintsEmployeeScheduling2WhatisScheduling?LaststageofplanningbeforeproductionoccursSpecifieswhenlabor,equipment,facilitiesareneededtoproduceaproductorprovideaservice3ScheduledOperationsProcessIndustryLinearprogrammingEOQwithnon-instantaneousreplenishmentMassProductionAssemblylinebalancingProjectProject-schedulingtechniques(PERT,CPM)BatchProductionAggregateplanningMasterschedulingMaterialrequirementsplanning(MRP)Capacityrequirementsplanning(CRP)4ObjectivesinSchedulingMeetcustomerduedatesMinimizejoblatenessMinimizeresponsetimeMinimizecompletiontimeMinimizetimeinthesystemMinimizeovertimeMaximizemachineorlaborutilizationMinimizeidletimeMinimizework-in-processinventory5ShopFloorControlLoadingCheckavailabilityofmaterial,machinesandlaborSequencingReleaseworkorderstoshopandissuedispatchlistsforindividualmachinesMonitoringMaintainprogressreportsoneachjobuntilitiscomplete6LoadingProcessofassigningworktolimitedresourcesPerformworkonmostefficientresourcesUseassignmentmethodoflinearprogrammingtodetermineallocation7AssignmentMethodPerformrowreductionssubtractminimumvalueineachrowfromallotherrowvaluesPerformcolumnreductionssubtractminimumvalueineachcolumnfromallothercolumnvaluesCrossoutallzerosinmatrixuseminimumnumberofhorizontalandverticallinesIfnumberoflinesequalsnumberofrowsinmatrixthenoptimumsolutionhasbeenfound.MakeassignmentswherezerosappearElsemodifymatrix

subtractminimumuncrossedvaluefromalluncrossedvaluesaddittoallcellswheretwolinesintersectothervaluesinmatrixremainunchangedRepeatsteps3through5untiloptimumsolutionisreached8AssignmentMethod:Example Rowreduction Columnreduction Coverallzeros 5 0 1 5 3 0 1 4 3 0 1 4 4 0 2 4 2 0 2 3 2 0 2 3 2 1 0 1 0 1 0 0 0 1 0 0 5 1 0 6 3 1 0 5 3 1 0 5

NumberlinesnumberofrowssomodifymatrixInitialPROJECTMatrix 1 2 3 4Bryan 10 5 6 10Kari 6 2 4 6Noah 7 6 5 6Chris 9 5 4 109AssignmentMethod:Example(cont.) Modifymatrix Coverallzeros 1 0 1 2 1 0 1 2 0 0 2 1 0 0 2 1 0 3 2 0 0 3 2 0 1 1 0 3 1 1 0 3Numberoflines=numberofrowssoatoptimalsolution

1 2 3 4Bryan 1 0 1 2Kari 0 0 2 1Noah 0 3 2 0Chris 1 1 0 3PROJECT

1 2 3 4Bryan 10 5 6 10Kari 6 2 4 6Noah 7 6 5 6Chris 9 5 4 10PROJECTProjectCost=(5+6+6+4)X$100=$2,10010SequencingPrioritizejobsassignedtoaresourceIfnoorderspecifiedusefirst-comefirst-served(FCFS)ManyothersequencingrulesexistEachattemptstoachievetoanobjective11SequencingRulesFCFS-first-come,first-servedLCFS-lastcome,firstservedDDATE-earliestduedateCUSTPR-highestcustomerprioritySETUP-similarrequiredsetupsSLACK-smallestslackCR-criticalratioSPT-shortestprocessingtimeLPT-longestprocessingtime12CriticalRatioRuleCRconsidersbothtimeandworkremaining CR== IfCR>1,jobaheadofschedule IfCR<1,jobbehindschedule IfCR=1,jobonschedule timeremaining duedate-today’sdate workremaining remainingprocessingtime13SequencingJobsThroughOneProcessFlowtime(completiontime)TimeforajobtoflowthroughthesystemMakespanTimeforagroupofjobstobecompletedTardinessDifferencebetweenalatejob’sduedate

anditscompletiontime14SimpleSequencingRules PROCESSING DUE JOB TIME DATE A 5 10 B 10 15 C 2 5 D 8 12 E 6 815SimpleSequencingRules:FCFS A 0 5 5 10 0 B 5 10 15 15 0 C 15 2 17 5 12 D 17 8 25 12 13 E 25 6 31 8 23 FCFS START PROCESSING COMPLETION DUE SEQUENCE TIME TIME TIME DATE TARDINESS16SimpleSequencingRules:DDATE C 0 2 2 5 0 E 2 6 8 8 0 A 8 5 13 10 3 D 13 8 21 12 9 B 21 10 31 15 16 DDATE START PROCESSING COMPLETION DUE SEQUENCE TIME TIME TIME DATE TARDINESS17A (10-0)–5=5B (15-0)-10=5C (5-0)–2=3D (12-0)–8=4E (8-0)–6=2SimpleSequencingRules:SLACK E 0 6 6 8 0 C 6 2 8 5 3 D 8 8 16 12 4 A 16 5 21 10 11 B 21 10 31 15 16 SLACK START PROCESSING COMPLETION DUE SEQUENCE TIME TIME TIME DATE TARDINESS18A (10)/5 =2.00B (15)/10 =1.50C (5)/2 =2.50D (12)/8 =1.50E (8)/6 =1.33SimpleSequencingRules:CR E 0 6 6 8 0 D 6 8 14 12 2 B 14 10 24 15 9 A 24 5 29 10 19 C 29 2 31 5 26 CR START PROCESSING COMPLETION DUE SEQUENCE TIME TIME TIME DATE TARDINESS19SimpleSequencingRules:SPT C 0 2 2 5 0 A 2 5 7 10 0 E 7 6 13 8 5 D 13 8 21 12 9 B 21 10 31 15 16 SPT START PROCESSING COMPLETION DUE SEQUENCE TIME TIME TIME DATE TARDINESS20SimpleSequencingRules:SummaryFCFS 18.60 9.6 3 23DDATE 15.00 5.6 3 16SLACK 16.40 6.8 4 16CR 20.80 11.2 4 26SPT 14.80 6.0 3 16 AVERAGE AVERAGE NO.OF MAXIMUM RULE COMPLETIONTIME TARDINESS JOBSTARDY TARDINESS21SequencingJobsThroughTwoSerialProcessJohnson’sRuleListtimerequiredtoprocesseachjobateachmachine.Setupaone-dimensionalmatrixtorepresentdesiredsequencewith#ofslotsequalto#ofjobs.Selectsmallestprocessingtimeateithermachine.Ifthattimeisonmachine1,putthejobasneartobeginningofsequenceaspossible.Ifsmallesttimeoccursonmachine2,putthejobasneartotheendofthesequenceaspossible.Removejobfromlist.Repeatsteps2-4untilallslotsinmatrixarefilledandalljobsaresequenced.22Johnson’sRule JOB PROCESS1 PROCESS2

A 6 8 B 11 6 C 7 3 D 9 7 E 5 10CEABD23Johnson’sRule(cont.)ABCDEEADBCProcess1(sanding)511203138EADBCProcess2(painting)51523303741IdletimeCompletiontime=41Idletime=5+1+1+3=1024GuidelinesforSelectingaSequencingRuleSPTmostusefulwhenshopishighlycongestedUseSLACKforperiodsofnormalactivityUseDDATEwhenonlysmalltardinessvaluescanbetoleratedUseLPTifsubcontractingisanticipatedUseFCFSwhenoperatingatlow-capacitylevelsDonotuseSPTtosequencejobsthathavetobeassembledwithotherjobsatalaterdate25MonitoringWorkpackageShoppaperworkthattravelswithajobGanttChartShowsbothplannedandcompletedactivitiesagainstatimescaleInput/OutputControlMonitorstheinputandoutputfromeachworkcenter2612345689101112Days123Today’sDateJob32BJob23CJob11CJob12AFacilityKey:PlannedactivityCompletedactivityBehindscheduleAheadofscheduleOnscheduleGanttChart27Input/OutputControlInput/OutputReportPlannedinput 65 65 70 75Actualinput 60 60 65 65 Deviation Plannedoutput 75 75 75 75 Actualoutput 70 70 65 65 Deviation Backlog 30 PERIOD 1 2 3 4 TOTAL28Input/OutputReportPlannedinput 60 65 70 75 270Actualinput 60 60 65 65 250Deviation 0 -5 -5 -10 -20Plannedoutput 75 75 75 75 300Actualoutput 70 70 65 65 270Deviation -5 -5 -10 -10 -30Backlog 30 20 10 10 10PERIOD 1 2 3 4 TOTALInput/OutputControl(cont.)29AdvancedPlanningandSchedulingSystemsInfinite-assumesinfinitecapacityLoadswithoutregardtocapacityThenlevelstheloadandsequencesjobsFinite-assumesfinite(limited)capacitySequencesjobsaspartoftheloadingdecisionResourcesareneverloadedbeyondcapacity30AdvancedPlanningandSchedulingSystems(cont.)Advancedplanningandscheduling(APS)Add-instoERPsystemsConstraint-basedprogramming(CBP)identifiesasolutionspaceandevaluatesalternativesGeneticalgorithmsbasedonnaturalselectionpropertiesofgeneticsManufacturingexecutionsystem(MES)monitorsstatus,usage,availability,quality31TheoryofConstraintsNotallresourcesareusedevenlyConcentrateonthe”bottleneck”resourceSynchronizeflowthroughthebottleneckUseprocessandtransferbatchsizestomoveproductthroughfacility32Drum-Buffer-RopeDrumBottleneck,beatingtosetthepaceofproductionfortherestofthesystemBufferInventory,placedinfrontofthebottlenecktoensureitisalwayskeptbusyDeterminesoutputorthroughputofthesystemRopeCommunicationsignal,tellsprocessesupstreamwhentheyshouldbeginproduction33TOCSchedulingProcedureIdentifybottleneckSchedulejobfirstwhoseleadtimetothebottleneckislessthanorequalbottleneckprocessingtimeForwardschedulethebottleneckmachineBackwardscheduletheothermachinestosustainthebottleneckscheduleTransferinbatchsizessmallerthantheprocessbatchsize34SynchronousManufacturingBACDB115B223B317C132C2110C3215D1310D228D335OperationjofitemiperformedatmachinecenterktakeslminutestoprocessItemiKey:iijkl35SynchronousManufacturing(cont.)Demand=100A’sMachinesetuptime=60minutes MACHINE1 MACHINE2 MACHINE3 B1 5 B2 3 C1 2 B3 7 C3 15 D3 5 C2 10 D2 8 D1 10 Sum 22 26* 17*Bottleneck36SynchronousManufacturing(cont.)Machine1Machine3SetupCompletiontime100223221227320200126019402737C2B1B3C3B2D2C1D1D3IdleSetupSetupSetupSetup156215121872SetupMachine2Idle237EmployeeSchedulingLaborisveryflexibleresourceSchedulingworkforceiscomplicatedrepetitivetaskAssignmentmethodcanbeusedHeuristicsarecommonlyused38EmployeeSchedulingHeuristicLet N=no.ofworkersavailable

Di=demandforworkersondayi

X=dayworking

O=dayoffAssignthefirstN-D1workersday1off.AssignthenextN-D2workersday2off.ContinueinasimilarmanneruntilalldaysarehavebeenscheduledIfnumberofworkdaysforfulltimeemployee<5,assignremainingworkdayssoconsecutivedaysoffarepossibleAssignanyremainingworktopart-timeemployeesIfconsecutivedaysoffaredesired,considerswitchingschedulesamongdayswiththesamedemandrequirements39 DAYOFWEEK M T W TH F SA SU MINNO.OF WORKERSREQUIRED 3 3 4 3 4 5 3 Taylor Smith Simpson Allen Dickerson EmployeeScheduling40 DAYOFWEEK M T W TH F SA SU MINNO.OF WORKERSREQUIRED 3 3 4 3 4 5 3 Taylor O X X O X X X Smith O X X O X X X Si