第九章 作业计划

1、 主讲：薛建改主讲：薛建改 生产与运作管理生产与运作管理Production&OperationsManagement2022-2-3 生产作业计划概述 期量标准 生产作业计划的编制 作业排序 作业控制第九章 作业计划与控制2022-2-3 作 业 排 序排序和排队顾客顾客到达到达 服务设施服务设施顾客顾客排队排队顾客顾客离开离开2022-2-32022-2-3作业排序排序的目标对服务企业： 减少等待顾客的平均数量； 减少顾客在服务系统中的平均时间； 减少顾客在队列中的平均时间； 失售概率最小 提高设备利用率2022-2-3cba/满足交货期满足交货期缩短提前期缩短提前期降低准备成本降

2、低准备成本降低在制品库存降低在制品库存充分利用资源充分利用资源制造企业2022-2-3制造业作业排序 n个作业的单机排序(n/1/ Fmax) n个作业2台机器上的流水排序(n/2/ F / Fmax) n/m/P/Fmax问题的启发式算法 单件车间作业计划问题 相同零件不同移动方式下加工周期的计算2022-2-3作业排序的假设条件 一个工件不能同时在几台不同的机器上加工。 工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。 不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。 每道工序只在一台机器上完成。 工件数、机器数和加工时间已知，

3、加工时间与加工顺序无关。 每台机器同时只能加工一个工件。制造业作业排序 作业排序的表示法 1967年，康维(Conway R. W.)等人首先提出用4个参数表示排序问题的方法，即4参数表示法：n/m/A/B 式中：n作业数，m作业中心数，A车间类型，B目标函数。 在A的位置若标以“F”，则表示流水作业排序问题，若标以了“p”，则表示流水作业排列排序流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。在B的位置，通常是使目标函数达到最小。制造业作业排序2022-2-3 作业排序的优先准则 迄今，人们已经提出100多个派工法则，这里简要介绍4种 FCFS：First-Come-Firs

4、t-Service 优先选择最早进入可排工序集合的工件 SPT：Shortest-Processing-Time 优先选择加工时间最短的工件 EDD：Earliest-Due-Date 优先选择完工期限最短的工件 LPT：Longest Processing Time 优先选择加工时间最长的工件制造业作业排序四种排序方法的比较按LPT规则F-D-B-E-C-A四种派工法则的绩效比较方法平均流程时间(天)利用率(%)加工时间/流程时间平均在制品数（流程时间/加工时间）平均延迟时间（天）FCFS2034.22.939SPT18382.636.67EDD18.337.32.686.33LPT29.8

5、22.94.37182022-2-3四种排序法则特点FCFS对工件较公平，在顾客服务中很重要。但在多方面不具备优势SPT平均流程时间最短，平均在制品数量最少，缺点是加工时间较长的任务可能总是被排在后面，顾客可能产生不满EDD可使工件的平均延迟时间最小，其它方面也可以，对延迟罚款数量大时非常必要LPT各方面都很差包括平均流程时间、利用率、平均在制品数、平均延迟时间等2022-2-3制造业作业排序 n个作业的单机排序(n/1/ Fmax) n个作业2台机器上的流水排序(n/2/ F / Fmax) n/m/P/Fmax问题的启发式算法单件车间作业计划问题相同零件不同移动方式下加工周期的计算2022

6、-2-3作业排序的方法：n个作业的单机排序(n/1/ Fmax) 单机排序是作业排序中最简单、最基本的问题。当n个作业在一台设备上加工时，可能有n！种排序方案。目标：平均流程时间最小，最大拖期量最小或者为零。制造业作业排序2022-2-3 作业排序方法：n个作业2台机器上的流水排序(n/2/ F / Fmax) 约翰逊贝尔曼规则(Johnson-Bellmans Rule) 目标：是使从第一个作业开始到最后一个作业结束的总流程时间最短。 制造业作业排序BA2022-2-3制造业作业排序最长流程时间Fmax的计算 问题问题：nmP /Fmax， FmaxFmax为目标函数为目标函数：目标函数是使

7、最长流程时间最短，最长流程时间又称作加工周期。 假设：假设：所有工件的到达时间都为零(R(Ri i， i= 1 i= 1，2 2，n)n)， Fmax等于排在末位加工工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。r设设n n个工件的加工顺序为个工件的加工顺序为S S(S(S1 1，S S2 2，S S3 3，S Sn n) )，其中，其中S Si i为为第第i i位加工的工件的代号。位加工的工件的代号。 以表示工件以表示工件S Si i在机器在机器 M M k k上的上的完工时间完工时间, , 表示工件表示工件S Si i在在 M Mk k上的加工时间，上的加工时间，k= 1k=

8、 1，2 2，m m； i=1i=1，2 2，n n， 则可按以下公式计算：则可按以下公式计算： max max ， (9(91)1)k=2k=2，3 3，m m； i=1i=1，2 2，n n ；当；当r ri i =0 =0， i=1 i=1 2 2，n n 时时F Fmaxmax= = (9.2)(9.2) iskCkispiskCisC111isC1ispiskCiskC) 1( 1iskCkispnsmC式(91)是一个递推公式。当由式(9.1)得出时 ，Fmax就求得了。例： 有一个64pFmax 问题，其加工时间如表9-2所示。当按顺序S=(6，1，5，2，4，3)加工时，求 F

9、max 。表9-2 为其加工时间矩阵 i123456 Pi1423142 Pi2456745 Pi3587555 Pi4424331nsmC 615243Pi1244213pi2544576pi3555857pi4143234最长流水时间的计算机器工件Fmax =46261012131671213111520273317223035422125323846解：按顺序S=(6，l，5，2，4，3)列出加工时间矩阵，如表9-7所示。按式(91)进行，将每个工件的完工时间标在其加工时间的右上角。对于第一行第一列，只需把加工时间的数值作为完工时间标在加工时间的右上角。对于第一行的其它元素，只需从左到右

10、依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。对于从第二行到第m行，第一列的算法相同。只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要从本行前一列右上角和本列上一行的右上角数字中取大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为，也是Fmax。计算结果如表9-7所示。本例 Fmax=46。i 6 1 5 2 4 3 Pi1 22 46 410 212 113 316 Pi2 57 411 415 520 727 633 Pi3 512 517 522 8

11、30 535 742 Pi4 113 421 325 232 338 446 Johnson法则法则 著名的Johnson算法是SMJohnson于1954年提出了一个有效算法。为了叙述方便，以ai表示 Ji 在M1上的加工时间，以bi 表示Ji 在M2上的加工时间。每个工件都按M1 M2的路线加工。 如果 min(amin(ai i , b , bj j )min( a )min( aj j , b , bi i) ) （9.39.3） 则Ji应该排在Jj之前。如果中间为等号，则工件i既可排在工件j之前，也可以排在它之后。可以确定每两个工件的相对位置，从而可以得到n个工件的完整的顺序 步骤：

12、1.选择最短的作业时间；2.如果最短时间的作业在第1个加工中心，则安排在最前面，若在第2个加工中心，则安排在最后；3.在等待的队列中，取消第2步安排了的作业；4.重复1，2，3步。 例92 求下表所示的62/FFmax 问题的最优解。 加工时间矩阵i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 Johnson方法方法 将工件2排第1位 2 将工件3排第6位 2 3 将工件5排第2位 2 5 3 将工件6排第3位 2 5 6 3 将工件4排第5位 2 5 6 4 3 将工件1排第4位 2 5 6 1 4 3 最优加工顺序为s=(2，5，6，1，4，3)。求

13、得最优顺序下的Fmax=28。解法如下原则：原则：1.找找min，前道，前道工序工序-最前，后最前，后道工序道工序-最后最后2.若多个若多个min,任任选。选。i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 作业排序方法： n/m/P/Fmax问题的启发式算法 对于3 台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。 对于一般的流水车间排列排序问题，可以用分支定界法。用分支定界法可以保证得到一般n/m/P/ Fmax问题的最优解。 启发式算法：Palmer、关键工件法、CDS法,这里就不再一一介绍制造业作业排序2022-2-3单件车间作业

14、计划问题单件车间作业计划问题 单件车间作业的排序问题是最一般的排序问题，也是最复杂的一种排序问题。 对于一般的n/m/G/ Fmax 问题，可以用分支定界法或整数规划法求最优解。但它们都是无效算法，不能应用到生产实际中。启发式方法是求解一般单件车间排序问题使用最多的方法。制造业作业排序制造业作业排序2022-2-3相同零件不同移动方式下加工周期的计算 当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同。三种典型的移动方式如下： 顺序移动方式 平行移动方式 平行顺序移动方式制造业作业排序顺序移动方式顺序移动方式特点：指一批零件或产品在前道工序全部加工完成后，整批转移到后道工序加工的移动

15、方式。 例: 加工批量n4，工序数m4，各道工序时间 t110分 t2=5分t3=15分t4=10分 其顺序移动方式示意图如下： 求其加工周期10105 51515工序工序4 4工序工序3 3工序工序2 2工序工序1 1t t20 40 60 80 1020 40 60 80 100 120 140 1600 120 140 1601010 生产周期计算公式：生产周期计算公式：miitnT1顺 平行移动方式平行移动方式特点：指每个产品或零件在上道工序加工完后，立即转到下道工序加工，使各个零件或产品在各道 工序上的加工平行地进行。 生产周期计算公式：长平tntTmii)1(1t长：工序时间最长的

16、工序时间例： T平=（1051510）（41）15 404585t20 40 60 80 85 100 工序4工序3工序2工序1 平行移动方式示意图平行移动方式示意图平行顺序移动方式平行顺序移动方式特点：即一批零件或产品特点：即一批零件或产品, ,既保持每道工序的平行性，既保持每道工序的平行性，又保持连续性的作业移动方式。又保持连续性的作业移动方式。1010151510105 50 10 20 30 40 50 60 0 10 20 30 40 50 60 70 80 90 10070 80 90 10025 4525 45工序工序4 4工序工序3 3工序工序2 2工序工序1 1 一是当t前t

17、后时,则前道工序上完工的零件,并不立即转移到后道工序,而是积累到一定数量,足以保证后道工序能连续加工时,才将完工的零件全部转移到后道工序去。这样可避免后道工序出现间断性的设备停歇时间，并把分散的时间集中起来加以利用。以前道工序最后一个零件的完工时间为基准，往前推移（n-1） t后作为零件在后道工序的开始加工时间。 二是当t前t后时，则零件按平行移动方式移动。计算公式：111)1(miimiitntnT短平顺短it三种移动方式的比较优点缺点顺序移动1.组织与计划工作简单2.零件集中加工，集中运输，减少了设备调整时间和运输工作量；3.设备连续加工不停顿，提高了工效1.大多数产品有等待加工和等待运输

18、的现象，生产周期长；2.资金周转慢，经济效益较差。平行移动1.加工周期短2.在制品占用量少1.运输次数多2.当前后工序时间不相等时，存在设备中断和制品等待的情况平行顺序移动1.中断时间比顺序移动方式的少2.零件生产周期较短；3.使工人和设备的空间时间集中起来，组织管理比较复杂2022-2-32022-2-3需求群体需求群体排队结构排队结构服务结构服务结构不再有服不再有服务需求务需求与需求的时间分与需求的时间分布空间分布有关布空间分布有关到达过程到达过程退出退出排队规则排队规则服务服务过程过程2022-2-3需求群体需求群体同质群体同质群体异质群体异质群体2022-2-33.到达过程：通过记录顾

19、客实际到达情况可以确定顾客到达时间间隔的分布。大量调查表明顾客到达的时间间隔服从指数分布。 tetf)(式中 为顾客平均到达率为到达的时间间隔为自然对数的低数 te2022-2-32022-2-3 5.服务结构 单队单服务台单阶段的服务排队系统单队单服务台单阶段的服务排队系统 多队多服务台单阶段的服务排队系统多队多服务台单阶段的服务排队系统 单队多服务台单阶段的服务排队系统单队多服务台单阶段的服务排队系统 单队单服务台多阶段的服务排队系统单队单服务台多阶段的服务排队系统 单队多服务台多阶段的服务排队系统单队多服务台多阶段的服务排队系统2022-2-32022-2-31）利用预约系统 控制顾客到

20、达时间 实现最高程度的服务能力利用率 减少顾客等待的时间 提高服务水平2）采用预订系统 对特定期间的服务需求做出较准确的估计3）采用差异定价措施2022-2-3 1）进行有效的人员班次排序2）利用临时工或兼职人员3）招聘和培养多技能的员工4）对组织结构、体制与服务流程进行重组2022-2-3 生产作业计划概述 期量标准 生产作业计划的编制 作业排序 生产作业控制第九章 作业计划与控制2022-2-3实施生产作业控制的原因和条件 实行生产作业控制的原因 （1）加工时间估计不准确。 （2）随机因素的影响。 （3）加工路线的多样性。 （4）企业环境的动态性。生产作业控制2022-2-3 实施作业控制

21、有三个条件： 一是要有一个标准。 二是要取得实际生产进度与计划偏离的信息。 三是要能采取纠正偏差的行动。生产作业控制2022-2-3 1、单件小批生产 对于单件小批生产，排队时间是主要的，它大约占工件加工提前期的90到95。排队时间越长，在制品库存就越多。如果能够控制排队时间，也就控制了工件在车间的停留时间。要控制排队时间，实际是控制排队长度的问题。因此，如控制排队长度，是作业控制要解决的主要问题。 通过输入/输出控制，可以控制队长不同生产类型的控制特点2022-2-3 2、大量大批生产 大量大批生产的产品是标准化，通常采用流水线或自动线的组织生产。在流水线或自动线上，每个工件的加工顺序都是确

22、定的，工件在加工过程中没有排队，没有派工问题，也无优先权问题。因此，控制问题比较简单，主要通过改变工作班次，调整工作时间和工人数来控制产量。但是，在组织混流生产时，由于产品型号、规格和花色的变化，也要加强计划性，使生产均衡。不同生产类型的控制特点2022-2-3 （1）利用”漏斗模型”进行生产控制 (2)输人/输出控制报告。其控制的主要原则是，工作中心的输入永远不能超过工作中心的输出。 (3)调度单 调度单告诉主管当天哪些作业需要完工、这些作业的优先级以及作业时间。 (4)异常报告。异常报告告诉主管需要处理的特殊情况和问题。通常这这些报告每周提供一两次。 (5)状态报告。通常包括按期完工的作业数量和比例、延期并未完成的每批产出量等。废品报告和返工报告是两种典型的例子。生产作业控制的方法利用“漏斗模型”进行控制控制规则（调整输入、输出、在制品库存和通过时间）若想保持在制品库存稳定，就要使单位时间内的平均输入等于平均输出若希望改变在制品库存量，可暂时增加或减少输入若希望平均通过时间在所控制的范围内，