第十章 作业计划及控制

1、第第9章章 作业计划与控制作业计划与控制Operations Scheduling and Controlling第第1节节 作业计划作业计划(Scheduling) .1 作业计划的含义与作用作业计划的含义与作用作业计划作业计划(Scheduling):作业计划是安排零部件（作业、活动）的作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。出产数量、设备及人工使用、投入时间及出产时间。通过制定作业计划，可以使企业：通过制定作业计划，可以使企业： 满足交货期要求满足交货期要求 Meet Due Dates 使在制品库存最小使在制品库存最小 Minimize wor

2、k-in-process inventory 使平均流程时间最小使平均流程时间最小 Minimize the average flow time through the system 提供准确的工件状态信息提供准确的工件状态信息 Provide for accurate job status information 提高机器提高机器/工人的时间利用率工人的时间利用率 Provide for high machine/worker time utilization(Minimize worker idle time) 减少调整准备时间减少调整准备时间 Reduce setup times 使生产

3、和人工成本最低使生产和人工成本最低 Minimize production and worker costs 制定作业计划的主要原则制定作业计划的主要原则 工件流动工件流动(物流物流)带来价值带来价值 = 现金流现金流 物流通过车间的速度物流通过车间的速度 = 效率效率 将工件流安排成一连续过程将工件流安排成一连续过程 流程上一步接一步流程上一步接一步 避免工作中断避免工作中断 动态安排作业计划动态安排作业计划 未完成任务要能够及时反馈未完成任务要能够及时反馈 投入工作地的任务与能力要匹配投入工作地的任务与能力要匹配 发现瓶颈发现瓶颈 动态特征动态特征 找出工程设计与制造执行过程之间的不相容性

4、找出工程设计与制造执行过程之间的不相容性1.2 作业计划的种类 大量生产类型的作业计划大量生产类型的作业计划(Scheduling in High-Volume Systems) 成批生产类型的作业计划成批生产类型的作业计划(Scheduling in Intermediate-Volume Systems) 单件小批生产类型作业计划单件小批生产类型作业计划(Scheduling in Low-Volume Systems)另外，还有其他分类：另外，还有其他分类： 车间作业计划车间作业计划(Job Floor scheduling) 人力计划人力计划(Personnel Scheduling)

5、 设施计划设施计划(Facilities Scheduling) 车辆调度计划车辆调度计划(Vehicle Scheduling) 供应商计划供应商计划(Vendor Scheduling) 工程项目计划工程项目计划(Project Scheduling) 动态计划和静态计划动态计划和静态计划(Dynamic versus Static Scheduling) 1.3 制定作业计划的影响因素 工件到达的方式工件到达的方式(The job arrival pattern) 车间内机器的数量车间内机器的数量(Number and variety of machines in the shop) 车

6、间拥有的人力资源车间拥有的人力资源(Number of workers in the shop) 工件移动方式工件移动方式(Particular flow patterns) 不同调度准则的评价不同调度准则的评价(Evaluations of alternative rules) 1.4 作业计划与控制的关系 作业计划：给生产活动作业计划：给生产活动(Production Activities)制定详细时间表制定详细时间表 生产控制：以生产计划和作业计划为依据，检查、落实计划生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计执行情况，发现偏

7、差即采取纠正措施，保证实现各项各项计划目标。划目标。第第2节节 排序的基本概念排序的基本概念 (Sequencing) 2.1 排序与编制作业计划的差别排序与编制作业计划的差别 上面讲了编制作业计划的问题上面讲了编制作业计划的问题. 在编制作业计划过程中在编制作业计划过程中,有一有一个问题需要管理人员注意个问题需要管理人员注意,即投入生产过程的作业顺序的安排即投入生产过程的作业顺序的安排. 作业计划是安排零部件（作业、活动）的出产数量、设备作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。及人工使用、投入时间及出产时间。 排序，给出零部件在一台或一组设备上加工的

8、先后顺序的排序，给出零部件在一台或一组设备上加工的先后顺序的工作。工作。 所以所以,编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。编制作业计划的主要工作之一就是要确定出最佳的作业顺序。 确定出最佳的作业顺序看似容易，只要列出所有的顺序，确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。是不可能的。例如，考虑例如，考虑32项任务（工件），有项任务（工件），有32！ 2.6 1035种

9、方案种方案,假定计算机每秒钟可以检查假定计算机每秒钟可以检查1 billion个顺序个顺序, 全部检验完毕全部检验完毕需要需要8.4 1015个世纪个世纪.如果只有如果只有16个工件个工件, 同样按每秒钟可以检查同样按每秒钟可以检查1 billion个顺个顺序计算序计算, 也需要也需要2/3年年.以上问题还没有考虑其他的约束条件以上问题还没有考虑其他的约束条件, 如机器、人力资源、如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实所以，很有必要去寻找一些有效算

10、法，解决管理中的实际问题。际问题。单件车间制定作业计划示意图单件车间制定作业计划示意图根据排序规则对根据排序规则对每一个达到的订每一个达到的订单安排作业顺序单安排作业顺序工作地工作地工件排工件排对等待对等待加工加工来自上来自上游工作游工作地的订地的订单单加工完毕加工完毕的订单流的订单流向下一工向下一工作地作地2.2 排序问题的分类 根据机器数的多少根据机器数的多少 单台机器的排序问题单台机器的排序问题 多台机器的排序问题多台机器的排序问题 根据加工路线的特征根据加工路线的特征 单件车间排序单件车间排序(Job Shop) 流水型排序流水型排序(Flow Shop) 根据工件到达系统的情况根据工

11、件到达系统的情况 静态排序静态排序 动态排序动态排序 根据参数的性质根据参数的性质 确定型排序确定型排序 随机型排序随机型排序 根据要实现的目标根据要实现的目标 单目标排序单目标排序 多目标排序多目标排序 2.3 排序问题的表示方法排序问题的表示方法 排序问题常用四个符号来描述排序问题常用四个符号来描述: n/m/A/B其中其中, n-工件数；工件数； m-机器数；机器数； A-车间类型车间类型, F=流水型排序流水型排序 P=排列排序排列排序 G=一般类型一般类型,即单件型排序即单件型排序 B-目标函数目标函数2.4 排序常用的符号排序常用的符号 Ji-工件工件i，i=1,2,.n di-工

12、件工件i的交货期的交货期 Pi-工件工件i的加工时间的加工时间, , pij-工件工件i在机器在机器j上的加工上的加工时间时间,j=1,mmjijipP1mjijiwW1Wi-工件工件i在系统内的等待时间在系统内的等待时间, , wij-工件工件i在机器在机器j前的等待时间前的等待时间, j=1,m Ci-工件工件i的完成时间的完成时间, 在工件都已到达的情况下在工件都已到达的情况下, Ci= Pi+ Wi Fi-工件工件i的流程时间的流程时间，在工件都已到达的情况下在工件都已到达的情况下, Fi= Pi+ Wi Li-工件工件i的延误时间的延误时间, Li= Ci- di , Li0 延误延

13、误 Ti-工件工件i的延期量的延期量, Ti=max0, Li Ei-工件工件i提前完成的时间提前完成的时间第第3节节 单台机器的排序问题单台机器的排序问题 3.1 单台机器排序问题单台机器排序问题 n个工件全部经由一台机器处理个工件全部经由一台机器处理 J1J2J3Jn机器机器到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）3.2 常见单台机器排序问题的目标函数常见单台机器排序问题的目标函数 1) 平均流程时间最短平均流程时间最短 FnFiin_11为为n个零件经由一台机器的平均流程时间。个零件经由一台机器的平均流程时间。 定义定义: FnFiin_11目标函数目标函数

14、MIN: 2）最大延期量最小）最大延期量最小 TTimaxmax定义定义: 为最大延期量。为最大延期量。 目标函数目标函数 minmax T根据排序目标的不同，可以选择不同的排序规则，根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权有时又称为确定优先权(Priorities)。常见的优先权规则常见的优先权规则(Priority rules)有：有：SPT-Shortest Process Time,EDD-Earliest Due DateFCFS-First Come First ServedCR-Critical Rate等等, 分别用于解决不同的问题。分别用于解决不同的问

15、题。 几种调度准则的比较几种调度准则的比较FCFS - First-Come-First-Served 看似看似“公平公平”，但是没有运用已有信息，但是没有运用已有信息. 通常用于服务业的排对系统通常用于服务业的排对系统 (银行银行, 商店商店)LCFS - Last-Come-First-Served 该准则通常是缺省情况下发生的，到达的该准则通常是缺省情况下发生的，到达的工件被依次放到最上面工件被依次放到最上面. SPT - Shortest Processing Time在给定的时间内能完成最多的任务，并且在给定的时间内能完成最多的任务，并且能使平均等待最小能使平均等待最小. 但是使有些

16、任务大大推但是使有些任务大大推迟完成迟完成.EDD - Earliest Due Date试图达到平均延期和最大延期最小试图达到平均延期和最大延期最小. 但是需但是需要正确的交货期要正确的交货期.STR - Slack Time Remaining 使任何任务（订单）最大延期最小使任何任务（订单）最大延期最小. 动态动态计算计算CR - Critical Ratio 该比值表明订单是超前该比值表明订单是超前 (CR 1), 准时准时 (CR =1) 还是延迟还是延迟 (CR t6, 所以：所以：J2J1J3J4J6J54、去掉已调整的任务，重复、去掉已调整的任务，重复2-4步。步。 最后得最优

17、解：最后得最优解： J2J1J3J4J6J5F=13.67第第4节节 n项任务在两台机器的排序问题项任务在两台机器的排序问题Scheduling n Jobs on Two Machines 4.1 两台机器排序问题的含义两台机器排序问题的含义n个工件都必须经过机器个工件都必须经过机器1和机器和机器2的加工，即工艺路线是一致的。的加工，即工艺路线是一致的。 机器机器1到达系统工到达系统工件的集合件的集合离开系统（离开系统（机器）机器）J1J2J3Jn机器机器24.2 两台机器排序问题的目标两台机器排序问题的目标 两台机器排序的目标是使最大完成时间（总加工周期）两台机器排序的目标是使最大完成时间

18、（总加工周期）Fmax最短。最短。 Fmax的含义见如下的的含义见如下的甘特图甘特图(Gantt Chart)。 多台机器排序的目标一般也是使最大完成时间（总加多台机器排序的目标一般也是使最大完成时间（总加工周期）工周期） Fmax最短。最短。Fmax 时间 机器 A B在机器A上的作业时间总加工周期总加工周期的计算方法总加工周期的计算方法工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号 J1 J2 J3 J4 J5设备设备A 3 6 7 1 5设备设备B 2 8 6 4 3例例: 在设备在设备A和和B上安排上安排5个工件的加工任务，每项任务的作业时间如个工件的加工任务，每

19、项任务的作业时间如下表所示。求下表所示。求: 该顺序的总加工周期该顺序的总加工周期Fmax 。图解法：图解法：30AB0表格法表格法工件编号工件编号 J1 J2 J3 J4 J5设备设备A 33 69 716 117 522设备设备B25 817 623 427 330Fmax =304.3 两台机器排序问题的算法两台机器排序问题的算法 实现两台机器排序的最大完成时间实现两台机器排序的最大完成时间Fmax最短的目标，一优最短的目标，一优化算法就是著名的约翰逊法化算法就是著名的约翰逊法(Johnsons Law)。其具体求解。其具体求解过程如下例所示。过程如下例所示。 约翰逊法解决这种问题分为约

20、翰逊法解决这种问题分为4个步骤：个步骤： (1)列出所有工件在两台设备上的作业时间。列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。找出作业时间最小者。 (3)如果该最小值是在设备如果该最小值是在设备1上，将对应的工件排在前面，上，将对应的工件排在前面，如果该最小值是在设备如果该最小值是在设备2上，则将对应的工件排在后面。上，则将对应的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤(2)和和(3)，直到所有工件都安排完毕。，直到所有工件都安排完毕。 例：某一班组有例：某一班组有A、B两台设备，要完成两台设备，要完成5个

21、工件的加工任务。个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。最短的作业顺序。 工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号 J1 J2 J3 J4 J5设备设备A 3 6 7 1 5设备设备B 2 8 6 4 3解：由约翰逊法可知，表解：由约翰逊法可知，表5-8中最小加工时间值是中最小加工时间值是1个时间单个时间单位，它又是出现在设备位，它又是出现在设备1上，根据约翰逊法的规则，应将上，根据约翰逊法的规则，应将对应的工件对应的工件4排在第一位，即得：排在第一位，即得： J4 - *

22、 - * - * - * 去掉去掉J4，在剩余的工件中再找最小值，不难看出，最小值，在剩余的工件中再找最小值，不难看出，最小值是是2个时间单位，它是出现在设备个时间单位，它是出现在设备2上的，所以应将对应的上的，所以应将对应的工件工件J1排在最后一位，即：排在最后一位，即： J4 - * - * - * - J1 再去掉再去掉J1，在剩余的，在剩余的J2、J3、J5中重复上述步骤，求解过中重复上述步骤，求解过程为：程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后

23、得当同时出现多个最小值时，可从中任选一个。最后得J4 - J2 - J3- J5 - J1(a) J1 - J2 - J3- J4 - J5 26AB(b) J4 - J2 - J3- J5 - J1 可以看出，初始作业顺序的总加工周期是可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业，用约翰逊法排出的作业顺序总加工周期是顺序总加工周期是26，显然后者的结果优于前者。，显然后者的结果优于前者。30AB04.4 两台机器排序问题算法的扩展两台机器排序问题算法的扩展(Extension to Three Machines)一般情况下，当机器数为一般情况下，当机器数为3台以上时，就很难

24、找到最优解了。台以上时，就很难找到最优解了。 但是，对于但是，对于n个工件由三台机器流水作业时，在满足某些条个工件由三台机器流水作业时，在满足某些条件后可以采用件后可以采用Johnsons Law解决问题。解决问题。 设：设：A、B、C为三台机器，如果工件在三台机器上的加工时为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题：间满足以下条件，则可以转化为两台机器的排序问题： min Ai=max Bior min Ci = max Bi 定义：定义：Ai = Ai+ Bi , Bi = Bi +Ci例例: 考虑以下问题考虑以下问题. 5个工件由个工件由3台机

25、器加工台机器加工, 作业时间见下表作业时间见下表. 求求: 总加工周期最短的作业顺序总加工周期最短的作业顺序. 1 2 3 4 5机器机器A 44 913 821 627 532机器机器B 59 619 223 330 436机器机器C 817 1029 635 742 1153 解解: 检查上表检查上表, 发现发现: min Ai = 4 max Bi = 6 min Ci = 6因此因此,满足以上条件满足以上条件, 建立两台机器的作业时间表建立两台机器的作业时间表: 应用应用Johnson法则，得出：法则，得出：总加工周期为：总加工周期为： 1 2 3 4 5机器机器A 9 15 10 9

26、 9机器机器B 13 16 8 10 15 1 4 5 2 3机器机器A 44 610 515 924 832机器机器B 59 313 419 630 234机器机器C 817 724 1135 1045 6514.5 m(m 3)台机器排序问题的算法台机器排序问题的算法 一般采用启发式算法一般采用启发式算法(Heuristics)解决这类问题。解决这类问题。 关键工件法关键工件法步骤步骤1 计算计算 ,找出其中最大者，定义为关键工件找出其中最大者，定义为关键工件JC。mjijp1步骤步骤2 除除JC外，将满足外，将满足pi1pim的工件，按的工件，按tim值的大小，从值的大小，从大到小排在大

27、到小排在JC的后面。的后面。步骤步骤4 除除JC外，将满足外，将满足pi1=pim的工件，排在的工件，排在JC的前面或者后面。的前面或者后面。步骤步骤5 如有多个方案，可再加比较，从中选优。如有多个方案，可再加比较，从中选优。关键工件法举例关键工件法举例J1J2J3J4J5J6机器机器1pi15541210机器机器2pi25553610机器机器3pi3833474机器机器4pi4282156机器机器5pi5 5212810总和总和252315112840找出关键工件：工作负荷最大的找出关键工件：工作负荷最大的40，对应的是工件，对应的是工件6，所以，所以JC=J6确定排在关键工件前面的工件：满

28、足步骤确定排在关键工件前面的工件：满足步骤2条件的有条件的有J4, J5, 所以有所以有J4 J5 J6 确定排在关键工件后面的工件：满足步骤确定排在关键工件后面的工件：满足步骤3条件的有条件的有J2, J3, 所以有所以有 J6 J2 J3满足步骤满足步骤4条件的有条件的有J1, 所以有所以有 J6 J1， 或者或者J1 J6最后有：最后有：J4 J5 J6 J1 J2 J3 ， 或者或者 J4 J5 J1 J6 J2 J3第第5节节 服务业企业作业排序问题服务业企业作业排序问题 5.1 服务作业排序与生产作业排序的主要区别服务作业排序与生产作业排序的主要区别l l 所提供产品的类型所提供产

29、品的类型 由于服务过程有顾客参与由于服务过程有顾客参与,作业排序对他们有直接影响作业排序对他们有直接影响,并因此成为服务的并因此成为服务的一部分一部分,而在生产作业排序对产品的最终使用者没有直接影响而在生产作业排序对产品的最终使用者没有直接影响l l 排序内容排序内容 在服务业中在服务业中, 排序要定义服务交易的时间或消耗点；而在制造业中仅仅定排序要定义服务交易的时间或消耗点；而在制造业中仅仅定义产品生产的操作步骤义产品生产的操作步骤l l 过程控制过程控制 在服务业中在服务业中,顾客参与服务过程顾客参与服务过程,并且对全部操作过程施加影响并且对全部操作过程施加影响.l l 人员规模人员规模

30、在顾客化服务中在顾客化服务中,服务的输出与劳动力的最佳规模之间的关系很难确定；而服务的输出与劳动力的最佳规模之间的关系很难确定；而生产作业中生产作业中,两者之间的关系有紧密联系两者之间的关系有紧密联系,因此最佳的作业顺序可以被计算出来因此最佳的作业顺序可以被计算出来 5.2 服务作业排序方法之一服务作业排序方法之一安排顾客需求安排顾客需求 预约：如医生、律师等的服务预约：如医生、律师等的服务 预定：顾客预定旅馆房间、火车或飞机票预定：顾客预定旅馆房间、火车或飞机票 排队等待：一种为顾客排序的不太准确的方法是允许需排队等待：一种为顾客排序的不太准确的方法是允许需求积压，让顾客排队等待。例如，餐馆、银行、零售商求积压，让顾客排队等待。例如，餐馆、银行、零售商店等。店等。5.3 服务作业排序方法之二服务作业排序方法之二安排服务人员安排服务人员 当需要快速响应顾客需求、且需求量大致可以预计时，当需要快速响应顾客需求、且需求量大致可