《作业排序》PPT课件.ppt

《《作业排序》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《作业排序》PPT课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章第十一章 作业排序作业排序本章主要介绍制造业的作业排序问本章主要介绍制造业的作业排序问题。题。2022/10/261生生产产与与运运作作管管理理一一、作业排序的概念和作业排序的概念和类类型型1、概念、概念w对一定期间内分配给生产单位的作业任务，对一定期间内分配给生产单位的作业任务，根据产品根据产品(零件零件)的工艺路线和设备负荷可的工艺路线和设备负荷可能性，确定各个生产单位作业任务的先后能性，确定各个生产单位作业任务的先后顺序。顺序。w作业排序问题通常表述为作业排序问题通常表述为“n项作业任务项作业任务在在m个生产单位的排序个生产单位的排序的问题的问题”。2022/10/262生生产产

2、与与运运作作管管理理一一、作业排序的概念和作业排序的概念和类类型型2、作业排序的类型：、作业排序的类型：流水型流水型mn排序问题排序问题 指指n项任务在项任务在m台设台设备上加工，所有任务的工艺顺序相同，有备上加工，所有任务的工艺顺序相同，有n!个排序方案。个排序方案。非流水型非流水型mn排序问题排序问题 指指n项任务在项任务在m台台设备上加工，所有任务的工艺顺序不同，设备上加工，所有任务的工艺顺序不同，有有(n!)m个排序方案。个排序方案。2022/10/263生生产产与与运运作作管管理理一一、作业排序的概念和作业排序的概念和类类型型w作业排序的表示方法为作业排序的表示方法为 生产单位数生产

3、单位数作业任务数作业任务数/排序问题类型排序问题类型/评价尺度评价尺度(优化目标优化目标)w如如m n/FLW/Fmax表示表示m个生产单位完成个生产单位完成n项作业任务、流水型排序问题和以最大项作业任务、流水型排序问题和以最大流程时间作为评价尺度。流程时间作为评价尺度。2022/10/264生生产产与与运运作作管管理理二、作业排序的评价尺度二、作业排序的评价尺度w最大流程时间最大流程时间w平均流程时间平均流程时间w最大延期量最大延期量w平均延期量平均延期量w在制品占用量在制品占用量w总调整时间总调整时间2022/10/265生生产产与与运运作作管管理理计算公式计算公式w设设设设n n为作业任

4、务数，为作业任务数，为作业任务数，为作业任务数，mm为机床数，为机床数，为机床数，为机床数，J Ji i为第为第为第为第i i项作业项作业项作业项作业任务，任务，任务，任务，O Oij ij为第为第为第为第i i项作业任务的和项作业任务的和项作业任务的和项作业任务的和j j工序，工序，工序，工序，t tij ij为第为第为第为第i i项项项项作业任务在第作业任务在第作业任务在第作业任务在第j j台机床上的作业时间，台机床上的作业时间，台机床上的作业时间，台机床上的作业时间，r ri i为任务为任务为任务为任务J Ji i可以开始加工的时刻，可以开始加工的时刻，可以开始加工的时刻，可以开始加工的

5、时刻，d di i为为为为J Ji i的要求完成时刻，的要求完成时刻，的要求完成时刻，的要求完成时刻，w wij ij为为为为O Oij ij在进行加工前的等候时间。如果没有等在进行加工前的等候时间。如果没有等在进行加工前的等候时间。如果没有等在进行加工前的等候时间。如果没有等候，候，候，候，w wij ij=0=0。w第第第第i i项任务的完成时刻项任务的完成时刻项任务的完成时刻项任务的完成时刻(c ci i)为为为为 c ci i=r ri i+t ti1 i1+w wi1i1+t ti2i2+w wi2i2+t timim+w wimim2022/10/266生生产产与与运运作作管管理理

6、计算公式计算公式(续续)w令令令令t ti i为作业任务为作业任务为作业任务为作业任务i i的总作业时间，则：的总作业时间，则：的总作业时间，则：的总作业时间，则：w令令令令w wi i为作业任务为作业任务为作业任务为作业任务i i的总等候时间，则：的总等候时间，则：的总等候时间，则：的总等候时间，则：w则则则则 c ci i=r ri i+t ti i+w wi i2022/10/267生生产产与与运运作作管管理理计算公式计算公式(续续)w第第i项作业任务在机床组的流程时间为：项作业任务在机床组的流程时间为：Fi=ci-ri=ti+wiw如果作业任务如果作业任务i的完成时刻的完成时刻ci已超

7、过要求完已超过要求完成时刻成时刻di，则形成交货延期，延期量则形成交货延期，延期量Di为：为：Di=ci-di=Fi+ri-diw如果如果ci未超过未超过di，则延期量，则延期量Di为为0。2022/10/268生生产产与与运运作作管管理理排序问题解法的约定排序问题解法的约定一个工件不能同时在不同的设备上加工；一个工件不能同时在不同的设备上加工；一个工件不能同时在不同的设备上加工；一个工件不能同时在不同的设备上加工；每道工序只在一台设备上完成，每台设备只完每道工序只在一台设备上完成，每台设备只完每道工序只在一台设备上完成，每台设备只完每道工序只在一台设备上完成，每台设备只完成一道工序；成一道工

8、序；成一道工序；成一道工序；每台设备同时只能加工一个工件；每台设备同时只能加工一个工件；每台设备同时只能加工一个工件；每台设备同时只能加工一个工件；工件在加工过程中采取平行移动方式；工件在加工过程中采取平行移动方式；工件在加工过程中采取平行移动方式；工件在加工过程中采取平行移动方式；工件数工件数工件数工件数(n n)、设备数设备数设备数设备数(mm)与加工时间均已知，允与加工时间均已知，允与加工时间均已知，允与加工时间均已知，允许工件在工序之间等待，允许设备在工件未到许工件在工序之间等待，允许设备在工件未到许工件在工序之间等待，允许设备在工件未到许工件在工序之间等待，允许设备在工件未到达时闲置

9、。达时闲置。达时闲置。达时闲置。2022/10/269生生产产与与运运作作管管理理三、单台机床作业排序方法三、单台机床作业排序方法w11n n流水排序型问题的优先规则：流水排序型问题的优先规则：流水排序型问题的优先规则：流水排序型问题的优先规则：w先到先服务先到先服务先到先服务先到先服务(FCFS)FCFS)w最短作业时间最短作业时间最短作业时间最短作业时间(SPT)SPT)w最短交货延期量最短交货延期量最短交货延期量最短交货延期量(EDD)EDD)wSPTSPTSPTSPT与与与与EDDEDDEDDEDD结结结结合原合原合原合原则则则则w最小松弛时间最小松弛时间最小松弛时间最小松弛时间(SS

10、TSST)w后到先服务后到先服务后到先服务后到先服务(LCFS)LCFS)w按期完成作业项目最多的原则按期完成作业项目最多的原则按期完成作业项目最多的原则按期完成作业项目最多的原则按期完成作按期完成作业项业项目最多的原目最多的原则则：即先按交货期优先原则逐项安即先按交货期优先原则逐项安排作业顺序，并依次计算每项排作业顺序，并依次计算每项任务是否拖期，如果遇到某项任务是否拖期，如果遇到某项任务拖期，则将其移至最后加任务拖期，则将其移至最后加工；之后，若又有任务拖期，工；之后，若又有任务拖期，则又将其移至最后加工。则又将其移至最后加工。2022/10/2610生生产产与与运运作作管管理理三、单台机

11、床作业排序方法三、单台机床作业排序方法w例：例：例：例：下表是在某工作中心等待加工的下表是在某工作中心等待加工的下表是在某工作中心等待加工的下表是在某工作中心等待加工的6 6项作业的项作业的项作业的项作业的加工时间（包含换产时间）与预定日期，假设加工时间（包含换产时间）与预定日期，假设加工时间（包含换产时间）与预定日期，假设加工时间（包含换产时间）与预定日期，假设工作的到达顺序与表中顺序相符工作的到达顺序与表中顺序相符工作的到达顺序与表中顺序相符工作的到达顺序与表中顺序相符 。根据以下规根据以下规根据以下规根据以下规则来决定其作业顺序：则来决定其作业顺序：则来决定其作业顺序：则来决定其作业顺序

12、：FCFSFCFSSPTSPTEDDEDDSSTSST并对它们分别进行评价。并对它们分别进行评价。并对它们分别进行评价。并对它们分别进行评价。作作作作 业业业业加工时间（天）加工时间（天）加工时间（天）加工时间（天）预定日期（天）预定日期（天）预定日期（天）预定日期（天）A AB BC CD DE EF F2 28 84 410105 512127 716164 41717151518182022/10/2611生生产产与与运运作作管管理理按按FCFS规则排序规则排序w排序的结果是排序的结果是A-B-C-D-E-F。顺序顺序顺序顺序加工时间加工时间加工时间加工时间流程时间流程时间流程时间流程时

13、间预定交货期预定交货期预定交货期预定交货期延期天数延期天数延期天数延期天数(如果如果如果如果为负则赋值为负则赋值为负则赋值为负则赋值0)0)A AB BC CD DE EF F 2 28 84 410105 512122 2101014142424292941417 716164 41717151518180 00 010107 714142323合计合计合计合计41411201205454平均平均平均平均120/41=2.93120/41=2.93120/6=20120/6=2054/6=954/6=92022/10/2612生生产产与与运运作作管管理理按按SPT规则规则w作业顺序是作业顺序

14、是A-C-E-B-D-F顺序顺序顺序顺序加工时间加工时间加工时间加工时间流程时间流程时间流程时间流程时间预定交货期预定交货期预定交货期预定交货期延期天数延期天数延期天数延期天数(如果如果如果如果为负则赋值为负则赋值为负则赋值为负则赋值0)0)A AC CE EB BD DF F 2 24 45 58 8101012122 26 611111919292941417 74 415151616171718180 02 20 03 312122323合计合计合计合计41411081084040平均平均平均平均108/41=2.63108/41=2.63108/6=18108/6=1840/6=6.6

15、740/6=6.672022/10/2613生生产产与与运运作作管管理理按按EDD规则规则w作业顺序是作业顺序是C-A-E-B-D-F顺序顺序顺序顺序加工时间加工时间加工时间加工时间流程时间流程时间流程时间流程时间预定交货预定交货预定交货预定交货期期期期延期天数延期天数延期天数延期天数(如果如果如果如果为负则赋值为负则赋值为负则赋值为负则赋值0)0)C CA AE EB BD DF F4 42 25 58 8101012124 46 611111919292941414 47 715151616171718180 00 00 03 312122323合计合计合计合计41411101103838

16、平均平均平均平均110/41=2.68110/41=2.68110/6=18.33 110/6=18.33 38/6=6.3338/6=6.332022/10/2614生生产产与与运运作作管管理理按按SST规则规则w w松弛时间松弛时间松弛时间松弛时间=预定日期预定日期预定日期预定日期-加工时间，按松弛时间从小到大排列，加工时间，按松弛时间从小到大排列，加工时间，按松弛时间从小到大排列，加工时间，按松弛时间从小到大排列，可得顺序：可得顺序：可得顺序：可得顺序：C-A-F-D-B-EC-A-F-D-B-E顺序顺序顺序顺序松弛时间松弛时间松弛时间松弛时间加工时间加工时间加工时间加工时间流程时间流程

17、时间流程时间流程时间预定交货期预定交货期预定交货期预定交货期延期天数延期天数延期天数延期天数(如果如果如果如果为负则赋值为负则赋值为负则赋值为负则赋值0)0)C CA AE EB BD DF F0 05 56 67 78 810104 42 2121210108 85 54 46 618182828363641414 47 718181717161615150 00 00 0111120202626合计合计合计合计41411331335757平均平均平均平均133/41=3.24133/41=3.24 133/6=22.17133/6=22.1757/6=9.557/6=9.52022/10/

18、2615生生产产与与运运作作管管理理四、两台机床作业排序方法四、两台机床作业排序方法w加工顺序相同的若干个作业在两台机床上的加加工顺序相同的若干个作业在两台机床上的加加工顺序相同的若干个作业在两台机床上的加加工顺序相同的若干个作业在两台机床上的加工排序，我们运用约翰逊（工排序，我们运用约翰逊（工排序，我们运用约翰逊（工排序，我们运用约翰逊（JohnsonJohnson）规则解决。规则解决。规则解决。规则解决。其步骤如下：其步骤如下：其步骤如下：其步骤如下：(1)(1)列出每个作业在两台机床上的作业时间；列出每个作业在两台机床上的作业时间；列出每个作业在两台机床上的作业时间；列出每个作业在两台机

19、床上的作业时间；(2)(2)选择最短的作业时间；选择最短的作业时间；选择最短的作业时间；选择最短的作业时间；(3)(3)如果最短的作业时间来自第一台机床，则首先如果最短的作业时间来自第一台机床，则首先如果最短的作业时间来自第一台机床，则首先如果最短的作业时间来自第一台机床，则首先进行这个作业；如果最短的作业时间来自第二进行这个作业；如果最短的作业时间来自第二进行这个作业；如果最短的作业时间来自第二进行这个作业；如果最短的作业时间来自第二台机床，则最后进行这个作业；台机床，则最后进行这个作业；台机床，则最后进行这个作业；台机床，则最后进行这个作业；(4)(4)重复上述步骤，直到排序完成。重复上述

20、步骤，直到排序完成。重复上述步骤，直到排序完成。重复上述步骤，直到排序完成。2022/10/2616生生产产与与运运作作管管理理约翰逊约翰逊-贝尔曼规则贝尔曼规则w例：例：4 4项作业在两台设备上进行加工，其加工顺项作业在两台设备上进行加工，其加工顺项作业在两台设备上进行加工，其加工顺项作业在两台设备上进行加工，其加工顺序相同，作业时间如下表所示序相同，作业时间如下表所示序相同，作业时间如下表所示序相同，作业时间如下表所示:6 62 25 53 37 74 42 26 68 8T TT=2+4+8+6+5=255 53 3A A7 78 86 6t t1 1t t2 26 6机床机床机床机床作

21、业作业作业作业B BD DC C2 24 4A AD DC C1 12022/10/2617生生产产与与运运作作管管理理五、五、3台机器上台机器上N项作业的排项作业的排序序(简称为简称为N/3排序排序)w此方法是约翰逊（此方法是约翰逊（Johnson）规则的扩展规则的扩展方法，它是将三台设备合并为两台假想的方法，它是将三台设备合并为两台假想的设备，然后按约翰逊设备，然后按约翰逊(Johnson)规则进行规则进行排序。排序。此方法可得到最优解；否则，只能得到近似最优解。此方法可得到最优解；否则，只能得到近似最优解。此方法可得到最优解；否则，只能得到近似最优解。此方法可得到最优解；否则，只能得到近

22、似最优解。当满足当满足当满足当满足或或或或时时时时注意：注意：注意：注意：2022/10/2618生生产产与与运运作作管管理理约翰逊约翰逊(Johnson)规则的规则的扩展方法扩展方法w例：例：4项作业在三台设备上进行加工，其项作业在三台设备上进行加工，其加工顺序相同，作业时间如下表所示加工顺序相同，作业时间如下表所示:9 9A A10104 46 6t t1 1t t2 26 6机床机床机床机床作业作业作业作业B BD DC C t t3 3 7 7 8 8 12 12 6 65 53 39 91 1A AD DC CB B作业作业作业作业1212A A1515t tGG1010机床机床机床

23、机床B BD DC C t tH H10101212181811111515解：解：解：解：2022/10/2619生生产产与与运运作作管管理理续续2T=7+6+12+6+9+6=46 T T7 7 8 812126 66 65 54 49 910106 69 93 33 3A A7 78 86 6t t1 1t t2 26 6机床机床机床机床作业作业作业作业B BD DC CE EF F2 26 67 79 94 45 57 7作业题：作业题：作业题：作业题：排序并计算排序并计算排序并计算排序并计算加工周期。加工周期。加工周期。加工周期。2022/10/2620生生产产与与运运作作管管理理六

24、、六、M台机器上台机器上N项作业的排项作业的排序序(简称为简称为N/M排序排序)w一般解法：一般解法：分枝定界法分枝定界法w启发式算法启发式算法称为称为CDS算法算法，该算法是该算法是将将N/3的约贝扩展方法进一步扩展到一般的约贝扩展方法进一步扩展到一般的的N/M问题，以求得一个近似的最优解。问题，以求得一个近似的最优解。也叫坎贝尔也叫坎贝尔-杜达克杜达克-史密斯法。史密斯法。w关键零件法关键零件法w最小排序系数最小排序系数 2022/10/2621生生产产与与运运作作管管理理CDS算法的步骤算法的步骤 w w第一步，根据第第一步，根据第第一步，根据第第一步，根据第1 1台与第台与第台与第台与

25、第MM台（即最后一台）机器的台（即最后一台）机器的台（即最后一台）机器的台（即最后一台）机器的两组操作时间，应用约贝规则排出第两组操作时间，应用约贝规则排出第两组操作时间，应用约贝规则排出第两组操作时间，应用约贝规则排出第1 1个作业顺序方个作业顺序方个作业顺序方个作业顺序方案；案；案；案；w w第二步，根据第第二步，根据第第二步，根据第第二步，根据第1 1台与第台与第台与第台与第2 2台机器的操作时间合并，台机器的操作时间合并，台机器的操作时间合并，台机器的操作时间合并，以及第（以及第（以及第（以及第（M-1M-1）与第与第与第与第MM台机器的操作时间合并，得台机器的操作时间合并，得台机器的

26、操作时间合并，得台机器的操作时间合并，得到两组操作时间，应用约贝规则排出第到两组操作时间，应用约贝规则排出第到两组操作时间，应用约贝规则排出第到两组操作时间，应用约贝规则排出第2 2个作业顺序个作业顺序个作业顺序个作业顺序方案；方案；方案；方案；w w第三步，根据第第三步，根据第第三步，根据第第三步，根据第1 1、第、第、第、第2 2、第、第、第、第3 3台，三台机器的操作时台，三台机器的操作时台，三台机器的操作时台，三台机器的操作时间合并，以及第（间合并，以及第（间合并，以及第（间合并，以及第（M-2M-2）、）、）、）、第（第（第（第（M-1M-1）、）、）、）、第第第第MM台三台台三台台

27、三台台三台机器的操作时间合并，又得到两组操作时间，应用机器的操作时间合并，又得到两组操作时间，应用机器的操作时间合并，又得到两组操作时间，应用机器的操作时间合并，又得到两组操作时间，应用约贝规则，排出第约贝规则，排出第约贝规则，排出第约贝规则，排出第3 3个作业顺序方案；个作业顺序方案；个作业顺序方案；个作业顺序方案；2022/10/2622生生产产与与运运作作管管理理CDS算法的步骤算法的步骤(续续)w第四步，重复以上运算，最后将第第四步，重复以上运算，最后将第第四步，重复以上运算，最后将第第四步，重复以上运算，最后将第1 1、第、第、第、第2 2、，第（第（第（第（M-1M-1）共（共（共

28、（共（M-1M-1）台机器和操作时间合并，台机器和操作时间合并，台机器和操作时间合并，台机器和操作时间合并，以及将第以及将第以及将第以及将第2 2、第、第、第、第3 3、第、第、第、第MM共（共（共（共（M-1M-1）台机器的台机器的台机器的台机器的操作时间合并，得到的两组操作时间，也应用约操作时间合并，得到的两组操作时间，也应用约操作时间合并，得到的两组操作时间，也应用约操作时间合并，得到的两组操作时间，也应用约贝规则，排出第（贝规则，排出第（贝规则，排出第（贝规则，排出第（M-1M-1）个作业顺序方案；个作业顺序方案；个作业顺序方案；个作业顺序方案；w第五步，根据以上（第五步，根据以上（第五步，根据以上（第五步，根据以上（M-1M-1）个工作顺序方案，分个工作顺序方案，分个工作顺序方案，分个工作顺序方案，分别作图求出它们的总流动时间从中取得小值，最别作图求出它们的总流动时间从中取得小值，最别作图求出它们的总流动时间从中取得小值，最别作图求出它们的总流动时间从中取得小值，最小值所对应的排序方案为最优的或近似最优的方小值所对应的排序方案为最优的或近似最优的方小值所对应的排序方案为最优的或近似最优的方小值所对应的排序方案为最优的或近似最优的方案。案。案。案。2022/10/2623生生产产与与运运作作管管理理2022/10/2624