經(jīng)濟學(xué)Scheduling調(diào)度與規(guī)劃

Copyright2006JohnWiley&Sons,Inc.16-1LectureOutlineObjectivesinSchedulingLoadingSequencingMonitoringAdvancedPlanningandSchedulingSystemsTheoryofConstraintsEmployeeSchedulingCopyright2006JohnWiley&Sons,Inc.16-2WhatisScheduling?LaststageofplanningbeforeproductionoccursSpecifieswhenlabor,equipment,facilitiesareneededtoproduceaproductorprovideaserviceCopyright2006JohnWiley&Sons,Inc.16-3ScheduledOperationsProcessIndustryLinearprogrammingEOQwithnon-instantaneousreplenishmentMassProductionAssemblylinebalancingProjectProject-schedulingtechniques(PERT,CPM)BatchProductionAggregateplanningMasterschedulingMaterialrequirementsplanning(MRP)Capacityrequirementsplanning(CRP)Copyright2006JohnWiley&Sons,Inc.16-4ObjectivesinSchedulingMeetcustomerduedatesMinimizejoblatenessMinimizeresponsetimeMinimizecompletiontimeMinimizetimeinthesystemMinimizeovertimeMaximizemachineorlaborutilizationMinimizeidletimeMinimizework-in-processinventoryCopyright2006JohnWiley&Sons,Inc.16-5ShopFloorControlLoadingCheckavailabilityofmaterial,machinesandlaborSequencingReleaseworkorderstoshopandissuedispatchlistsforindividualmachinesMonitoringMaintainprogressreportsoneachjobuntilitiscompleteCopyright2006JohnWiley&Sons,Inc.16-6LoadingProcessofassigningworktolimitedresourcesPerformworkonmostefficientresourcesUseassignmentmethodoflinearprogrammingtodetermineallocationCopyright2006JohnWiley&Sons,Inc.16-7AssignmentMethodPerformrowreductionssubtractminimumvalueineachrowfromallotherrowvaluesPerformcolumnreductionssubtractminimumvalueineachcolumnfromallothercolumnvaluesCrossoutallzerosinmatrixuseminimumnumberofhorizontalandverticallinesIfnumberoflinesequalsnumberofrowsinmatrixthenoptimumsolutionhasbeenfound.MakeassignmentswherezerosappearElsemodifymatrix

subtractminimumuncrossedvaluefromalluncrossedvaluesaddittoallcellswheretwolinesintersectothervaluesinmatrixremainunchangedRepeatsteps3through5untiloptimumsolutionisreachedCopyright2006JohnWiley&Sons,Inc.16-8AssignmentMethod: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

Numberlines

numberofrowssomodifymatrixInitialPROJECTMatrix 1 2 3 4Bryan 10 5 6 10Kari 6 2 4 6Noah 7 6 5 6Chris 9 5 4 10Copyright2006JohnWiley&Sons,Inc.16-9AssignmentMethod: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,100Copyright2006JohnWiley&Sons,Inc.16-10SequencingPrioritizejobsassignedtoaresourceIfnoorderspecifiedusefirst-comefirst-served(FCFS)ManyothersequencingrulesexistEachattemptstoachievetoanobjectiveCopyright2006JohnWiley&Sons,Inc.16-11SequencingRulesFCFS-first-come,first-servedLCFS-lastcome,firstservedDDATE-earliestduedateCUSTPR-highestcustomerprioritySETUP-similarrequiredsetupsSLACK-smallestslackCR-criticalratioSPT-shortestprocessingtimeLPT-longestprocessingtimeCopyright2006JohnWiley&Sons,Inc.16-12CriticalRatioRuleCRconsidersbothtimeandworkremaining CR== IfCR>1,jobaheadofschedule IfCR<1,jobbehindschedule IfCR=1,jobonschedule timeremaining duedate-today’sdate workremaining remainingprocessingtimeCopyright2006JohnWiley&Sons,Inc.16-13SequencingJobsThroughOneProcessFlowtime(completiontime)TimeforajobtoflowthroughthesystemMakespanTimeforagroupofjobstobecompletedTardinessDifferencebetweenalatejob’sduedate

anditscompletiontimeCopyright2006JohnWiley&Sons,Inc.16-14SimpleSequencingRules PROCESSING DUE JOB TIME DATE A 5 10 B 10 15 C 2 5 D 8 12 E 6 8Copyright2006JohnWiley&Sons,Inc.16-15SimpleSequencingRules: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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-16SimpleSequencingRules: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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-17A (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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-18A (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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-19SimpleSequencingRules: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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-20SimpleSequencingRules: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 TARDINESSCopyright2006JohnWiley&Sons,Inc.16-21SequencingJobsThroughTwoSerialProcessJohnson’sRuleListtimerequiredtoprocesseachjobateachmachine.Setupaone-dimensionalmatrixtorepresentdesiredsequencewith#ofslotsequalto#ofjobs.Selectsmallestprocessingtimeateithermachine.Ifthattimeisonmachine1,putthejobasneartobeginningofsequenceaspossible.Ifsmallesttimeoccursonmachine2,putthejobasneartotheendofthesequenceaspossible.Removejobfromlist.Repeatsteps2-4untilallslotsinmatrixarefilledandalljobsaresequenced.Copyright2006JohnWiley&Sons,Inc.16-22Johnson’sRule JOB PROCESS1 PROCESS2

A 6 8 B 11 6 C 7 3 D 9 7 E 5 10CEABDCopyright2006JohnWiley&Sons,Inc.16-23Johnson’sRule(cont.)ABCDEEADBCProcess1(sanding)511203138EADBCProcess2(painting)51523303741IdletimeCompletiontime=41Idletime=5+1+1+3=10Copyright2006JohnWiley&Sons,Inc.16-24GuidelinesforSelectingaSequencingRuleSPTmostusefulwhenshopishighlycongestedUseSLACKforperiodsofnormalactivityUseDDATEwhenonlysmalltardinessvaluescanbetoleratedUseLPTifsubcontractingisanticipatedUseFCFSwhenoperatingatlow-capacitylevelsDonotuseSPTtosequencejobsthathavetobeassembledwithotherjobsatalaterdateCopyright2006JohnWiley&Sons,Inc.16-25MonitoringWorkpackageShoppaperworkthattravelswithajobGanttChartShowsbothplannedandcompletedactivitiesagainstatimescaleInput/OutputControlMonitorstheinputandoutputfromeachworkcenterCopyright2006JohnWiley&Sons,Inc.16-2612345689101112Days123Today’sDateJob32BJob23CJob11CJob12AFacilityKey:PlannedactivityCompletedactivityBehindscheduleAheadofscheduleOnscheduleGanttChartCopyright2006JohnWiley&Sons,Inc.16-27Input/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 TOTALCopyright2006JohnWiley&Sons,Inc.16-28Input/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.)Copyright2006JohnWiley&Sons,Inc.16-29AdvancedPlanningandSchedulingSystemsInfinite-assumesinfinitecapacityLoadswithoutregardtocapacityThenlevelstheloadandsequencesjobsFinite-assumesfinite(limited)capacitySequencesjobsaspartoftheloadingdecisionResourcesareneverloadedbeyondcapacityCopyright2006JohnWiley&Sons,Inc.16-30AdvancedPlanningandSchedulingSystems(cont.)Advancedplanningandscheduling(APS)Add-instoERPsystemsConstraint-basedprogramming(CBP)identifiesasolutionspaceandevaluatesalternativesGeneticalgorithmsbasedonnaturalselectionpropertiesofgeneticsManufacturingexecutionsystem(MES)monitorsstatus,usage,availability,qualityCopyright2006JohnWiley&Sons,Inc.16-31TheoryofConstraintsNotallresourcesareusedevenlyConcentrateonthe”bottleneck”resourceSynchronizeflowthroughthebottleneckUseprocessandtransferbatchsizestomoveproductthroughfacilityCopyright2006JohnWiley&Sons,Inc.16-32Drum-Buffer-RopeDrumBottleneck,beatingtosetthepaceofproductionfortherestofthesystemBufferInventory,placedinfrontofthebottlenecktoensureitisalwayskeptbusyDeterminesoutputorthroughputofthesystemRopeCommunicationsignal,tellsprocessesupstreamwhentheyshouldbeginproductionCopyright2006JohnWiley&Sons,Inc.16-33TOCSchedulingProcedureIdentifybottleneckSchedulejobfirstwhoseleadtimetothebottleneckislessthanorequalbottleneckprocessingtimeForwardschedulethebottleneckmachineBackwardscheduletheothermachinestosustainthebottleneckscheduleTransferinbatchsizessmallerthantheprocessbatchsizeCopyright2006JohnWiley&Sons,Inc.16-34SynchronousManufacturingBACDB115B223B317C132C2110C3215D1310D228D335OperationjofitemiperformedatmachinecenterktakeslminutestoprocessItemiKey:iijklCopyright2006JohnWiley&Sons,Inc.16-35SynchronousManufacturing(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*BottleneckCopyright2006JohnWiley&Sons,Inc.16-36SynchronousManufacturing(cont.)Machine1Machine3SetupCompletiontime100223221227320200126019402737C2B1B3C3B2D2C1D1D3IdleSetupSetupSetupSetup156215121872SetupMachine2Idle2Copyright2006JohnWiley&Sons,Inc.16-37EmployeeSchedulingLaborisveryflexibleresourceSchedulingworkforceiscomplicatedrepetitivetaskAssignmentmethodcanbeusedHeuristicsarecommonlyusedCopyright2006JohnWiley&Sons,Inc.16-38EmployeeSchedulingHeuristicLet N=no.ofworkersavailable

Di=demandforworkersondayi

X=dayworking

O=dayoffAssignthefirstN-D1workersday1off.AssignthenextN-D2workersday2off.ContinueinasimilarmanneruntilalldaysarehavebeenscheduledIfnumberofworkdaysforfulltimeemployee<5,assignremainingworkdayssoconsecutivedaysoffarepossibleAssignanyremainingworktopart-timeemployeesIfconsecutivedaysoffaredesired,considerswitchingschedulesamongdayswiththesamedemandrequirementsCopyright2006JohnWiley&Sons,Inc.16-39 DAYOFWEEK M T W TH F SA SU MINNO.OF WORKERSREQUIRED 3 3 4 3 4 5 3 Taylor Smith Simpson Allen Dickerson EmployeeSchedulingCopyright2006JohnWiley&Sons,Inc.16-40 DAYOFWEEK M T W TH F SA SU MINNO.OF WORKERSREQUIRED 3 3 4 3 4 5 3 Ta