第八章生产作业计划

第八章生产作业计划OperationsSchedulingandControlling第一节生产作业排序第二节生产作业控制第一节生产作业排序一、基本概念1、排序•排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。•实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。•排序的作用–油漆生产顺序：某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？–复印排序问题：有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？•方案1：白-灰-红-蓝T-setup=12方案2：蓝-红-灰-白T-setup=20白灰红蓝白0123灰5012红7601蓝9860排序中常用的几个概念•工件（Job）：服务对象；•机器（Machine、Processor）：服务者。如：•n个零件在机器上加工，则零件是工件，设备是机器；•工人维修设备，出故障的设备是工件，工人是机器。所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如可用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。2、作业计划（Scheduling）•作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。•作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。•如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。3、排序问题的分类与表示•根据机器数的多少单台机器的排序问题多台机器的排序问题•根据加工路线的特征单件作业排序(JobShop)流水型排序(FlowShop)流水作业排序问题的基本特征：•每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。•不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。单件车间排序问题的基本特征：•每个工件都有其独特的加工路线，工件没有一定的流向。表示方法一般正规的表示方法为：n/m/A/Bn：工件数；m：机器数；A：作业类型（F、P、G）；B：目标函数4、排序常用的符号Ji----工件i，i=1,2,....nMj----机器,j=1,2…mdi----工件i的交货期pij----工件i在机器j上的加工时间,j=1,…,mPi----工件i的加工时间,mjijipP1mjijiwW1Wi----工件i在系统内的等待时间,wij----工件i在机器j前的等待时间,j=1,…,mCi----工件i的完成时间,在工件都已到达的情况下,Ci=Pi+WiFi----工件i的流程时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件i的延误时间,Li=Ci-di,Li=0按期或完成提前；Li0延误Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的时间5、排序问题的假设条件•工件同时到达。•一个工件不能同时在几台不同的机器上加工。•工件在加工过程中采取平行移动方式。•不允许中断。•每道工序只在一台机器上完成。•每台机器同时只能加工一个工件。•工件数、机器数和加工时间已知，加工时间与加工顺序无关。二、两台机器的排序问题1、两台机器排序问题的含义•n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器22、最长流程时间•最长流程时间（加工周期Fmax）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。Fmax时间机器AB在机器A上的作业时间总加工周期•假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。•计算Fmax的几个假定条件：–机器M1不会发生空闲；–对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。3、Fmax问题的算法•两台机器排序的目标是使Fmax最短。•假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1—M2的路线加工。•Johnson算法：–从加工时间矩阵中找出最短的加工时间。–若最短时间出现在M1上，则对应的工件尽可能往前排。–若最短时间出现在M2上，则对应的工件尽可能往后排。–若最短时间有多个，则任选一个。–划去已排序的工件。–若所有工件都已排序，则停止，否则重复上述步骤。例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。工件在两台设备上的加工时间工件编号J1J2J3J4J5设备A36715设备B28643解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得：J4-*-*-*-*去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即：J4-*-*-*-J1再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J530AB26AB(b)J4-J2-J3-J5-J1可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优于前者。任务j1j2j3j4j5j6j7j8Mataj235867123Mbtbj1171095432Mctcj1113121516111214N项任务、三台设备的排序例：三台设备、8项任务，各任务的工艺顺序相同，资料如下：•求最优解条件，满足如下条件之一：jbjcjbjatttt,,,,maxminmaxmin•求解步骤：•1、把三台设备转换为两台假象设备，假想设备加工时间按如下公式转换：jbjcjhjbjajgtttttt,,,,,,任务j1j2j3j4j5j6j7j8Mgtgj131015171111155Mhthj2220222421151516用约-贝规则求得排序结果如下：J8-J2-J5-J6-J1-J3-J7-J4；(或：-J4-J7）上例中，满足条件jbjctt,,maxmin转换两台假想设备，结果如下表：三、一般n/m/P/Fmax问题的启发式算法对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。1、Palmer法•计算工件斜度指标i：m:机器数pik：工件i在机器k上的加工时间。i=1,2,,n•排序方法:按i从大到小的顺序排列。•按排序的顺序计算Fmaxm1kikip]2/)1m(k[2、关键工件法：•计算Pi=Pij，找出Pi最长的工件，将之作为关键工件C。•对其余工件，若Pi1≤Pim，则按Pi1由小到大排成序列SA。若Pi1Pim，则按Pim由大到小排成序列SB。•顺序（SA，C，SB）即为近优解。用关键工件法求解i1234Pi11263Pi28429Pi34582pi13111614得到的加工顺序为(1，2，3，4)•关键工件法举例J1J2J3J4J5J6机器1pi15541210机器2pi25553610机器3pi3833474机器4pi4282156机器5pi55212810总和252315112840找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6确定排在关键工件前面的工件：满足步骤2条件的有J1,J4,J5,所以有SA=J4–J5–J1确定排在关键工件后面的工件：满足步骤3条件的有J2,J3,所以有SB=J2–J3最后有：J4–J5–J1–J6–J2–J33、CDS法：•CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。加工顺序A加工时间B加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tm……………m-1t1+t2+…+tm-1t2+…+tm-1+tm•L＝1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax＝28•L＝2，按Johnson算法得到加工顺序(2，3，1，4)，Fmax＝29•取顺序(1，2，3，4）为最优顺序。用CDS法求解i1234Pi11263L=1Pi34582Pi1+pi296812L=2Pi2+pi31291011四、N个零件在某个加工中心的排序排序的优先规则主要有：先到的先服务（FCFS）加工时间短的优先加工（SPT）交货期早的先加工（EDD）最短松弛时间先加工（LS）(某项任务距计划交货期的剩余时间与该任务的作业时间之差)随机加工比较研究：例：有5个任务到达，原始排序是任务到达顺序加工时间/天交货期/天ABCDE34261567921、先到的先服务（FCFS）加工顺序加工时间交货日期流程时间延期交货时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16——12614总流程时间=3+7+9+15+16=50(天)平均流程时间=50/5=10（天）平均延迟时间=(1+2+6+14)/5=4.6(天)2、加工时间短的优先加工（SPT）加工顺序加工时间交货日期流程时间延期交货时间ECABD12346275690+1=11+2=33+3=66+4=1010+6=16——-----147总流程时间=1+3+6+10+16=36(天)平均流程时间=36/5=7.2（天）平均延迟时间=(1+4+7)/5=2.4(天)3、交货期早的先加工（EDD）加工顺序a加工时间交货日期流程时间延期交货时间EABCD13426256790+1=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、最短松弛时间先加工（LS）加工顺序加工时间交货日期流程时间延期交货时间EABDC13462256970+1=11+3=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、顺序移动方式一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。优点：设备利用率高；移动次数少缺点：加工周期长；管理工作复杂常用于单件或成批生产过程——工艺原则T顺=nt1+nt2+…+ntn=nti时间工序n=4件，m=4工序t1=10分钟/件，t2=5分钟/件，t3=20分钟/件，t4=10分钟/件总加工周期T顺2、平行移动方式每个零件在前道工序加工完毕后立即转移到下道工序继续加工，形成前后工序交叉作业。优点：加工周期短；管理工作简单缺点：设备利用率低；移动次数多常用于装配流水线、大量生产过程——对象原则T平=ti+（n-1）tl时间工序总加工周期T平n=4件，m=4工序t1=10分钟/件，t2=5分钟/件，t3=20分钟/件，t4=10分钟/件3、平行顺序移动方式要求：每道工