第12讲 作业计划

1、第12讲 作业计划生产作业计划概述作业排序的数学方法 服务业的作业排序第一节 生产作业计划概述一、生产作业计划的概念 生产作业计划是根据MRP（物料需求计划）下达的生产任务，具体、详细地规定了各车间、工段、班组以至每个工作地在相应时间内的生产运作任务和加工顺序。二、排序的分类二、排序的分类v 按排序的基本形式分：按排序的基本形式分：劳动力排序劳动力排序确定人员工作开始与结束时间确定人员工作开始与结束时间生产作业排序生产作业排序工件加工顺序或人员工作分配工件加工顺序或人员工作分配v 按机器的种类和数量分：按机器的种类和数量分：单台机器单台机器多台机器多台机器流水型排序流水型排序非流水型排序非流水

2、型排序v 按预期目标分：按预期目标分：平均流程时间最短平均流程时间最短误期完工的工件最少误期完工的工件最少v 按工件到达车间的情况分：按工件到达车间的情况分：静态排序静态排序动态排序动态排序三、作业排序的一般方法 （一）（一）甘特图甘特图 甘特图是作业排序中最常用的一种工具。它是由亨利劳伦斯甘特(Henry L.Gantt)在1917年首先提出来的。甘特是泰勒创立和推广科学管理制度的亲密的合作者，也是科学管理运动的先驱者之一。机械制造工厂作业进度甘特图机械制造工厂作业进度甘特图机械制造工厂作业机械制造工厂作业机器机器甘特图甘特图（二）排序的优先规则 (1) FCFS(first come fi

3、rst serve，先到先服务)：按订单送到的先后顺序进行加工。 (2) SPT(smallest processing time，最短作业时间)：加工时间最短的作业首先进行，然后是加工时间第二短的，以此类推。 (3) EDD(earliest due date，最早交货期)最早交货期最早加工。将交货期最早的作业放在第一个进行。 (4) STR(剩余松弛时间)：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。 (5) STR/OP(每个作业剩余的松弛时间)：STR/OP最短的任务最先进行。 (6) CR(关键比率)：关键比率是用交货日期减去当前日期的差值除以剩余的工作日数。关键比率最小

4、的任务先执行。 (7) LCFS(后到先服务)：该规则经常作为默认规则使用。因为后来的工单放在先来的上面，操作员通常是先加工上面的工单。 (8) 随机次序第二节作业排序的数学方法第二节作业排序的数学方法 作业排序的表示方法作业排序的表示方法单台设备上的作业排序方法单台设备上的作业排序方法 流水生产线作业排序方法流水生产线作业排序方法 单件生产任务分配与作业排序单件生产任务分配与作业排序一、作业排序的表示方法 Conway等人提出了可用4个描述作业的排序问题， 即：n/m/A/B。其中： n：工件数 m：机器数 A：排序的类型，可用F、P和G表示。F表示流水型，指所有工件的工艺过程均相同；P表示

5、流水型且为同顺序排序，指所有工件的工艺过程均相同，且在每台设备上所有工件的投产顺序也必须相同；表示非流水型排序。 B：具体的目标。如Fmax为最大的流程时间最短。 例如，n/5/P/Fmax则表示工件数为n、机器数为5、同顺序流水型排序，其目标是最大的流程时间最短。二、单台设备上的作业排序方法二、单台设备上的作业排序方法排序规则： 先到先服务先到先服务FCF First-Come, First-Serve 交货期最早交货期最早EDD Earliest Due Date 最短加工时间最短加工时间 SPT Smallest processing time【范例1】有6个工件需要在某台设备上加工，各

6、工件的加工时间如图1-1所示（工件编号是工件达到工作地的先后次序）（当前日期为1） 表表1-1 工件的加工时间与交货期工件的加工时间与交货期工件编号i123456加工时间交货期7148121020210515618 表表1-2 按照先来先加工的规则排序按照先来先加工的规则排序注：总的拖期数是注：总的拖期数是5件，平均拖期时间为：件，平均拖期时间为：（0+3+5+17+17+20）/6=10.33,平均流程时间：平均流程时间：(7+15+25+27+32+38)/6=24作业排序工件编号112233445566加工时间等待时间完成时间交货期拖期时间707140871512310152520522

7、5271017527321517632381820FCFS-先到先服务先到先服务二、流水生产线作业排序方法二、流水生产线作业排序方法流水线排序问题的描述流水线排序问题的描述 多工件两台设备的排序问题算法多工件两台设备的排序问题算法多工件多设备的排序问题算法多工件多设备的排序问题算法1.流水线排序问题的描述流水线排序问题的描述假设：（1）一个工件不能同时在不同机器上加工。（2）工件在加工过程中采用平行移动方式（当上一道工序完成后立即进入下道工序）。（3）不允许中断，工件一旦进入加工状态，一直加工完成为止，中途不插入其他工件。（4）每道工序只在一台设备上加工。（5）工件数、机器数与加工时间已知。2

8、. 多工件两台设备的排序问题算法多工件两台设备的排序问题算法 约翰逊法是作业排序中比较常用的一种排序方法，解决n/2/P/Fmax的排序问题。 它适用的条件是：n个工件经过两台设备(有限台设备)加工，所有工件在有限设备上加工的次序相同。 约翰逊法操作步骤： (1) 选出最短加工时间i，若最短加工时间有多个，任选1个； (2) 若i出现在机床1，它对应的工件先安排加工，否则放在最后安排，安排后划去该工件； (3) 重复上两个步骤，直到所有工件都排序完毕。零 件(i)作业时间tix机器1(j)机器2(k)A52B36C75D43E64【范例2】 有5个工件在2台设备上加工，加工顺序相同，先在设备1

9、上加工，再在设备2上加工，工时列于表1中，用约翰逊法排序。表2 加工工时表 表表3 零件加工顺序表零件加工顺序表步 骤加工顺序1A2BA3BDA4BEDA5BCEDA零 件BCEDA机器13/37/106/164/205/25机器26/95/154/203/232/27表4 零件加工时间表课堂练习 已经有6个工件需要在两台设备上加工的流水作业，单件加工时间矩阵如表所示。应用Johnson算法确定最优解。加工时间矩阵加工时间矩阵1234568342761932105i1 ip2ip课堂练习 表中的第2步，由于最小时间是2，有两种可选的方案，即先选工件2和先选工件5，最后得出两种不同的排序结果：4

10、36152 或436125。 两种排序的最长流程时间都是35。故两种排序都是最优的排序。3.多工件多设备的排序问题的算法多工件多设备的排序问题的算法 CDS法 CDSCDS法是由法是由CambelCambel、DudekDudek、SmithSmith三人合三人合作创立的作创立的Johnson算法的扩展方法。 这种方法的基本思想是把多设备的排序 问题转化为两台设备的排序问题，然后 利用Johnson算法排序。CDS法的解题步骤 基本步骤：基本步骤： 1 1） 将第将第1 1台设备与第台设备与第m m台设备的工件加工时间组成两组加台设备的工件加工时间组成两组加工时间，应用工时间，应用Johnso

11、nJohnson算法得出一个排序方案。算法得出一个排序方案。 2 2）将第）将第1 1、第、第2 2台设备的工件加工时间相加台设备的工件加工时间相加 ，第（，第（m-1m-1）和第和第m m台设备的工件加工时间相加台设备的工件加工时间相加 ，组成两组加工时间，组成两组加工时间，用用JohnsonJohnson算法得出第算法得出第2 2个排序方案。个排序方案。 3）重复上述做法，直到将第）重复上述做法，直到将第1台设备的加工时间至第台设备的加工时间至第(m-1)台设备的加工时间相加，第台设备的加工时间相加，第2台设备至第台设备至第m台设备的工台设备的工件加工时间相加，组成两组加工时间，利用件加工

12、时间相加，组成两组加工时间，利用Johnson算算法得到第（法得到第（m-1）个排序方案。）个排序方案。 4）在所有的）在所有的(m-1)个排序方案中选择流程时间最短的一个，个排序方案中选择流程时间最短的一个，即为所求即为所求。CDS法案例 【范例3】已知有4个工件在3个机器上作业，见表4，求最优工作排序。 用用CDS法求最优加工顺序。法求最优加工顺序。 表4 加工时间表工 件设 备1234Pi11363Pi28429Pi34582CDS法法-穷举方案表5 CDS法的方案第一步，取首末两道工序的时间构成一个2行矩阵，用约翰逊法排序，即方案1，排序为(1-2-3-4)，Fmax=28，计算过程见

13、表6。表表6 方案方案1的加工时间的加工时间表表7 方案方案2的加工时间的加工时间第二步，取首两道工序和尾两道工序的和，组成一个新的2行矩阵，用约翰逊法排序，即方案2，排序为(2-3-1-4)，Fmax30，计算过程见表7。（三）单件生产作业任务分配与排序（三）单件生产作业任务分配与排序1. 任务分配任务分配2. 作业排序作业排序 1. 任务分配任务分配 假设有n份任务要分配给n个任务承担者（人或机器），用0-1整数规划方法表示，任务分配问题的数学模型为： 式中： 为第 个任务承担者完成第 个任务的时间（或费用）。 ninjijijxcZ11minijcij1. 任务分配（续）任务分配（续）约

14、束条件： （1） （2） （3）系数矩阵：niijx11nj,2, 111njijxni,2, 11, 0 orxijnnnnnnijcccccccccc212222111211)(【范例4】 现将某种产品的4个零件，分配给4个班组分别去完成。一个小组承担一个零件，不同小组完成这一零件的作业时间见表8，求怎样分配任务所花时间最少。表8 作业时间表 天 解题过程见：P346课堂练习 有四项任务要在4个设备上加工，加工时间如表所示。确定最优化的任务分配方案。 表表9-任务加工时间任务加工时间任务设备J1J2J3J4任务设备J1J2J3J4M135710M35738M242148M4849112.

15、单件车间排序单件车间排序单件生产作业排序问题是最复杂的一类排序问题。单件车间作业计划与流水车间的作业计划不同，由于工件的加工路线多样化，导致其作业排序的问题比流水作业排序问题复杂得多。用优化方法需要更长计算时间，因此一般也都用启发方法才更有实践应用价值第三节 服务作业排序 服务运作的特点 顾客排序 服务人员排序一、一、服务运作的特征服务运作的特征同步性同步性(simultaneity)(simultaneity)，服务过程中的顾客参与。，服务过程中的顾客参与。异质性异质性(heterogeneity)(heterogeneity)，服务难以标准化。，服务难以标准化。易逝性易逝性(perisha

16、bility)(perishability)，服务不能通过库存来调，服务不能通过库存来调节能力。节能力。二、顾客排序二、顾客排序q预约预约q预订预订q排队等待排队等待三三、 服务员服务员排序排序-轮班轮班 将服务员工安排到不同的服务需求时间上的作业计划是服务员工轮班问题。 下面介绍两种常见的轮班方式： 1. 员工固定的轮班计划 2. 员工变化的轮班计划。1. 员工固定的轮班计划员工固定的轮班计划 (1) 三班制:班次第一周第二周第三周第四周早甲乙丙甲中乙丙甲乙夜丙甲乙丙表表10 10 三班倒的轮班计划三班倒的轮班计划(2)四班制:即“四班三运转” 轮班方式工作日1234567891011121

17、3141516工作班组早班甲甲丁丁丙丙乙乙甲甲丁丁丙丙乙乙中班乙乙甲甲丁丁丙丙乙乙甲甲丁丁丙丙夜班丙丙乙乙甲甲丁丁丙丙乙乙甲甲丁丁轮休班组丁丁丙丙乙乙甲甲丁丁丙丙乙乙甲甲表表11 11 四班三运转的轮班计划四班三运转的轮班计划2. 员工变化的轮班计划员工变化的轮班计划 员工上班人数变化的工作轮班计划是每个人没有固定的工作班组，每个时间段的上岗人员也不固定，随需求的变化而变化。 员工上班人数变化的工作轮班方式很多,有日工作制与小时工作制等,解决排班的方法主要有如下两种: （1）启发方法:如循环排序法 （2）最优化方法:如线性规划法（1）循环排序法循环排序法 循环排序法是一种既简单又实用的启发式方

18、法，其基本步骤如下： 步骤步骤1：从每周的员工需求人数中找到所需员工数量之和最小的连续两个工作日,安排一名员工在这两天中休息。步骤步骤2：使该两天的需求人数保持不变使该两天的需求人数保持不变, 其他日期的需其他日期的需求人数减求人数减1(如果是如果是0不变不变)步骤步骤3：在新一行中找出所需员工数量最少的连续两天，并再次循环。将下一名员工分配到剩余的工作日中。步骤步骤4：重复上述过程（步骤2和3），直到所有的人员需求得到满足。【范例5】某医院拟根据一周内病人每天就医数量不均衡的情况，确定护士的数量及排班计划。要求每名护士每周工作5天，并连续休息2天。每天所需的护士数量如表12所示。表12 护士需求数量一览表解：循环排序法从连续2天所需护士数量最少的日期确定护士的休息日，其他的为工作日，并以此类推，排出每名护士工作与休息计划。本例，星期六和星期日所需护士最少，故护士一被安排到这两天休息，星期一至星期五工作。因此，星期一至星期五所需的护士数在原护士需求数量的基础上减1，星期六和星期日数量不变（因护士一休息），这两个数字用“”括起来，表示本循环内不参与数量调整，而其他的数字则减1。重复上述过程，排出护士工作的计划。 13 护士需求数量与排