1、作业排序作业排序8C H A P T E R输入待转化资源输入待转化资源物料物料信息信息顾客顾客输入转化资源输入转化资源设施设施 员工员工顾客顾客输入资源输入资源输出输出产品与服务产品与服务改善改善计划与计划与控制控制设计设计运作战略运作战略企业战略企业战略作业排序作业排序更低的成本更低的成本更好的顾客服务更好的顾客服务更可靠的交货更可靠的交货收到收到订单订单交货期交货期订购订购原料原料作业作业1作业作业2作业作业3作业作业4订购订购原料原料作业作业1作业作业2作业作业3作业作业4前向排序前向排序后向排序后向排序请思考下列两种情况下适用哪种排序方式？请思考下列两种情况下适用哪种排序方式？按订单
2、生产的企业按订单生产的企业为节省库存的费用为节省库存的费用工作工作11/10 11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18 11/19ABC开始时间开始时间结束时间结束时间计划所用时间计划所用时间实际进度实际进度表示一项工作的计划开始日期、计划完成日期以及现在表示一项工作的计划开始日期、计划完成日期以及现在的进度的进度机器机器11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18磨床磨床抛光机抛光机开始时间开始时间结束时间结束时间计划所用时间计划所用时间实际进度实际进度非生产性时间非生产性时间ABCABC
3、劳动力作业排序劳动力作业排序生产作业排序生产作业排序主要是确定人员何时工作主要是确定人员何时工作n两种基本形式的作业排序两种基本形式的作业排序按机器数按机器数量分类量分类单台机器的单台机器的排序问题排序问题多台机器的多台机器的排序问题排序问题单件作业排序问题单件作业排序问题(Job-Shop)流水作业排序问题流水作业排序问题(Flow-Shop)按工件到达车按工件到达车间的情况不同间的情况不同静态排序问题静态排序问题动态排序问题动态排序问题工件陆续到达，要随时安排它们的加工顺序工件陆续到达，要随时安排它们的加工顺序排序时，所有工件都已到达，可一次性进行排序排序时，所有工件都已到达，可一次性进行
4、排序对象对象1对象对象2对象对象3对象对象n工作地工作地FCFS (First Come First Served)规则规则EDD (Earliest Due Date)规则规则SPT (Shortest Processing Time)规则规则SCR (Smallest Critical Ratio)规则规则MWKR (Most Work Remaining)规则规则LWRK (Least work Remaining)规则规则MOPNR (Most Operations Remaining)规规则则 RANDOM规则规则 规则规则解释解释CR剩余时间剩余时间剩余工作时间剩余工作时间 完工期
5、完工期 - 今日之日期今日之日期剩余工作时间剩余工作时间=工作数量流程时间平均完工时间流程时间处理时间时间利用率 处理时间流程时间在制品）系统中的平均工作数 (工作数量延迟时间平均延迟 作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12所有的订单都要使用唯一的彩色复印机，李生必须决定所有的订单都要使用唯一的彩色复印机，李生必须决定5个订单的加工个订单的加工顺序，评价标准是流程时间最短。顺序，评价标准是流程时间最短。作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟A350+3=30
6、B463+4=7761C277+2=9972D699+6=151596E1215+1=1616214总流程时间总流程时间=3+7+9+15+16=50(天）天）平均流程时间平均流程时间=50/5=10(天）天）总延迟总延迟=0+1+2+6+14=23，平均延迟，平均延迟=23/5=4.6(天）天）作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12E1
7、20+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(天天)作业顺序作业顺序加工时间加工时间交货日期交货日期流程时间流程时间延迟延迟总流程时间总流程时间=平均流程时间平均流程时间=总延迟总延迟=，平均延迟，平均延迟=作业（按到达顺序）作业（按到达顺序）加工时间（天）加工时间（天）交货日期（从现在起天数）交货日期（从现在起天数）A35B46C27D69E12E120+1=10A351+3=40B464+4=88-6=2C278+
8、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(天天)规划规划总完成时间总完成时间(天天)平均完成时间平均完成时间(天天)平均延迟平均延迟(天天)FCFS50104.6SPT367.22.4EDD397.82.4n从上面可看出，从上面可看出，SPT规则比其他规则较好，规则比其他规则较好，n事实上也是这样，用数学方法可以证明在事实上也是这样，用数学方法可以证明在n/1情况下使用其他衡量标准，情况下使用其他衡量标准，如平均等待时间和平均完成时间，如平均等待时间和平均完成时间，SPT都能产生最
9、优解。都能产生最优解。n这种简单的规则如此有用，以至于被称为这种简单的规则如此有用，以至于被称为“整个排序科学中最重要的概整个排序科学中最重要的概念念”机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间在制品库存贡献在制品库存贡献E01111/16 0.0625A13444/160.25B44888/160.5C82101010/160.625D106161616/161总数总数392.4375平均在制品库存平均在制品库存39/162.4375机壳加机壳加工次序工次序加工时间加工时间 结束时间结束时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取
10、货时间取货时间提前延迟提前延迟E11221A34551B48682C2107103D6169167总数总数3941212平均总库存平均总库存41/162.5625发动机机壳发动机机壳所需标准加工时间所需标准加工时间(h)(包括机器调整包括机器调整)预计顾客取货时间预计顾客取货时间(h)(从现在开始算起的所需从现在开始算起的所需时间时间)机壳机壳1机壳机壳2机壳机壳3机壳机壳4机壳机壳586153121012201822一个加工车间负责加工发动机机壳，现在共有一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只个机壳等待加工。只有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算
11、有一名技工在岗做此项工作。现各个机壳的标准加工时间已经被估算出来，顾客也已经明确提出了他们所希望的完工时间。出来，顾客也已经明确提出了他们所希望的完工时间。请给出分别使用请给出分别使用SPT和和EDD规则进行排序，并计算这两个方案的规则进行排序，并计算这两个方案的平均提前时间、延迟时间、在制品库存和总库存平均提前时间、延迟时间、在制品库存和总库存机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均
12、总库存平均总库存机壳机壳4机壳机壳2机壳机壳1机壳机壳5机壳机壳3机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳40333181815机壳机壳2369912123机壳机壳198171710177机壳机壳51712292922297机壳机壳329154444204424总数总数1021201838平均数平均数20.43.67.6平均在制品库存平均在制品库存102/442.32个个 平均总库存平均总库存120/44=2.73个个机壳加机壳加
13、工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数总数总数平均数平均数平均在制品库存平均在制品库存 平均总库存平均总库存机壳机壳1机壳机壳2机壳机壳4机壳机壳3机壳机壳5机壳加机壳加工次序工次序开始工作开始工作 加工时间加工时间 结束工作结束工作 流程时间流程时间预计顾客预计顾客取货时间取货时间顾客实际顾客实际取货时间取货时间提前提前小时数小时数拖延拖延小时数小时数机壳机壳1088810102机壳机壳286141412142机壳机壳4143171718181机
14、壳机壳317153232203212机壳机壳532124444224422总数总数115118336平均数平均数230.67.2平均在制品库存平均在制品库存115/44=2.61 平均总库存平均总库存118/44=2.68iksC1111iiissspCCksskskksiiiipCCC)()1(1,max表示工件表示工件Si在机器在机器Mk上的完工时间上的完工时间ksip表示工件表示工件Si在机器在机器Mk上的加工时间上的加工时间i615243Pi1244213Pi2544576Pi3555857Pi4143234 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
15、 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46机器机器1机器机器2机器机器3机器机器4时间时间锯锯钻钻工作工作 A工作工作 B工作工作 C工作工作 (N = 3)列出作业及加工时间列出作业及加工时间全部安排全部安排完毕完毕?Yes12YesNoNo选择加工时间选择加工时间最短的作业最短的作业哪台机器？哪台机器？先完成这一作业先完成这一作业最后完成这一作业最后完成这一作业删除这一作业删除这一作业还有剩余还有剩余作业吗？作业吗？结束结束强制结束强制结束作业作业工作工
16、作1工作工作2Y11222Y245Y353Y41516Y5108(1)列出每个作业在两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成业；如果来自第二台机器，那么这个作业就放在最后完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有作业排序完毕，直到所有作业排序完毕步骤步骤 1步骤步骤 2步骤步骤 3步骤步骤 4步骤步骤 5(1)列出每个作业在
17、两台机器上的加工时间列出每个作业在两台机器上的加工时间(2)选择最短的加工时间。如果最短的加工时间来自第一台机器，那选择最短的加工时间。如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成完成(3)删除已排序作业删除已排序作业(4)对剩余作业重复步骤对剩余作业重复步骤(2)和和(3)，直到所有作业排序完毕，直到所有作业排序完毕作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1工序1工序1工序2工序24
18、5450 05 510101515202025253030353540405050555560606565Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空闲，等待新任务空闲，等待新任务Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空闲空闲空闲空闲Y4Y3Y2Y5Y1作业作业工作工作1工作工作2Y11222Y245Y353Y41516Y51084121538Y4Y3Y2Y5Y1nai bi按按bi值不增的序列值不增的序列B：(8,3),(Y5,Y3)分配方法是一种特殊的可将任务或工作分分配方法是一种特殊的可将任务或工作分配给相应的资源的线性规划模型，是线性规划配给相应的资源的线
19、性规划模型，是线性规划运输问题的一个特例。运输问题的一个特例。适用于有适用于有n个需求和个需求和n个供给的情况个供给的情况成本成本或或时间时间达到最少达到最少目标目标特征特征一件工作一件工作(或一个人或一个人)仅分配给一台机器仅分配给一台机器(或或一个项目一个项目)每个分配问题用一张表，表中数字是与每个分配问题用一张表，表中数字是与特定的分配相关的成本或时间。特定的分配相关的成本或时间。通过在增加或减少一适当的数字以找到通过在增加或减少一适当的数字以找到各种分配的最小机会成本。各种分配的最小机会成本。1.1.将每行数字减去该行中最小数字，将每列减去该将每行数字减去该行中最小数字，将每列减去该列
20、中最小数字。列中最小数字。2.2.画数量最小的水平线和垂直线以盖住表中的所有画数量最小的水平线和垂直线以盖住表中的所有的零。若的零。若直线数等于表的行或列数直线数等于表的行或列数，那么我们就，那么我们就找到了最优分配找到了最优分配( (见步骤见步骤4)4)；否则进入步骤；否则进入步骤3 3。3.3.从未被直线盖住的所有数中减去最小的数，并将从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上。再回到此最小数加到所有两两相交之处的数上。再回到步骤步骤2 2往下操作直到出现可能的最佳分配。往下操作直到出现可能的最佳分配。4.4.最佳分配总在表中零位置出现。最佳分配总在表中零
21、位置出现。 机器机器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元将工作分配到机器上去将工作分配到机器上去机器机器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元步骤步骤1a1a：从各行数字中减去其中数字最小的数字：从各行数字中减去其中数字最小的数字机器机器工作工作ABCR-34S-66T-50658002325087机器机器工作工作ABCR-34580S-66023T-50250步骤步骤1b1b：从各列数字中减去其中数字最小的数字：从各列数字中减去其中数字最小的数字机器机器工作工作ABCR-34S-66T-500502
22、26030300机器机器工作工作ABCR-34560S-66003T-50230步骤步骤2 2：画最小数目的直线盖住所有的：画最小数目的直线盖住所有的0 0直线数直线数=2=2行行( (列列) )数数3 3，故非最优答案，故非最优答案机器机器工作工作ABCR-34560S-66003T-50230步骤步骤3：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两：从未被直线盖住的所有数中减去最小的数，并将此最小数加到所有两两相交之处的数上两相交之处的数上 机器机器工作工作ABCR-340S-6600T-50034015回到步骤回到步骤2 2，画线盖，画线盖0 0由于直线数由于直线数=3=
23、3=行行( (列列) )数，数，故为最优答案故为最优答案最佳分配总是在表中零位置出现最佳分配总是在表中零位置出现将将R-34R-34分配给分配给C C，S-66S-66分配给分配给B B T-50 T-50分配给分配给A A最小成本最小成本=6+10+9=25=6+10+9=25元元问题：问题：S-66S-66能否分配给能否分配给A A？ 机器机器工作工作ABCR-34340S-66005T-50010M1M2M3M4T顺顺miitnT1顺特点：特点：M1M2M3M4T顺顺LmiitntT) 1(1平特点：特点：M1M2M3M4T平顺平顺),min() 1(1111jmjjmiittntnT平顺特点：特点：M1M2M3M4T顺顺miitnT1顺特点：特点：M1M2M3M4T顺顺特点：特点：M1M2M3M4T顺顺特点：特点：M1M2M3M4T顺顺特点：特点：M1M2M3M4T顺顺特点：特点：M1M2M3M4T顺顺特点：特点：M1M2M3M4T顺顺特点：特点：),min() 1(1111jmjjmiittntnT平顺排队管理的权衡排队管理的权衡等待时间等待时间长长短短成成本本服务成本服务成本等待成本等待成本总成本总成本感知等待时间感知等待时间顾客满意度顾客满意度怎么还怎么还不来车不来车一会儿就轮一会儿就轮到我了到我了在制品在制品投入控制投入控制产出控制产出控制
