第十一章作业排序

一章作业排序本章主要介绍制造业的作业排序问题。2021/5/91一、作业排序的概念和类型1、概念对一定期间内分配给生产单位的作业任务，根据产品(零件)的工艺路线和设备负荷可能性，确定各个生产单位作业任务的先后顺序。作业排序问题通常表述为“n项作业任务在m个生产单位的排序的问题”。2021/5/92武汉理工大学管理学院袁付礼一、作业排序的概念和类型2、作业排序的类型：⑴流水型m×n排序问题指n项任务在m台设备上加工，所有任务的工艺顺序相同，有n!个排序方案。⑵非流水型m×n排序问题

指n项任务在m台设备上加工，所有任务的工艺顺序不同，有(n!)m个排序方案。

2021/5/93武汉理工大学管理学院袁付礼一、作业排序的概念和类型作业排序的表示方法为

生产单位数×作业任务数/排序问题类型/评价尺度(优化目标)如m

×n/FLW/Fmax表示m个生产单位完成n项作业任务、流水型排序问题和以最大流程时间作为评价尺度。2021/5/94武汉理工大学管理学院袁付礼二、作业排序的评价尺度最大流程时间平均流程时间最大延期量平均延期量在制品占用量总调整时间2021/5/95武汉理工大学管理学院袁付礼计算公式设n为作业任务数，m为机床数，Ji为第i项作业任务，Oij为第i项作业任务的和j工序，tij为第i项作业任务在第j台机床上的作业时间，ri为任务Ji可以开始加工的时刻，di为Ji的要求完成时刻，wij为Oij在进行加工前的等候时间。如果没有等候，wij=0。第i项任务的完成时刻(ci)为ci=ri+ti1+wi1+ti2+wi2+…+tim+wim2021/5/96武汉理工大学管理学院袁付礼计算公式(续)令ti为作业任务i的总作业时间，则：令wi为作业任务i的总等候时间，则：则ci=ri+ti+wi2021/5/97武汉理工大学管理学院袁付礼计算公式(续)第i项作业任务在机床组的流程时间为：Fi=ci-ri=ti+wi如果作业任务i的完成时刻ci已超过要求完成时刻di，则形成交货延期，延期量Di为：Di=ci-di=Fi+ri-di如果ci未超过di，则延期量Di为0。2021/5/98武汉理工大学管理学院袁付礼排序问题解法的约定⑴一个工件不能同时在不同的设备上加工；⑵每道工序只在一台设备上完成，每台设备只完成一道工序；⑶每台设备同时只能加工一个工件；⑷工件在加工过程中采取平行移动方式；⑸工件数(n)、设备数(m)与加工时间均已知，允许工件在工序之间等待，允许设备在工件未到达时闲置。2021/5/99武汉理工大学管理学院袁付礼三、单台机床作业排序方法1×n流水排序型问题的优先规则：先到先服务(FCFS)最短作业时间(SPT)最短交货延期量(EDD)SPT与EDD结合原则最小松弛时间(SST)

后到先服务(LCFS)按期完成作业项目最多的原则按期完成作业项目最多的原则：即先按交货期优先原则逐项安排作业顺序，并依次计算每项任务是否拖期，如果遇到某项任务拖期，则将其移至最后加工；之后，若又有任务拖期，则又将其移至最后加工。

2021/5/910武汉理工大学管理学院袁付礼三、单台机床作业排序方法例：下表是在某工作中心等待加工的6项作业的加工时间（包含换产时间）与预定日期，假设工作的到达顺序与表中顺序相符。根据以下规则来决定其作业顺序：①FCFS②SPT③EDD④SST并对它们分别进行评价。

作业加工时间（天）预定日期（天）ABCDEF2841051271641715182021/5/911武汉理工大学管理学院袁付礼按FCFS规则排序排序的结果是A-B-C-D-E-F。顺序加工时间流程时间预定交货期延期天数(如果为负则赋值0)ABCDEF28410512210142429417164171518001071423合计4112054平均120/41=2.93120/6=2054/6=92021/5/912武汉理工大学管理学院袁付礼按SPT规则作业顺序是A-C-E-B-D-F顺序加工时间流程时间预定交货期延期天数(如果为负则赋值0)ACEBDF

245810122611192941741516171802031223合计4110840平均108/41=2.63108/6=1840/6=6.672021/5/913武汉理工大学管理学院袁付礼按EDD规则作业顺序是C-A-E-B-D-F顺序加工时间流程时间预定交货期延期天数(如果为负则赋值0)CAEBDF425810124611192941471516171800031223合计4111038平均110/41=2.68110/6=18.3338/6=6.332021/5/914武汉理工大学管理学院袁付礼按SST规则松弛时间=预定日期-加工时间，按松弛时间从小到大排列，可得顺序：C-A-F-D-B-E顺序松弛时间加工时间流程时间预定交货期延期天数(如果为负则赋值0)CAEBDF05678104212108546182836414718171615000112026合计4113357平均133/41=3.24133/6=22.1757/6=9.52021/5/915武汉理工大学管理学院袁付礼四、两台机床作业排序方法加工顺序相同的若干个作业在两台机床上的加工排序，我们运用约翰逊（Johnson）规则解决。其步骤如下：(1)列出每个作业在两台机床上的作业时间；(2)选择最短的作业时间；(3)如果最短的作业时间来自第一台机床，则首先进行这个作业；如果最短的作业时间来自第二台机床，则最后进行这个作业；(4)重复上述步骤，直到排序完成。2021/5/916武汉理工大学管理学院袁付礼约翰逊-贝尔曼规则例：4项作业在两台设备上进行加工，其加工顺序相同，作业时间如下表所示:625374268TT=2+4+8+6+5=2553A786t1t26机床作业BDC24ADC12021/5/917武汉理工大学管理学院袁付礼五、3台机器上N项作业的排序(简称为N/3排序)此方法是约翰逊（Johnson）规则的扩展方法，它是将三台设备合并为两台假想的设备，然后按约翰逊(Johnson)规则进行排序。此方法可得到最优解；否则，只能得到近似最优解。当满足或时注意：2021/5/918武汉理工大学管理学院袁付礼约翰逊(Johnson)规则的

扩展方法例：4项作业在三台设备上进行加工，其加工顺序相同，作业时间如下表所示:9A1046t1t26机床作业BDC

t3781265391ADCB作业12A15tG10机床BDC

tH1012181115解：2021/5/919武汉理工大学管理学院袁付礼续2T=7+6+12+6+9+6=46

T781266549106933A786t1t26机床作业BDCEF2679457作业题：排序并计算加工周期。2021/5/920武汉理工大学管理学院袁付礼六、M台机器上N项作业的排序(简称为N/M排序)

一般解法：分枝定界法启发式算法——称为CDS算法，该算法是将N/3的约贝扩展方法进一步扩展到一般的N/M问题，以求得一个近似的最优解。也叫坎贝尔-杜达克-史密斯法。关键零件法最小排序系数

2021/5/921武汉理工大学管理学院袁付礼CDS算法的步骤第一步，根据第1台与第M台（即最后一台）机器的两组操作时间，应用约贝规则排出第1个作业顺序方案；第二步，根据第1台与第2台机器的操作时间合并，以及第（M-1）与第M台机器的操作时间合并，得到两组操作时间，应用约贝规则排出第2个作业顺序方案；第三步，根据第1、第2、第3台，三台机器的操作时间合并，以及第（M-2）、第（M-1）、第M台三台机器的操作时间合并，又得到两组操作时间，应用约贝规则，排出第3个作业顺序方案；2021/5/922武汉理工大学管理学院袁付礼CDS算法的步骤(续)第四步，重复以上运算，最后将第1、第2、…，第（M-1