《作业排序》PPT课件.ppt

第十一章 作业排序,本章主要介绍制造业的作业排序问题。,2019/6/22,武汉理工大学管理学院 袁付礼,2,一、作业排序的概念和类型,1、概念 对一定期间内分配给生产单位的作业任务，根据产品(零件)的工艺路线和设备负荷可能性，确定各个生产单位作业任务的先后顺序。 作业排序问题通常表述为“n项作业任务在m个生产单位的排序的问题”。,2019/6/22,武汉理工大学管理学院 袁付礼,3,一、作业排序的概念和类型,2、作业排序的类型： 流水型mn排序问题 指n项任务在m台设备上加工，所有任务的工艺顺序相同，有n!个排序方案。 非流水型mn排序问题 指n项任务在m台设备上加工，所有任务的工艺顺序不同，有(n!)m个排序方案。,2019/6/22,武汉理工大学管理学院 袁付礼,4,一、作业排序的概念和类型,作业排序的表示方法为 生产单位数作业任务数/排序问题类型/评价尺度(优化目标) 如m n/FLW/Fmax表示m个生产单位完成n项作业任务、流水型排序问题和以最大流程时间作为评价尺度。,2019/6/22,武汉理工大学管理学院 袁付礼,5,二、作业排序的评价尺度,最大流程时间 平均流程时间 最大延期量 平均延期量 在制品占用量 总调整时间,2019/6/22,武汉理工大学管理学院 袁付礼,6,计算公式,设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 + wim,2019/6/22,武汉理工大学管理学院 袁付礼,7,计算公式(续),令ti为作业任务i的总作业时间，则： 令wi为作业任务i的总等候时间，则： 则 ci=ri+ti+wi,2019/6/22,武汉理工大学管理学院 袁付礼,8,计算公式(续),第i项作业任务在机床组的流程时间为： Fi=ci-ri=ti+wi 如果作业任务i的完成时刻ci已超过要求完成时刻di，则形成交货延期，延期量Di为： Di= ci-di=Fi+ri-di 如果ci未超过di ，则延期量Di为0。,2019/6/22,武汉理工大学管理学院 袁付礼,9,排序问题解法的约定,一个工件不能同时在不同的设备上加工； 每道工序只在一台设备上完成，每台设备只完成一道工序； 每台设备同时只能加工一个工件； 工件在加工过程中采取平行移动方式； 工件数(n)、设备数(m)与加工时间均已知，允许工件在工序之间等待，允许设备在工件未到达时闲置。,2019/6/22,武汉理工大学管理学院 袁付礼,10,三、单台机床作业排序方法,1n流水排序型问题的优先规则： 先到先服务(FCFS) 最短作业时间(SPT) 最短交货延期量(EDD) SPT与EDD结合原则 最小松弛时间(SST) 后到先服务(LCFS) 按期完成作业项目最多的原则,按期完成作业项目最多的原则：即先按交货期优先原则逐项安排作业顺序，并依次计算每项任务是否拖期，如果遇到某项任务拖期，则将其移至最后加工；之后，若又有任务拖期，则又将其移至最后加工。,2019/6/22,武汉理工大学管理学院 袁付礼,11,三、单台机床作业排序方法,例：下表是在某工作中心等待加工的6项作业的加工时间（包含换产时间）与预定日期，假设工作的到达顺序与表中顺序相符 。根据以下规则来决定其作业顺序：FCFSSPTEDDSST并对它们分别进行评价。,2019/6/22,武汉理工大学管理学院 袁付礼,12,按FCFS规则排序,排序的结果是A-B-C-D-E-F。,2019/6/22,武汉理工大学管理学院 袁付礼,13,按SPT规则,作业顺序是A-C-E-B-D-F,2019/6/22,武汉理工大学管理学院 袁付礼,14,按EDD规则,作业顺序是C-A-E-B-D-F,2019/6/22,武汉理工大学管理学院 袁付礼,15,按SST规则,松弛时间=预定日期-加工时间，按松弛时间从小到大排列，可得顺序：C-A-F-D-B-E,2019/6/22,武汉理工大学管理学院 袁付礼,16,四、两台机床作业排序方法,加工顺序相同的若干个作业在两台机床上的加工排序，我们运用约翰逊（Johnson）规则解决。其步骤如下： (1)列出每个作业在两台机床上的作业时间； (2)选择最短的作业时间； (3)如果最短的作业时间来自第一台机床，则首先进行这个作业；如果最短的作业时间来自第二台机床，则最后进行这个作业； (4)重复上述步骤，直到排序完成。,2019/6/22,武汉理工大学管理学院 袁付礼,17,约翰逊-贝尔曼规则,例：4项作业在两台设备上进行加工，其加工顺序相同，作业时间如下表所示:,T = 2+4+8+6+5 = 25,2019/6/22,武汉理工大学管理学院 袁付礼,18,五、3台机器上N项作业的排序(简称为N/3排序),此方法是约翰逊（Johnson）规则的扩展方法，它是将三台设备合并为两台假想的设备，然后按约翰逊(Johnson)规则进行排序。,2019/6/22,武汉理工大学管理学院 袁付礼,19,约翰逊(Johnson)规则的 扩展方法,例：4项作业在三台设备上进行加工，其加工顺序相同，作业时间如下表所示:,2019/6/22,武汉理工大学管理学院 袁付礼,20,续,2,T = 7+6+12+6+9+6 = 46,作业题： 排序并计算 加工周期。,2019/6/22,武汉理工大学管理学院 袁付礼,21,六、M台机器上N项作业的排序(简称为N/M排序),一般解法：分枝定界法 启发式算法称为CDS算法，该算法是将N/3的约贝扩展方法进一步扩展到一般的N/M问题，以求得一个近似的最优解。也叫坎贝尔-杜达克-史密斯法。 关键零件法 最小排序系数,2019/6/22,武汉理工大学管理学院 袁付礼,22,CDS算法的步骤,第一步，根据第1台与第M台（即最后一台）机器的两组操作时间，应用约贝规则排出第1个作业顺序方案； 第二步，根据第1台与第2台机器的操作时间合并，以及第（M-1）与第M台机器的操作时间合并，得到两组操作时间，应用约贝规则排出第2个作业顺序方案； 第三步，根据第1、第2、第3台，三台机器的操作时间合并，以及第（M-2）、第（M-1）、第M台三台机器的操作时间合并，又得到两组操作时间，应用约贝规则，排出第3个作业顺序方案；,2019/6/22,武汉理工大学管理学院 袁付礼,23,CDS算法的步骤(续),第四步，重复以上运算，最后将第1、第2、，第（M-1）共（M-1）台机器和操作时间合并，以及将第2、第3、第