经济学Scheduling调度与规划.pptx

Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1 1Lecture OutlinewObjectives in SchedulingwLoadingwSequencingwMonitoringwAdvanced Planning and Scheduling SystemswTheory of ConstraintswEmployee SchedulingCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2 2What is Scheduling?wLast stage of planning before production occurswSpecifies when labor,equipment,facilities are needed to produce a product or provide a serviceCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-3 3Scheduled Operationsw wProcess IndustryProcess Industryn nLinear programmingLinear programmingn nEOQ with non-instantaneous EOQ with non-instantaneous replenishmentreplenishmentw wMass ProductionMass Productionn nAssembly line balancingAssembly line balancingw wProjectProjectn nProject-scheduling Project-scheduling techniques(PERT,CPM)techniques(PERT,CPM)w wBatch ProductionBatch Productionn nAggregate planningAggregate planningn nMaster schedulingMaster schedulingn nMaterial requirements Material requirements planning(MRP)planning(MRP)n nCapacity requirements Capacity requirements planning(CRP)planning(CRP)Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-4 4Objectives in Schedulingw wMeet customer due Meet customer due datesdatesw wMinimize job latenessMinimize job latenessw wMinimize response timeMinimize response timew wMinimize completion Minimize completion timetimew wMinimize time in the Minimize time in the systemsystemw wMinimize overtimeMinimize overtimew wMaximize machine or Maximize machine or labor utilizationlabor utilizationw wMinimize idle timeMinimize idle timew wMinimize work-in-Minimize work-in-process inventoryprocess inventoryCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-5 5Shop Floor ControlwLoadingLoadingn nCheck availability of material,machines and laborCheck availability of material,machines and laborwSequencingSequencingn nRelease work orders to shop and issue dispatch Release work orders to shop and issue dispatch lists for individual machineslists for individual machineswMonitoringMonitoringn nMaintain progress reports on each job until it is Maintain progress reports on each job until it is completecompleteCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-6 6LoadingwProcess of assigning work to limited resourceswPerform work on most efficient resourceswUse assignment method of linear programming to determine allocationCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-7 7Assignment Method1.1.Perform row reductionsPerform row reductionsn nsubtract minimum value in each subtract minimum value in each row from all other row valuesrow from all other row values2.2.Perform column reductionsPerform column reductionsn nsubtract minimum value in each subtract minimum value in each column from all other column column from all other column valuesvalues3.3.Cross out all zeros in matrixCross out all zeros in matrixuse minimum number of use minimum number of horizontal and vertical lineshorizontal and vertical lines4.4.If number of lines equals number of If number of lines equals number of rows in matrix then orows in matrix then optimum solution ptimum solution has been found.Make assignments has been found.Make assignments where zeros appearwhere zeros appear5.5.Else modify matrixElse modify matrix n nsubtract minimum uncrossed value subtract minimum uncrossed value from all uncrossed valuesfrom all uncrossed valuesn nadd it to all cells where two lines add it to all cells where two lines intersectintersectn nother values in matrix remain other values in matrix remain unchangedunchanged6.6.Repeat steps 3 through 5 until Repeat steps 3 through 5 until optimum solution is reachedoptimum solution is reachedCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-8 8Assignment Method:ExampleRow reductionRow reduction Column reduction Column reduction Cover all zeros Cover all zeros5 50 01 15 53 30 01 14 43 3014 44 40 02 24 42 20 02 23 32 2023 32 21 10 01 10 01 10 00 001005 51 10 06 63 31 10 05 53 3105 5Number lines Number lines number of rows so modify matrix number of rows so modify matrixInitial PROJECTInitial PROJECTMatrixMatrix1 12 23 34 4BryanBryan10105 56 61010KariKari6 62 24 46 6NoahNoah7 76 65 56 6ChrisChris9 95 54 41010Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-9 9Assignment Method:Example(cont.)Modify matrixModify matrixCover all zerosCover all zeros1 10 01 12 210120 00 02 21 100210 03 32 20 003201 11 10 03 31103Number of lines=number of rows so at optimal solutionNumber of lines=number of rows so at optimal solution1 12 23 34 4BryanBryan1 10 01 12 2KariKari0 00 02 21 1NoahNoah0 03 32 20 0ChrisChris1 11 10 03 3PROJECTPROJECT1 12 23 34 4BryanBryan101056 61010KariKari62 24 46 6NoahNoah7 76 65 56ChrisChris9 95 541010PROJECTPROJECTProject Cost=(5+6+6+4)X$100=$2,100Project Cost=(5+6+6+4)X$100=$2,100Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1010SequencingPrioritize jobs assigned to a resourceIf no order specified use first-come first-served(FCFS)Many other sequencing rules existEach attempts to achieve to an objectiveCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1111Sequencing Rules FCFS-first-come,first-servedFCFS-first-come,first-served LCFS-last come,first servedLCFS-last come,first served DDATE-earliest due dateDDATE-earliest due date CUSTPR-highest customer priorityCUSTPR-highest customer priority SETUP-similar required setupsSETUP-similar required setups SLACK-smallest slackSLACK-smallest slack CR-critical ratioCR-critical ratio SPT-shortest processing timeSPT-shortest processing time LPT-longest processing timeLPT-longest processing timeCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1212Critical Ratio RuleCR considers both time and work remainingCR considers both time and work remainingCR=CR=If CR 1,job ahead of scheduleIf CR 1,job ahead of scheduleIf CR 1,job behind scheduleIf CR 1,job behind scheduleIf CR=1,job on scheduleIf CR=1,job on scheduletime remainingtime remainingdue date-todays datedue date-todays datework remainingwork remainingremaining processing timeremaining processing timeCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1313Sequencing Jobs Through One ProcesswFlowtime(completion time)n nTime for a job to flow through the systemTime for a job to flow through the systemwMakespann nTime for a group of jobs to be completedTime for a group of jobs to be completedwTardinessn nDifference between a late jobs due date Difference between a late jobs due date and its completion timeand its completion timeCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1414Simple Sequencing RulesPROCESSINGPROCESSINGDUEDUEJOBJOBTIMETIMEDATEDATEA A5 51010B B10101515C C2 25 5D D8 81212E E6 68 8Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1515Simple Sequencing Rules:FCFSA A0 05 55 510100 0B B5 51010151515150 0C C15152 217175 51212D D17178 8252512121313E E25256 631318 82323FCFSFCFSSTARTSTARTPROCESSINGPROCESSINGCOMPLETIONCOMPLETIONDUEDUESEQUENCESEQUENCETIMETIMETIMETIMETIMETIMEDATEDATETARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1616Simple Sequencing Rules:DDATEC C0 02 22 25 50 0E E2 26 68 88 80 0A A8 85 5131310103 3D D13138 8212112129 9B B21211010313115151616DDATEDDATESTARTSTARTPROCESSINGPROCESSINGCOMPLETIONCOMPLETIONDUEDUESEQUENCESEQUENCETIMETIMETIMETIMETIMETIMEDATEDATETARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1717A(10-0)5=5B(15-0)-10=5C(5-0)2=3D(12-0)8=4E(8-0)6=2Simple Sequencing Rules:SLACKE E0 06 66 68 80 0C C6 62 28 85 53 3D D8 88 8161612124 4A A16165 5212110101111B B21211010313115151616SLACKSLACKSTARTSTARTPROCESSINGPROCESSINGCOMPLETIONCOMPLETIONDUEDUESEQUENCESEQUENCETIMETIMETIMETIMETIMETIMEDATEDATETARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1818A(10)/5=2.00B(15)/10=1.50C(5)/2=2.50D(12)/8=1.50E(8)/6=1.33Simple Sequencing Rules:CRE E0 06 66 68 80 0D D6 68 8141412122 2B B14141010242415159 9A A24245 5292910101919C C29292 231315 52626CRCRSTARTSTARTPROCESSINGPROCESSINGCOMPLETIONCOMPLETIONDUEDUESEQUENCESEQUENCETIMETIMETIMETIMETIMETIMEDATEDATETARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-1919Simple Sequencing Rules:SPTC C0 02 22 25 50 0A A2 25 57 710100 0E E7 76 613138 85 5D D13138 8212112129 9B B21211010313115151616SPTSPTSTARTSTARTPROCESSINGPROCESSINGCOMPLETIONCOMPLETIONDUEDUESEQUENCESEQUENCETIMETIMETIMETIMETIMETIMEDATEDATETARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2020Simple Sequencing Rules:SummaryFCFSFCFS18.6018.609.69.632323DDATEDDATE15.0015.005.6316SLACKSLACK16.4016.406.86.84 41616CRCR20.8020.8011.211.24 42626SPTSPT14.806.06.0316AVERAGEAVERAGEAVERAGEAVERAGENO.OFNO.OFMAXIMUMMAXIMUMRULERULECOMPLETION TIMECOMPLETION TIMETARDINESSTARDINESSJOBS TARDYJOBS TARDYTARDINESSTARDINESSCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2121Sequencing Jobs Through Two Serial ProcessJohnsons RuleJohnsons Rule1.1.List time required to process each job at each machine.List time required to process each job at each machine.Set up a one-dimensional matrix to represent desired Set up a one-dimensional matrix to represent desired sequence with#of slots equal to#of jobs.sequence with#of slots equal to#of jobs.2.2.Select smallest processing time at either machine.If Select smallest processing time at either machine.If that time is on machine 1,put the job as near to that time is on machine 1,put the job as near to beginning of sequence as possible.beginning of sequence as possible.3.3.If smallest time occurs on machine 2,put the job as If smallest time occurs on machine 2,put the job as near to the end of the sequence as possible.near to the end of the sequence as possible.4.4.Remove job from list.Remove job from list.5.5.Repeat steps 2-4 until all slots in matrix are filled and all Repeat steps 2-4 until all slots in matrix are filled and all jobs are sequenced.jobs are sequenced.Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2222Johnsons RuleJOBJOBPROCESS 1PROCESS 1PROCESS 2PROCESS 2A A6 68 8B B11116 6C C7 73 3D D9 97 7E E5 51010CEABDCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2323Johnsons Rule(cont.)ABCDEEADBCProcess 1Process 1(sanding)(sanding)5 51111202031313838EADBCProcess 2Process 2(painting)(painting)5 515152323303037374141Idle timeIdle timeCompletion time=41Idle time=5+1+1+3=10Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2424Guidelines for Selecting a Sequencing Rule1.1.SPT most useful when shop is highly congestedSPT most useful when shop is highly congested2.2.Use SLACK for periods of normal activityUse SLACK for periods of normal activity3.3.Use DDATE when only small tardiness values can Use DDATE when only small tardiness values can be toleratedbe tolerated4.4.Use LPT if subcontracting is anticipatedUse LPT if subcontracting is anticipated5.5.Use FCFS when operating at low-capacity levelsUse FCFS when operating at low-capacity levels6.6.Do not use SPT to sequence jobs that have to be Do not use SPT to sequence jobs that have to be assembled with other jobs at a later dateassembled with other jobs at a later dateCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2525MonitoringwWork packagen nShop paperwork that travels with a jobShop paperwork that travels with a jobwGantt Chartn nShows both planned and completed Shows both planned and completed activities against a time scaleactivities against a time scalewInput/Output Controln nMonitors the input and output from each Monitors the input and output from each work centerwork centerCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-26261 12 23 34 45 56 68 89 9101011111212DaysDays1 12 23 3Todays DateTodays DateJob 32BJob 32BJob 23CJob 23CJob 11CJob 11CJob 12AJob 12AFacilityFacilityKey:Key:Planned activityPlanned activityCompleted activityCompleted activityBehind scheduleBehind scheduleAhead of scheduleAhead of scheduleOn scheduleOn scheduleGantt ChartCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2727Input/Output ControlInput/Output ReportInput/Output ReportPlanned inputPlanned input6565656570707575Actual inputActual input6060606065656565DeviationDeviationPlanned outputPlanned output7575757575757575Actual outputActual output7070707065656565DeviationDeviationBacklogBacklog3030PERIODPERIOD1 12 23 34 4TOTALTOTALCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2828Input/Output ReportInput/Output ReportPlanned inputPlanned input6060656570707575270270Actual inputActual input6060606065656565250250DeviationDeviation0 0-5-5-5-5-10-10-20-20Planned outputPlanned output7575757575757575300300Actual outputActual output7070707065656565270270DeviationDeviation-5-5-5-5-10-10-10-10-30-30BacklogBacklog30302020101010101010PERIODPERIOD1 12 23 34 4TOTALTOTALInput/Output Control(cont.)Copyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-2929Advanced Planning and Scheduling SystemswInfinite-assumes infinite capacityn nLoads without regard to capacityLoads without regard to capacityn nThen levels the load and sequences jobsThen levels the load and sequences jobswFinite-assumes finite(limited)capacityn nSequences jobs as part of the loading Sequences jobs as part of the loading decisiondecisionn nResources are never loaded beyond Resources are never loaded beyond capacitycapacityCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-3030Advanced Planning and Scheduling Systems(cont.)wAdvanced planning and scheduling(APS)Advanced planning and scheduling(APS)n nAdd-ins to ERP systemsAdd-ins to ERP systemsn nConstraint-based programming(CBP)identifies a Constraint-based programming(CBP)identifies a solution space and evaluates alternativessolution space and evaluates alternativesn nGenetic algorithms based on natural selection Genetic algorithms based on natural selection properties of geneticsproperties of geneticsn nManufacturing execution system(MES)monitors Manufacturing execution system(MES)monitors status,usage,availability,qualitystatus,usage,availability,qualityCopyright 2006 John Wiley&Sons,Inc.Copyright 2006 John Wiley&Sons,Inc.16-16-3131Theory of ConstraintswNot all resources are used evenlyNot all resources are used evenlywConcentrate on the”bottleneck”resourceConcentrate on the”bottleneck”resourcewSynchronize flow through the bottleneckSynchronize flow through the bottleneckwUse process and transfer batch sizes to Use process and transfer batch sizes to move product through facilitymove product throug