第八章生产作业计划

1、第八章第八章 生产作业计划生产作业计划 Operations Scheduling and Controlling第一节第一节 生产作业排序生产作业排序第二节第二节 生产作业控制生产作业控制 第一节第一节 生产作业排序生产作业排序一、基本概念一、基本概念1、排序、排序 排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。 实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。 排序的作用排序的作用 油漆生产顺序：油漆生产顺序：某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？

2、复印排序问题：复印排序问题：有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？ 方案1：白-灰-红-蓝 T-setup=12方案2：蓝-红-灰-白 T-setup=20白白灰灰红红蓝蓝白白0123灰灰5012红红7601蓝蓝9860排序中常用的几个概念排序中常用的几个概念 工件（Job）：服务对象； 机器（Machine、Processor）：服务者。如： n个零件在机器上加工，则零件是工件，设备是机器； 工人维修设备，出故障的设备是工件，工人是机器。 所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如可用（1

3、，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。2、作业计划（、作业计划（Scheduling） 作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。 作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。3、排序问题的分类与表示、排序问题的分类与表示 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件作业排序(Job Shop) 流水型排序(Flow Shop)流水作业排序问题的基本特征

4、：流水作业排序问题的基本特征： 每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。 不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。单件车间排序问题的基本特征：单件车间排序问题的基本特征： 每个工件都有其独特的加工路线，工件没有一定的流向。表示方法表示方法 一般正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：作业类型（F、P、G）；B：目标函数 4、排序常用的符号

5、、排序常用的符号 Ji-工件i，i=1,2,.n Mj -机器,j=1,2m di-工件i的交货期 pij-工件i在机器j上的加工时间,j=1,m Pi-工件i的加工时间, mjijipP1mjijiwW1 Wi-工件i在系统内的等待时间, wij-工件i在机器j前的等待时间, j=1,m Ci-工件i的完成时间, 在工件都已到达的情况下, Ci= Pi+ Wi Fi-工件i的流程时间，在工件都已到达的情况下, Fi= Pi+ Wi Li-工件i的延误时间, Li= Ci- di , Li0 延误 Ti-工件i的延期量, Ti=max0, Li Ei-工件i提前完成的时间5、排序问题的假设条件

6、、排序问题的假设条件 工件同时到达。 一个工件不能同时在几台不同的机器上加工。 工件在加工过程中采取平行移动方式。 不允许中断。 每道工序只在一台机器上完成。 每台机器同时只能加工一个工件。 工件数、机器数和加工时间已知，加工时间与加工顺序无关。二、两台机器的排序问题二、两台机器的排序问题1、 两台机器排序问题的含义两台机器排序问题的含义 n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。 机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器22、最长流程时间、最长流程时间 最长流程时间（加工周期Fmax ）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工

7、完毕为止所经过的时间。Fmax 时间 机器 A B在机器A上的作业时间总加工周期 假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。 计算Fmax的几个假定条件： 机器M1不会发生空闲； 对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。3、 Fmax问题的算法问题的算法 两台机器排序的目标是使Fmax最短。 假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。 Johnson算法：算法： 从加工时间矩阵中找出最短的加工时间。 若最短时间出现在

8、M1上，则对应的工件尽可能往前排。 若最短时间出现在M2上，则对应的工件尽可能往后排。 若最短时间有多个，则任选一个。 划去已排序的工件。 若所有工件都已排序，则停止，否则重复上述步骤。例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。 工件在两台设备上的加工时间工件编号 J1 J2 J3 J4 J5设备A 3 6 7 1 5设备B 2 8 6 4 3解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉

9、J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得J4 - J2 - J3- J5 - J1(a) J1 - J2 - J3- J4 - J5 30AB26AB(b) J4 - J2 - J3- J5 - J1 可以看出，初始作业顺序的总加

10、工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。任务j1j2j3j4j5j6j7j8 Ma taj23 5867123 Mb tbj1171095432Mc tcj1113121516111214 求最优解条件，满足如下条件之一：jbjcjbjatttt,maxminmaxmin 求解步骤： 1、把三台设备转换为两台假象设备，假想设备加 工时间按如下公式转换：jbjcjhjbjajgtttttt, 任 务j1j2j3j4j5j6j7j8 Mg tgj131015171111155 Mh thj2220222421151516jbjctt,maxmin三、一般三、

11、一般n/m/P/ Fmax问题的问题的启发式算法启发式算法 对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。1 1、PalmerPalmer法法 计算工件斜度指标计算工件斜度指标 i i ： m : m : 机器数机器数 p pikik ：工件：工件i i在机器在机器k k上的加工时间。上的加工时间。 i=1,2,i=1,2,n,n 排序方法排序方法: : 按按 i i从大到小的顺序排列。从大到小的顺序排列。 按排序的顺序计算按排序的顺序计算FmaxFmaxm1kikip2/ ) 1m(k2 2、关键工件法、关键工件法： 计算Pi

12、= Pij ，找出Pi最长的工件，将之作为关键工件C。 对其余工件，若Pi1Pim ，则按Pi1由小到大排成序列SA。若Pi1 Pim ，则按Pim由大到小排成序列SB。 顺序（SA，C，SB）即为近优解。用用关关键键工工件件法法求求解解i 1 2 3 4Pi1 1 2 6 3Pi2 8 4 2 9Pi3 4 5 8 2pi 13 11 16 14得到的加工顺序为得到的加工顺序为 (1，2，3，4)关键工件法举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi5 5212810总和252315112840找出

13、关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6确定排在关键工件前面的工件：满足步骤2条件的有J1, J4, J5, 所以有SA =J4 J5 J1确定排在关键工件后面的工件：满足步骤3条件的有J2, J3, 所以有SB = J2 J3最后有：J4 J5 J1 J6 J2 J33 3、CDS法法： CDS法法是Johnson算法算法的扩展方法，从M-1个排序中找出近优解。加工顺序 A 加工时间 B 加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm L1，按Johnson算法得到加工顺序(1，2，3，

14、4)，Fmax28 L2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax29 取顺序(1，2，3，4）为最优顺序。用用 CDS 法求解法求解i 1 2 3 4Pi1 1 2 6 3L=1Pi3 4 5 8 2Pi1+pi2 9 6 8 12L=2Pi2+pi3 12 9 10 11四、四、N N个零件在某个加工中心的个零件在某个加工中心的排序排序排序的优先规则主要有：先到的先服务（FCFSFCFS）加工时间短的优先加工（SPTSPT）交货期早的先加工（EDDEDD）最短松弛时间先加工（LSLS）(某项任务距计划交货期的剩余时间与该任务的作业时间之差)随机加工比较研究：例：有5个

15、任务到达，原始排序是任务到达顺序 加工时间/天 交货期/天ABCDE34261567921 1、先到的先服务、先到的先服务（FCFS）加工顺序加工时间交货日期流程时间延期交货时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=1612614总流程时间=3+7+9+15+16=50(天)平均流程时间=50/5=10（天）平均延迟时间=(1+2+6+14)/5=4.6(天) 2 2、加工时间短的优先加工、加工时间短的优先加工（SPT）加工顺序加工时间交货日期流程时间延期交货时间ECABD12346275690+1=11+2=33+3=66+4=1010+6=16-

16、147总流程时间=1+3+6+10+16=36(天)平均流程时间=36/5=7.2（天）平均延迟时间=(1+4+7)/5=2.4(天)3 3、交货期早的先加工、交货期早的先加工（EDD）加工顺序a加工时间交货日期流程时间延期交货时间EABC1=11+3=44+4=88+2=1010+6=16-237总流程时间=1+4+8+10+16=39(天)平均流程时间=39/5=7.8（天）平均延迟时间=(2+3+7)/5=2.4(天)4 4、最短松弛时间先加工、最短松弛时间先加工（LS）加工顺序加工时间交货日期流程时间延期交货时间EABD1=11+3=

17、44+4=88+6=1414+2=16-259总流程时间=1+4+8+14+16=43(天)平均流程时间=43/5=8.6（天）平均延迟时间=(2+5+9)/5=3.2(天)优先调度规则比较优先调度规则比较规则总的完成时间平均完成时间平均延期FCFS50104.6SPT367.22.4EDD397.82.4LS438.63.2零件在加工过程中的移动方式，零件在加工过程中的移动方式，包括： 顺序移动方式； 平行移动方式； 平行顺序移动方式。五、相同零件、不同移动方式五、相同零件、不同移动方式下加工周期的计算下加工周期的计算1 1、顺序移动方式、顺序移动方式 一批零件在上道工序全部加工完毕后才整批

18、地转移到下道工序继续加工。 优点：设备利用率高；移动次数少 缺点：加工周期长；管理工作复杂 常用于单件或成批生产过程工艺原则T顺顺=n t1+ n t2 + +n tn = n ti时间时间工序工序n=4件， m=4 工序t1=10分钟/件，t2=5分钟/件，t3=20分钟/件，t4=10分钟/件总加工周期T顺2 2、平行移动方式、平行移动方式 每个零件在前道工序加工完毕后立即转移到下道工序继续加工，形成前后工序交叉作业。 优点：加工周期短；管理工作简单 缺点：设备利用率低；移动次数多 常用于装配流水线、大量生产过程对象原则T平平= ti + （n-1）tl时间时间工序工序总加工周期T平平n=4件， m=4 工序t1=10分钟/件，t2=5分钟/件，t3=20分钟/件，t4=10分钟/件 3 3、平行顺序移动方式、平行顺序移动方式 要求： 每道工序连续进行加工； 各道工序尽可能平行地加工；