生产作业计划教材

第八章生产作业计划

OperationsSchedulingandControlling第一节生产作业排序第二节生产作业控制第一节生产作业排序

一、基本概念1、排序排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。排序的作用油漆生产顺序：某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？复印排序问题：有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？方案1：白-灰-红-蓝T-setup=12

方案2：蓝-红-灰-白T-setup=20排序中常用的几个概念工件（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的加加工工时时间间,Wi----工件件i在系系统统内内的的等等待待时时间间,wij----工工件件i在在机机器器j前前的的等等待待时时间间,j=1,……,mCi----工件件i的完完成成时时间间,在在工工件件都都已已到到达达的的情情况况下下,Ci=Pi+WiFi----工件件i的流流程程时时间间，在工工件件都都已已到到达达的的情情况况下下,Fi=Pi+WiLi----工件件i的延延误误时时间间,Li=Ci-di,Li<=0按期期或或完完成成提提前前；Li>0延误误Ti----工件件i的延延期期量量,Ti=max{0,Li}Ei----工件件i提前前完完成成的的时时间间5、、排排序序问问题题的的假假设设条条件件工件件同同时时到到达达。。一个个工工件件不不能能同同时时在在几几台台不不同同的的机机器器上上加加工工。。工件件在在加加工工过过程程中中采采取取平平行行移移动动方方式式。。不允允许许中中断断。。每道道工工序序只只在在一一台台机机器器上上完完成成。。每台台机机器器同同时时只只能能加加工工一一个个工工件件。。工件件数数、、机机器器数数和和加加工工时时间间已已知知，，加加工工时时间间与与加加工工顺顺序序无无关关。。二、、两两台台机机器器的的排排序序问问题题1、、两两台台机机器器排排序序问问题题的的含含义义n个工工件件都都必必须须经经过过机机器器1和和机机器器2的的加加工工，，即即工工艺艺路路线线是是一一致致的的。。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器22、、最最长长流流程程时时间间最长长流流程程时时间间（（加加工工周周期期Fmax））：：从从第第一一个个工工件件在在第第一一台台机机器器上上加加工工起起到到最最后后一一个个工工件件在在最最后后一一台台机机器器上上加加工工完完毕毕为为止止所所经经过过的的时时间间。。Fmax时间

机器A

B在机器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项任务务，各任务的的工艺顺序相相同，资料如如下：求最优解条件件，满足如下下条件之一：：求解步骤：1、把三台设设备转换为两两台假象设备备，假想设备备加工时间按如下下公式转换：：任务j1j2j3j4j5j6j7j8Mgtgj131015171111155Mhthj2220222421151516用约-贝规则则求得排序结结果如下：J8-J2-J5-J6-J1-J3-J7-J4；(或：-J4-J7）上例中，满足足条件转换两台假想想设备，结果果如下表：三、一般n/m/P/Fmax问问题的启发式式算法对于一般的n/m/P/Fmax问问题，可以用用分支定界法法求得最优解解，但计算量量很大。实际际中，可以用用启发式算法法求近优解。。1、Palmer法计算工件斜度度指标i：m:机器器数pik：工件i在机机器k上的加加工时间。i=1,2,,n排序方法:按按i从大到小的顺顺序排列。按排序的顺序序计算Fmax2、关键工件件法：计算Pi=Pij，找出Pi最长的工件，，将之作为关关键工件C。。对其余工件，，若Pi1≤Pim，则按Pi1由小到大排成成序列SA。若Pi1>Pim，则按Pim由大到小排成成序列SB。顺序（SA，C，SB）即为近优解解。得到的加工顺顺序为(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个个排序中找出出近优解。L＝1，按Johnson算法得到到加工顺序(1，2，3，4)，Fmax＝28L＝2，按Johnson算法得到到加工顺序(2，3，1，4)，Fmax＝29取顺序(1，，2，3，4）为最优顺顺序。四、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加工时间交货日期流程时间延期交货时间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、最短松弛弛时间先加工工（LS）加工顺序加工时间交货日期流程时间延期交货时间EABD1=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、顺序移动动方式一批零件在上上道工序全部部加工完毕后后才整批地转转移到下道工工序继续加工工。优点：设备利利用率高；移移动次数少缺点：加工周周期长；管理理工作复杂常用于单件或或成批生产过过程——工艺艺原