《生产与运作管理》八作业排序解析课件

1生产与运作管理浙江财经学院工商管理学院作业排序8CHAPTER1生产与运作管理作业排序CHAPTER浙江财经学院工商管理学院2生产运作管理模型输入待转化资源物料信息顾客输入转化资源设施员工顾客输入资源输出产品与服务改善计划与控制设计运作战略企业战略作业排序浙江财经学院工商管理学院2生产运作管理模型输入待转化浙江财经学院工商管理学院3本章主要内容作业排序的基本概念作业排序的表示方式流水作业排序问题单件作业排序问题服务排队系统设计中的心理因素浙江财经学院工商管理学院3本章主要内容作业排序的基本浙江财经学院工商管理学院4医院门诊病人治疗手术室大学排课教室工厂生产采购作业排序例子浙江财经学院工商管理学院4医院作业排序例子浙江财经学院工商管理学院5作业计划与排序作业排序(Sequencing)是确定加工对象的加工顺序作业计划(Scheduling)还要确定开始加工和完工的时间作业排序是作业计划的关键在实际中，这两个词经常被等同使用浙江财经学院工商管理学院5作业计划与排序作业排序(S浙江财经学院工商管理学院6作业排序的战略目的有效的排序可以提高设施的利用率，这意味着：有效的排序可以提高交货速度，这意味着：好的排序提供更低的成本更好的顾客服务更可靠的交货浙江财经学院工商管理学院6作业排序的战略目的有效的排浙江财经学院工商管理学院7前向排序与后向排序收到订单交货期订购原料作业1作业2作业3作业4订购原料作业1作业2作业3作业4前向排序后向排序请思考下列两种情况下适用哪种排序方式？按订单生产的企业为节省库存的费用浙江财经学院工商管理学院7前向排序与后向排序收到订单浙江财经学院工商管理学院8甘特图（Gantt

Chart）作业进度图表示一项工作的计划开始日期、计划完成日期以及现在的进度机器图（甘特负荷图）描述不同工作在每一台机器上的工作次序，可被用来管理生产进度浙江财经学院工商管理学院8甘特图（GanttCh浙江财经学院工商管理学院9作业进度甘特图工作11/1011/1111/1211/1311/1411/1511/1611/1711/1811/19ABC开始时间结束时间计划所用时间实际进度表示一项工作的计划开始日期、计划完成日期以及现在的进度浙江财经学院工商管理学院9作业进度甘特图工作11/1浙江财经学院工商管理学院10描述不同工作在每一台机器上的工作次序机器甘特图机器11/1111/1211/1311/1411/1511/1611/1711/18磨床抛光机开始时间结束时间计划所用时间实际进度非生产性时间ABCABC浙江财经学院工商管理学院10描述不同工作在每一台机器浙江财经学院工商管理学院11排序问题的分类主要是将不同工件安排到不同设备上，或安排不同的人做不同的工作劳动力作业排序生产作业排序主要是确定人员何时工作两种基本形式的作业排序浙江财经学院工商管理学院11排序问题的分类主要是将不浙江财经学院工商管理学院12制造业生产作业排序分类按机器数量分类单台机器的排序问题多台机器的排序问题单件作业排序问题

(Job-Shop)流水作业排序问题(Flow-Shop)按工件到达车间的情况不同静态排序问题动态排序问题工件陆续到达，要随时安排它们的加工顺序

排序时，所有工件都已到达，可一次性进行排序浙江财经学院工商管理学院12制造业生产作业排序分类按浙江财经学院工商管理学院13n个作业的单台机器排序问题(n/1)对于某一工作地，在给定的一段时间内，顺次决定下一个被加工的工件可能要考虑交付日期、在制品数量、全部完工时间等因素对象1对象2对象3对象n…工作地浙江财经学院工商管理学院13n个作业的单台机器排序问浙江财经学院工商管理学院14常用的优先顺序规则先到先服务优先选择完工期限最紧的工件优先选择加工时间最短的工件优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比优先选择余下加工时间最长的工件优先选择余下加工时间最短的工件优先选择余下工序数最多的工件随机地挑选下一个工件FCFS(FirstComeFirstServed)规则EDD(EarliestDueDate)规则SPT(ShortestProcessingTime)规则SCR(SmallestCriticalRatio)规则MWKR(MostWorkRemaining)规则LWRK(LeastworkRemaining)规则MOPNR(MostOperationsRemaining)规则RANDOM规则规则解释浙江财经学院工商管理学院14常用的优先顺序规则先到先浙江财经学院工商管理学院15最先到的工作先处理大多数作业排序标准能达到平均水平对顾客来说是公平的对服务组织更重要如:餐厅先到先服务

FCFS,(FirstCome,FirstServedRule)浙江财经学院工商管理学院15最先到的工作先处理先到先浙江财经学院工商管理学院16优先处理完工时间最早的工作被一些企业广泛的应用如果完工时间很重要MRP系统完工时间使最大延迟最小，提高客户满意水平在许多排程标准上表现并不是太好最早交货时间

EDD（EarliestDueDateRule）浙江财经学院工商管理学院16优先处理完工时间最早的工浙江财经学院工商管理学院17最短作业时间

SPT（ShortestProcessingTimeRule）优先处理完工时间最短的工作可以使工作流最小化，或系统中要完成的工作数量最小化在单台机器或单个工作中心（n/1）情况下使用平均延迟、平均等待时间和平均完成时间上都能产生最优解。最大的缺陷是工作时间长的工作将被不断地推迟。浙江财经学院工商管理学院17最短作业时间

SPT（S浙江财经学院工商管理学院18最小临界值(关键比率规划)

SCR（SmallestCriticalRatio）临界值：距离完工期剩余时间与剩余工作时间之比值先处理临界值最小的工作可以缩短平均延迟时间，有效地跟踪记载工作进展和位置CR剩余时间剩余工作时间

完工期

-

今日之日期剩余工作时间==浙江财经学院工商管理学院18最小临界值(关键比率规划浙江财经学院工商管理学院19最长余下时间

MWKR(MostWorkRemaining)优先选择余下加工时间最长的工作浙江财经学院工商管理学院19最长余下时间

MWKR浙江财经学院工商管理学院20最短余下时间

LWRK(LeastworkRemaining)优先选择余下工作时间最短的工作浙江财经学院工商管理学院20最短余下时间

LWRK浙江财经学院工商管理学院21最多余下作业

MOPNR(MostOperationsRemaining)优先选择余下处理工序最多的工作浙江财经学院工商管理学院21最多余下作业

MOPNR浙江财经学院工商管理学院22随机规则（RANDOM）随机挑选下一个工作浙江财经学院工商管理学院22随机规则（RANDOM）浙江财经学院工商管理学院23作业排序方案的评价指标工件流程时间从工件可以开始加工(不一定是实际的开始时间)至完工的时间全部完工时间完成一组工作所需的全部时间延迟可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间完工的工件数占总工件数的百分比来表示在制品库存(WIP)度量标准可以用工件个数、其货币价值或可供应的周数来表示总库存计划入库量和现有库存量的总和为总库存量利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示浙江财经学院工商管理学院23作业排序方案的评价指标工浙江财经学院工商管理学院24作业排序方案的评价指标（续）浙江财经学院工商管理学院24作业排序方案的评价指标（浙江财经学院工商管理学院25作业排序目标满足交货日期提前期最短准备时间最短或者成本最小在制品库存最小机器或劳动力利用率最大这一条有争议，因为仅仅考虑保持机器或者劳动力处于繁忙状态可能不是在工序中进行管理的最有效的方法浙江财经学院工商管理学院25作业排序目标满足交货日期浙江财经学院工商管理学院26n/1排序问题例李生是A复印公司的主管，复印公司为其所在市区的某法律公司提供复印服务，在这周开始，5个客户提供了他们的订单。详细的排序数据如下：作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12所有的订单都要使用唯一的彩色复印机，李生必须决定5个订单的加工顺序，评价标准是流程时间最短。浙江财经学院工商管理学院26n/1排序问题例李生是A浙江财经学院工商管理学院27FCFS作业顺序加工时间交货日期流程时间延迟A350+3=30B463+4=77－6＝1C277+2=99－7＝2D699+6=1515－9＝6E1215+1=1616－2＝14总流程时间=3+7+9+15+16=50(天）平均流程时间=50/5=10(天）总延迟=0+1+2+6+14=23，平均延迟=23/5=4.6(天）浙江财经学院工商管理学院27FCFS作业顺序加工时间浙江财经学院工商管理学院28SPT作业顺序加工时间交货日期流程时间延迟总流程时间=平均流程时间=总延迟=，平均延迟=作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12E120+1=10C271+2=30A353+3=66-5=1B466+4=1010-6=4D6910+6=1616-9=71+3+6+10+16=36(天)36/5=7.2(天)1+4+7=12(天)12/5=2.4(天)浙江财经学院工商管理学院28SPT作业顺序加工时间交浙江财经学院工商管理学院29EDD作业顺序加工时间交货日期流程时间延迟总流程时间=平均流程时间=总延迟=，平均延迟=作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12E120+1=10A351+3=40B464+4=88-6=2C278+2=1010-7=3D6910+6=1616-9=71+4+8+10+16=39(天)39/5=7.8(天)2+3+7=12(天)12/5=2.4(天)浙江财经学院工商管理学院29EDD作业顺序加工时间交浙江财经学院工商管理学院30优先调度规则对比规划总完成时间(天)平均完成时间(天)平均延迟(天)FCFS50104.6SPT367.22.4EDD397.82.4从上面可看出，SPT规则比其他规则较好，事实上也是这样，用数学方法可以证明在n/1情况下使用其他衡量标准，如平均等待时间和平均完成时间，SPT都能产生最优解。这种简单的规则如此有用，以至于被称为“整个排序科学中最重要的概念”浙江财经学院工商管理学院30优先调度规则对比规划总完浙江财经学院工商管理学院31对在制品库存的理解n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态机壳加工次序开始工作加工时间结束工作流程时间在制品库存贡献E01111/16＝0.0625A13444/16＝0.25B44888/16＝0.5C82101010/16＝0.625D106161616/16＝1总数392.4375平均在制品库存＝39/16＝2.4375浙江财经学院工商管理学院31对在制品库存的理解n/1浙江财经学院工商管理学院32对总库存的理解n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态机壳加工次序加工时间结束时间预计顾客取货时间顾客实际取货时间提前延迟E11221A34551B48682C2107103D6169167总数3941212平均总库存＝41/16＝2.5625浙江财经学院工商管理学院32对总库存的理解n/1排序浙江财经学院工商管理学院33优先规则及其事例（学生练习）例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存浙江财经学院工商管理学院33优先规则及其事例（学生练浙江财经学院工商管理学院34发动机机壳的加工与取货信息发动机机壳所需标准加工时间(h)(包括机器调整)预计顾客取货时间(h)(从现在开始算起的所需时间)机壳1机壳2机壳3机壳4机壳586153121012201822一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间。请给出分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存浙江财经学院工商管理学院34发动机机壳的加工与取货信浙江财经学院工商管理学院35SPT规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数总数平均数平均在制品库存＝平均总库存＝机壳4机壳2机壳1机壳5机壳3浙江财经学院工商管理学院35SPT规则排序结果机壳加浙江财经学院工商管理学院36SPT规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存＝102/44＝2.32个平均总库存＝120/44=2.73个浙江财经学院工商管理学院36SPT规则排序结果机壳加浙江财经学院工商管理学院37EDD规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数总数平均数平均在制品库存＝平均总库存＝机壳1机壳2机壳4机壳3机壳5浙江财经学院工商管理学院37EDD规则排序结果机壳加浙江财经学院工商管理学院38EDD规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数230.67.2平均在制品库存＝115/44=2.61平均总库存＝118/44=2.68浙江财经学院工商管理学院38EDD规则排序结果机壳加浙江财经学院工商管理学院39流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致讨论所有工件在各台机器上的加工顺序都相同的情况浙江财经学院工商管理学院39流水作业排序问题流水作业浙江财经学院工商管理学院40最长流程时间最长流程时间又称加工周期是第一个工件在一台机器开始加工时算起，到最后一个工件在最后一台机器上完工时为至所经过的时间假定所有工件到达时间为零，则 最长流程时间=排在末位加工工件在车间的停留时间流水作业排序一个目标函数：最长流程时间最短浙江财经学院工商管理学院40最长流程时间最长流程时间浙江财经学院工商管理学院41最长流程时间设n个工件的加工顺序为S=(S1,S2,…,Sn)表示工件Si在机器Mk上的完工时间表示工件Si在机器Mk上的加工时间浙江财经学院工商管理学院41最长流程时间设n个工件的浙江财经学院工商管理学院42加工顺序矩阵i615243Pi1244213Pi2544576Pi3555857Pi4143234浙江财经学院工商管理学院42加工顺序矩阵i61524浙江财经学院工商管理学院43加工顺序矩阵图示解释

12345678910111213141516171819202122232425262728293031323334353637383940414243444546机器1机器2机器3机器4时间浙江财经学院工商管理学院43加工顺序矩阵图示解释浙江财经学院工商管理学院44n个作业两台机器排序问题(n/2)两个或者更多以上的作业必须在两台机器上以共同的工序进行加工评价标准：从第一个作业开始到最后一个作业结束的总流程时间最短，即全部完工时间最短－－Johnson方法（约翰逊方法）浙江财经学院工商管理学院44n个作业两台机器排序问题浙江财经学院工商管理学院45N项作业按相同顺序经过2台机器加工，使全部完工时间最小N项作业的双机排序（N/2）锯钻工作A工作B工作C工作(N=3)Johnson方法（约翰逊方法）浙江财经学院工商管理学院45N项作业按相同顺序经过2浙江财经学院工商管理学院46Johnson方法-N项作业的双机排序(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕浙江财经学院工商管理学院46Johnson方法-浙江财经学院工商管理学院47列出作业及加工时间全部安排完毕?Yes12YesNoNoJohnson法的步骤选择加工时间最短的作业哪台机器？先完成这一作业最后完成这一作业删除这一作业还有剩余作业吗？结束强制结束浙江财经学院工商管理学院47列出作业及加工时间全部安浙江财经学院工商管理学院48Johnson法–

例子作业工作1工作2Y11222Y245Y353Y41516Y5108(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕浙江财经学院工商管理学院48Johnson法–例浙江财经学院工商管理学院49Johnson法–

例子步骤1步骤2步骤3步骤4步骤5(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕作业工作1工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1浙江财经学院工商管理学院49Johnson法–例浙江财经学院工商管理学院50Johnson法例子的甘特图Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空闲，等待新任务Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空闲空闲Y4Y3Y2Y5Y1浙江财经学院工商管理学院50Johnson法例子的甘浙江财经学院工商管理学院51提问如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，应该如何排序？如果一项作业在两台机器上的作业时间相同，应该如何排序？浙江财经学院工商管理学院51提问如果第一台机器的某作浙江财经学院工商管理学院52Johnson法的补充说明如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，则第一台机器的这一作业安排在前面完成，而第二台机器的这项作业安排在后面完成如果一项作业在两台机器上的作业时间相同，这个项目可以被安排在两个作业时间的任一一个浙江财经学院工商管理学院52Johnson法的补充说浙江财经学院工商管理学院53Johnson法的优化（P303）第一台机器上的加工时间记为ai，第二台机器上的加工时间bi将所有工件ai≤bi按ai值不减的顺序排成一个序列A将所有工件ai＞bi按bi值不增的顺序排成一个序列B将A放在B之前，就构成了最优加工顺序浙江财经学院工商管理学院53Johnson法的优化（浙江财经学院工商管理学院54Johnson法的优化

ai≤bi按ai值不减的序列A：(4,12,15),(Y2,Y1,Y4)作业工作1工作2Y11222Y245Y353Y41516Y51084121538Y4Y3Y2Y5Y1ai＞bi按bi值不增的序列B：(8,3),(Y5,Y3)浙江财经学院工商管理学院54Johnson法的优化浙江财经学院工商管理学院55n个作业n台机器排序问题(n/n)当作业数和机器数相同时，能够同时开始所有作业作业排序问题不是哪个作业先开始，而是哪个作业指派到哪台机器上的安排使得总排序最佳浙江财经学院工商管理学院55n个作业n台机器排序问题浙江财经学院工商管理学院56n/n作业问题的分配方法AssignmentMethod分配方法是一种特殊的可将任务或工作分配给相应的资源的线性规划模型，是线性规划运输问题的一个特例。适用于有n个需求和n个供给的情况成本或时间达到最少目标特征一件工作(或一个人)仅分配给一台机器(或一个项目)浙江财经学院工商管理学院56n/n作业问题的分配方法浙江财经学院工商管理学院57n/n作业问题的分配方法每个分配问题用一张表，表中数字是与特定的分配相关的成本或时间。通过在增加或减少一适当的数字以找到各种分配的最小机会成本。浙江财经学院工商管理学院57n/n作业问题的分配方法浙江财经学院工商管理学院58分配方法的步骤1.将每行数字减去该行中最小数字，将每列减去该列中最小数字。2.画数量最小的水平线和垂直线以盖住表中的所有的零。若直线数等于表的行或列数，那么我们就找到了最优分配(见步骤4)；否则进入步骤3。3.从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上。再回到步骤2往下操作直到出现可能的最佳分配。4.最佳分配总在表中零位置出现。浙江财经学院工商管理学院58分配方法的步骤1.将每行浙江财经学院工商管理学院59分配方法示例

机器工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元将工作分配到机器上去浙江财经学院工商管理学院59分配方法示例机浙江财经学院工商管理学院60分配方法示例

机器工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元步骤1a：从各行数字中减去其中数字最小的数字机器工作ABCR-34S-66T-50658002325087浙江财经学院工商管理学院60分配方法示例机器AB浙江财经学院工商管理学院61分配方法示例机器工作ABCR-34580S-66023T-50250步骤1b：从各列数字中减去其中数字最小的数字机器工作ABCR-34S-66T-50050226030300浙江财经学院工商管理学院61分配方法示例机器A浙江财经学院工商管理学院62分配方法示例

机器工作ABCR-34560S-66003T-50230步骤2：画最小数目的直线盖住所有的0直线数=2<行(列)数3，故非最优答案浙江财经学院工商管理学院62分配方法示例机器ABC浙江财经学院工商管理学院63分配方法示例

机器工作ABCR-34560S-66003T-50230步骤3：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上

机器工作ABCR-340S-6600T-50034015回到步骤2，画线盖0由于直线数=3=行(列)数，故为最优答案浙江财经学院工商管理学院63分配方法示例机器ABC浙江财经学院工商管理学院64分配方法示例最佳分配总是在表中零位置出现将R-34分配给C，S-66分配给BT-50分配给A最小成本=6+10+9=25元问题：S-66能否分配给A？

机器工作ABCR-34340S-66005T-50010浙江财经学院工商管理学院64分配方法示例最佳分配总是浙江财经学院工商管理学院65n/m作业排序问题本课程不讲，有兴趣的同学自己看书浙江财经学院工商管理学院65n/m作业排序问题本课程浙江财经学院工商管理学院66相同零件、不同移动方式下的加工周期n个零件相同，在加工过程中采取不同的移动方式，会导致一批零件的加工周期不同有三种典型的移动方式顺序移动方式平行移动方式平行顺序移动方式浙江财经学院工商管理学院66相同零件、不同移动方式下浙江财经学院工商管理学院67不同移动方式下加工周期的计算顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院67不同移动方式下加工周期的浙江财经学院工商管理学院68不同移动方式下加工周期的计算平行移动M1M2M3M4T顺特点：浙江财经学院工商管理学院68不同移动方式下加工周期的浙江财经学院工商管理学院69不同移动方式下加工周期的计算平行顺序移动M1M2M3M4T平顺特点：浙江财经学院工商管理学院69不同移动方式下加工周期的浙江财经学院工商管理学院70平行顺序移动加工周期的推演0顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院70平行顺序移动加工周期的推浙江财经学院工商管理学院71平行顺序移动加工周期的推演1顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院71平行顺序移动加工周期的推浙江财经学院工商管理学院72平行顺序移动加工周期的推演2顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院72平行顺序移动加工周期的推浙江财经学院工商管理学院73平行顺序移动加工周期的推演3顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院73平行顺序移动加工周期的推浙江财经学院工商管理学院74平行顺序移动加工周期的推演4顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院74平行顺序移动加工周期的推浙江财经学院工商管理学院75平行顺序移动加工周期的推演5顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院75平行顺序移动加工周期的推浙江财经学院工商管理学院76平行顺序移动加工周期的推演6顺序移动M1M2M3M4T顺特点：浙江财经学院工商管理学院76平行顺序移动加工周期的推浙江财经学院工商管理学院77服务的作业排序规则预约系统–

美容服务预订系统–

饭店先到先服务–

熟食店、食堂紧急优先–

医院急救浙江财经学院工商管理学院77服务的作业排序规则预约系浙江财经学院工商管理学院78服务系统的作业排序特点客户的参与服务无法储存浙江财经学院工商管理学院78服务系统的作业排序特点客浙江财经学院工商管理学院79排队系统排队管理的权衡等待时间长短成本服务成本等待成本总成本浙江财经学院工商管理学院79排队系统排队管理的权衡等浙江财经学院工商管理学院80等待时间感知等待时间实际等待时间感知等待时间顾客满意度怎么还不来车一会儿就轮到我了浙江财经学院工商管理学院80等待时间感知等待时间感知浙江财经学院工商管理学院81影响顾客满意度不公平的等待和公平的等待食堂中插队不舒适的等待和舒适的等待站着与坐者等待没有解释的等待和解释的等待过程前的等待和过程中的等待麦当劳：排队点菜与等待食物忙碌中等待与空闲中等待看报纸、听音乐焦急等待与耐心等待手术室外面浙江财经学院工商管理学院81影响顾客满意度不公平的等浙江财经学院工商管理学院82影响顾客满意度独立等待和群体等待高价值服务等待和低价值服务等待时间对于顾客的重要程度进入服务系统前顾客的心态浙江财经学院工商管理学院82影响顾客满意度独立等待和浙江财经学院工商管理学院83投入-产出控制

（Input/Outputcontrol，I/O）在制品投入控制产出控制浙江财经学院工商管理学院83投入-产出控制

（Inp浙江财经学院工商管理学院84无限生产排成浙江财经学院工商管理学院84无限生产排成浙江财经学院工商管理学院85有限生产排成浙江财经学院工商管理学院85有限生产排成浙江财经学院工商管理学院86高级生产排程（AdvancedProductionSchedule，APS）浙江财经学院工商管理学院86高级生产排程（Advan浙江财经学院工商管理学院87应对瓶颈工序的策略浙江财经学院工商管理学院87应对瓶颈工序的策略88生产与运作管理浙江财经学院工商管理学院作业排序8CHAPTER1生产与运作管理作业排序CHAPTER浙江财经学院工商管理学院89生产运作管理模型输入待转化资源物料信息顾客输入转化资源设施员工顾客输入资源输出产品与服务改善计划与控制设计运作战略企业战略作业排序浙江财经学院工商管理学院2生产运作管理模型输入待转化浙江财经学院工商管理学院90本章主要内容作业排序的基本概念作业排序的表示方式流水作业排序问题单件作业排序问题服务排队系统设计中的心理因素浙江财经学院工商管理学院3本章主要内容作业排序的基本浙江财经学院工商管理学院91医院门诊病人治疗手术室大学排课教室工厂生产采购作业排序例子浙江财经学院工商管理学院4医院作业排序例子浙江财经学院工商管理学院92作业计划与排序作业排序(Sequencing)是确定加工对象的加工顺序作业计划(Scheduling)还要确定开始加工和完工的时间作业排序是作业计划的关键在实际中，这两个词经常被等同使用浙江财经学院工商管理学院5作业计划与排序作业排序(S浙江财经学院工商管理学院93作业排序的战略目的有效的排序可以提高设施的利用率，这意味着：有效的排序可以提高交货速度，这意味着：好的排序提供更低的成本更好的顾客服务更可靠的交货浙江财经学院工商管理学院6作业排序的战略目的有效的排浙江财经学院工商管理学院94前向排序与后向排序收到订单交货期订购原料作业1作业2作业3作业4订购原料作业1作业2作业3作业4前向排序后向排序请思考下列两种情况下适用哪种排序方式？按订单生产的企业为节省库存的费用浙江财经学院工商管理学院7前向排序与后向排序收到订单浙江财经学院工商管理学院95甘特图（Gantt

Chart）作业进度图表示一项工作的计划开始日期、计划完成日期以及现在的进度机器图（甘特负荷图）描述不同工作在每一台机器上的工作次序，可被用来管理生产进度浙江财经学院工商管理学院8甘特图（GanttCh浙江财经学院工商管理学院96作业进度甘特图工作11/1011/1111/1211/1311/1411/1511/1611/1711/1811/19ABC开始时间结束时间计划所用时间实际进度表示一项工作的计划开始日期、计划完成日期以及现在的进度浙江财经学院工商管理学院9作业进度甘特图工作11/1浙江财经学院工商管理学院97描述不同工作在每一台机器上的工作次序机器甘特图机器11/1111/1211/1311/1411/1511/1611/1711/18磨床抛光机开始时间结束时间计划所用时间实际进度非生产性时间ABCABC浙江财经学院工商管理学院10描述不同工作在每一台机器浙江财经学院工商管理学院98排序问题的分类主要是将不同工件安排到不同设备上，或安排不同的人做不同的工作劳动力作业排序生产作业排序主要是确定人员何时工作两种基本形式的作业排序浙江财经学院工商管理学院11排序问题的分类主要是将不浙江财经学院工商管理学院99制造业生产作业排序分类按机器数量分类单台机器的排序问题多台机器的排序问题单件作业排序问题

(Job-Shop)流水作业排序问题(Flow-Shop)按工件到达车间的情况不同静态排序问题动态排序问题工件陆续到达，要随时安排它们的加工顺序

排序时，所有工件都已到达，可一次性进行排序浙江财经学院工商管理学院12制造业生产作业排序分类按浙江财经学院工商管理学院100n个作业的单台机器排序问题(n/1)对于某一工作地，在给定的一段时间内，顺次决定下一个被加工的工件可能要考虑交付日期、在制品数量、全部完工时间等因素对象1对象2对象3对象n…工作地浙江财经学院工商管理学院13n个作业的单台机器排序问浙江财经学院工商管理学院101常用的优先顺序规则先到先服务优先选择完工期限最紧的工件优先选择加工时间最短的工件优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比优先选择余下加工时间最长的工件优先选择余下加工时间最短的工件优先选择余下工序数最多的工件随机地挑选下一个工件FCFS(FirstComeFirstServed)规则EDD(EarliestDueDate)规则SPT(ShortestProcessingTime)规则SCR(SmallestCriticalRatio)规则MWKR(MostWorkRemaining)规则LWRK(LeastworkRemaining)规则MOPNR(MostOperationsRemaining)规则RANDOM规则规则解释浙江财经学院工商管理学院14常用的优先顺序规则先到先浙江财经学院工商管理学院102最先到的工作先处理大多数作业排序标准能达到平均水平对顾客来说是公平的对服务组织更重要如:餐厅先到先服务

FCFS,(FirstCome,FirstServedRule)浙江财经学院工商管理学院15最先到的工作先处理先到先浙江财经学院工商管理学院103优先处理完工时间最早的工作被一些企业广泛的应用如果完工时间很重要MRP系统完工时间使最大延迟最小，提高客户满意水平在许多排程标准上表现并不是太好最早交货时间

EDD（EarliestDueDateRule）浙江财经学院工商管理学院16优先处理完工时间最早的工浙江财经学院工商管理学院104最短作业时间

SPT（ShortestProcessingTimeRule）优先处理完工时间最短的工作可以使工作流最小化，或系统中要完成的工作数量最小化在单台机器或单个工作中心（n/1）情况下使用平均延迟、平均等待时间和平均完成时间上都能产生最优解。最大的缺陷是工作时间长的工作将被不断地推迟。浙江财经学院工商管理学院17最短作业时间

SPT（S浙江财经学院工商管理学院105最小临界值(关键比率规划)

SCR（SmallestCriticalRatio）临界值：距离完工期剩余时间与剩余工作时间之比值先处理临界值最小的工作可以缩短平均延迟时间，有效地跟踪记载工作进展和位置CR剩余时间剩余工作时间

完工期

-

今日之日期剩余工作时间==浙江财经学院工商管理学院18最小临界值(关键比率规划浙江财经学院工商管理学院106最长余下时间

MWKR(MostWorkRemaining)优先选择余下加工时间最长的工作浙江财经学院工商管理学院19最长余下时间

MWKR浙江财经学院工商管理学院107最短余下时间

LWRK(LeastworkRemaining)优先选择余下工作时间最短的工作浙江财经学院工商管理学院20最短余下时间

LWRK浙江财经学院工商管理学院108最多余下作业

MOPNR(MostOperationsRemaining)优先选择余下处理工序最多的工作浙江财经学院工商管理学院21最多余下作业

MOPNR浙江财经学院工商管理学院109随机规则（RANDOM）随机挑选下一个工作浙江财经学院工商管理学院22随机规则（RANDOM）浙江财经学院工商管理学院110作业排序方案的评价指标工件流程时间从工件可以开始加工(不一定是实际的开始时间)至完工的时间全部完工时间完成一组工作所需的全部时间延迟可以用比预定完工时间延迟了的时间部分来表示，也可以用未按预定时间完工的工件数占总工件数的百分比来表示在制品库存(WIP)度量标准可以用工件个数、其货币价值或可供应的周数来表示总库存计划入库量和现有库存量的总和为总库存量利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示浙江财经学院工商管理学院23作业排序方案的评价指标工浙江财经学院工商管理学院111作业排序方案的评价指标（续）浙江财经学院工商管理学院24作业排序方案的评价指标（浙江财经学院工商管理学院112作业排序目标满足交货日期提前期最短准备时间最短或者成本最小在制品库存最小机器或劳动力利用率最大这一条有争议，因为仅仅考虑保持机器或者劳动力处于繁忙状态可能不是在工序中进行管理的最有效的方法浙江财经学院工商管理学院25作业排序目标满足交货日期浙江财经学院工商管理学院113n/1排序问题例李生是A复印公司的主管，复印公司为其所在市区的某法律公司提供复印服务，在这周开始，5个客户提供了他们的订单。详细的排序数据如下：作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12所有的订单都要使用唯一的彩色复印机，李生必须决定5个订单的加工顺序，评价标准是流程时间最短。浙江财经学院工商管理学院26n/1排序问题例李生是A浙江财经学院工商管理学院114FCFS作业顺序加工时间交货日期流程时间延迟A350+3=30B463+4=77－6＝1C277+2=99－7＝2D699+6=1515－9＝6E1215+1=1616－2＝14总流程时间=3+7+9+15+16=50(天）平均流程时间=50/5=10(天）总延迟=0+1+2+6+14=23，平均延迟=23/5=4.6(天）浙江财经学院工商管理学院27FCFS作业顺序加工时间浙江财经学院工商管理学院115SPT作业顺序加工时间交货日期流程时间延迟总流程时间=平均流程时间=总延迟=，平均延迟=作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12E120+1=10C271+2=30A353+3=66-5=1B466+4=1010-6=4D6910+6=1616-9=71+3+6+10+16=36(天)36/5=7.2(天)1+4+7=12(天)12/5=2.4(天)浙江财经学院工商管理学院28SPT作业顺序加工时间交浙江财经学院工商管理学院116EDD作业顺序加工时间交货日期流程时间延迟总流程时间=平均流程时间=总延迟=，平均延迟=作业（按到达顺序）加工时间（天）交货日期（从现在起天数）A35B46C27D69E12E120+1=10A351+3=40B464+4=88-6=2C278+2=1010-7=3D6910+6=1616-9=71+4+8+10+16=39(天)39/5=7.8(天)2+3+7=12(天)12/5=2.4(天)浙江财经学院工商管理学院29EDD作业顺序加工时间交浙江财经学院工商管理学院117优先调度规则对比规划总完成时间(天)平均完成时间(天)平均延迟(天)FCFS50104.6SPT367.22.4EDD397.82.4从上面可看出，SPT规则比其他规则较好，事实上也是这样，用数学方法可以证明在n/1情况下使用其他衡量标准，如平均等待时间和平均完成时间，SPT都能产生最优解。这种简单的规则如此有用，以至于被称为“整个排序科学中最重要的概念”浙江财经学院工商管理学院30优先调度规则对比规划总完浙江财经学院工商管理学院118对在制品库存的理解n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态机壳加工次序开始工作加工时间结束工作流程时间在制品库存贡献E01111/16＝0.0625A13444/16＝0.25B44888/16＝0.5C82101010/16＝0.625D106161616/16＝1总数392.4375平均在制品库存＝39/16＝2.4375浙江财经学院工商管理学院31对在制品库存的理解n/1浙江财经学院工商管理学院119对总库存的理解n/1排序第一件工件开始生产前所有工件已经达到，处于等待状态机壳加工次序加工时间结束时间预计顾客取货时间顾客实际取货时间提前延迟E11221A34551B48682C2107103D6169167总数3941212平均总库存＝41/16＝2.5625浙江财经学院工商管理学院32对总库存的理解n/1排序浙江财经学院工商管理学院120优先规则及其事例（学生练习）例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存浙江财经学院工商管理学院33优先规则及其事例（学生练浙江财经学院工商管理学院121发动机机壳的加工与取货信息发动机机壳所需标准加工时间(h)(包括机器调整)预计顾客取货时间(h)(从现在开始算起的所需时间)机壳1机壳2机壳3机壳4机壳586153121012201822一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间。请给出分别使用SPT和EDD规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存浙江财经学院工商管理学院34发动机机壳的加工与取货信浙江财经学院工商管理学院122SPT规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数总数平均数平均在制品库存＝平均总库存＝机壳4机壳2机壳1机壳5机壳3浙江财经学院工商管理学院35SPT规则排序结果机壳加浙江财经学院工商管理学院123SPT规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存＝102/44＝2.32个平均总库存＝120/44=2.73个浙江财经学院工商管理学院36SPT规则排序结果机壳加浙江财经学院工商管理学院124EDD规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数总数平均数平均在制品库存＝平均总库存＝机壳1机壳2机壳4机壳3机壳5浙江财经学院工商管理学院37EDD规则排序结果机壳加浙江财经学院工商管理学院125EDD规则排序结果机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数230.67.2平均在制品库存＝115/44=2.61平均总库存＝118/44=2.68浙江财经学院工商管理学院38EDD规则排序结果机壳加浙江财经学院工商管理学院126流水作业排序问题流水作业排序问题的基本特征是每个工件的加工路线都一致讨论所有工件在各台机器上的加工顺序都相同的情况浙江财经学院工商管理学院39流水作业排序问题流水作业浙江财经学院工商管理学院127最长流程时间最长流程时间又称加工周期是第一个工件在一台机器开始加工时算起，到最后一个工件在最后一台机器上完工时为至所经过的时间假定所有工件到达时间为零，则 最长流程时间=排在末位加工工件在车间的停留时间流水作业排序一个目标函数：最长流程时间最短浙江财经学院工商管理学院40最长流程时间最长流程时间浙江财经学院工商管理学院128最长流程时间设n个工件的加工顺序为S=(S1,S2,…,Sn)表示工件Si在机器Mk上的完工时间表示工件Si在机器Mk上的加工时间浙江财经学院工商管理学院41最长流程时间设n个工件的浙江财经学院工商管理学院129加工顺序矩阵i615243Pi1244213Pi2544576Pi3555857Pi4143234浙江财经学院工商管理学院42加工顺序矩阵i61524浙江财经学院工商管理学院130加工顺序矩阵图示解释

12345678910111213141516171819202122232425262728293031323334353637383940414243444546机器1机器2机器3机器4时间浙江财经学院工商管理学院43加工顺序矩阵图示解释浙江财经学院工商管理学院131n个作业两台机器排序问题(n/2)两个或者更多以上的作业必须在两台机器上以共同的工序进行加工评价标准：从第一个作业开始到最后一个作业结束的总流程时间最短，即全部完工时间最短－－Johnson方法（约翰逊方法）浙江财经学院工商管理学院44n个作业两台机器排序问题浙江财经学院工商管理学院132N项作业按相同顺序经过2台机器加工，使全部完工时间最小N项作业的双机排序（N/2）锯钻工作A工作B工作C工作(N=3)Johnson方法（约翰逊方法）浙江财经学院工商管理学院45N项作业按相同顺序经过2浙江财经学院工商管理学院133Johnson方法-N项作业的双机排序(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕浙江财经学院工商管理学院46Johnson方法-浙江财经学院工商管理学院134列出作业及加工时间全部安排完毕?Yes12YesNoNoJohnson法的步骤选择加工时间最短的作业哪台机器？先完成这一作业最后完成这一作业删除这一作业还有剩余作业吗？结束强制结束浙江财经学院工商管理学院47列出作业及加工时间全部安浙江财经学院工商管理学院135Johnson法–

例子作业工作1工作2Y11222Y245Y353Y41516Y5108(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕浙江财经学院工商管理学院48Johnson法–例浙江财经学院工商管理学院136Johnson法–

例子步骤1步骤2步骤3步骤4步骤5(1)列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业(4)对剩余作业重复步骤(2)和(3)，直到所有作业排序完毕作业工作1工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1浙江财经学院工商管理学院49Johnson法–例浙江财经学院工商管理学院137Johnson法例子的甘特图Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空闲，等待新任务Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空闲空闲Y4Y3Y2Y5Y1浙江财经学院工商管理学院50Johnson法例子的甘浙江财经学院工商管理学院138提问如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，应该如何排序？如果一项作业在两台机器上的作业时间相同，应该如何排序？浙江财经学院工商管理学院51提问如果第一台机器的某作浙江财经学院工商管理学院139Johnson法的补充说明如果第一台机器的某作业的所用时间同第二台机器的另一作业的时间相同，则第一台机器的这一作业安排在前面完成，而第二台机器的这项作业安排在后面完成如果一项作业在两台机器上的作业时间相同，这个项目可以被安排在两个作业时间的任一一个浙江财经学院工商管理学院52Johnson法的补充说浙江财经学院工商管理学院140Johnson法的优化（P303）第一台机器上的加工时间记为ai，第二台机器上的加工时间bi将所有工件ai≤bi按ai值不减的顺序排成一个序列A将所有工件ai＞bi按bi值不增的顺序排成一个序列B将A放在B之前，就构成了最优加工顺序浙江财经学院工商管理学院53Johnson法的优化（浙江财经学院工商管理学院141Johnson法的优化

ai≤bi按ai值不减的序列A：(4,12,15),(Y2,Y1,Y4)作业工作1工作2Y11222Y245Y353Y41516Y51084121538Y4Y3Y2Y5Y1ai＞bi按bi值不增的序列B：(8,3),(Y5,Y3)浙江财经学院工商管理学院54Johnson法的优化浙江财经学院工商管理学院142n个作业n台机器排序问题(n/n)当作业数和机器数相同时，能够同时开始所有作业作业排序问题不是哪个作业先开始，而是哪个作业指派到哪台机器上的安排使得总排序最佳浙江财经学院工商管理学院55n个作业n台机器排序问题浙江财经学院工商管理学院143n/n作业问题的分配方法AssignmentMethod分配方法是一种特殊的可将任务或工作分配给相应的资源的线性规划模型，是线性规划运输问题的一个特例。适用于有n个需求和n个供给的情况成本或时间达到最少目标特征一件工作(或一个人)仅分配给一台机器(或一个项目)浙江财经学院工商管理学院56n/n作业问题的分配方法浙江财经学院工商管理学院144n/n作业问题的分配方法每个分配问题用一张表，表中数字是与特定的分配相关的成本或时间。通过在增加或减少一适当的数字以找到各种分配的最小机会成本。浙江财经学院工商管理学院57n/n作业问题的分配方法浙江财经学院工商管理学院145分配方法的步骤1.将每行数字减去该行中最小数字，将每列减去该列中最小数字。2.画数量最小的水平线和垂直线以盖住表中的所有的零。若直线数等于表的行或列数，那么我们就找到了最优分配(见步骤4)；否则进入步骤3。3.从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上。再回到步骤2往下操作直到出现可能的最佳分配。4.最佳分配总在表中零位置出现。浙江财经学院工商管理学院58分配方法的步骤1.将每行浙江财经学院工商管理学院146分配方法示例

机器工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元将工作分配到机器上去浙江财经学院工商管理学院59分配方法示例机浙江财经学院工商管理学院147分配方法示例

机器工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元步骤1a：从各行数字中减去其中数字最小的数字机器工作ABCR-34S-66T-50658002325087浙江财经学院工商管理学院60分配方法示例机器AB浙江财经学院工商管理学院148分配方法示例机器工作ABCR-34580S-66023T-50250步骤1b：从