《生产作业计划教材》由会员分享，可在线阅读，更多相关《生产作业计划教材（47页珍藏版）》请在金锄头文库上搜索。
1、第八章 生产作业计划 Operations Scheduling and Controlling,第一节 生产作业排序 第二节 生产作业控制,第一节 生产作业排序 一、基本概念,1、排序 排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。 实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。,排序的作用 油漆生产顺序：某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？ 复印排序问题：有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最
2、小？,方案1：白-灰-红-蓝 T-setup=12 方案2：蓝-红-灰-白 T-setup=20,排序中常用的几个概念 工件（Job）：服务对象； 机器（Machine、Processor）：服务者。,如： n个零件在机器上加工，则零件是工件，设备是机器； 工人维修设备，出故障的设备是工件，工人是机器。,所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如可用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。,2、作业计划（Scheduling） 作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。 作业计划与排
3、序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。,3、排序问题的分类与表示 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件作业排序(Job Shop) 流水型排序(Flow Shop),流水作业排序问题的基本特征： 每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。 不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺
4、序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。,单件车间排序问题的基本特征： 每个工件都有其独特的加工路线，工件没有一定的流向。,表示方法 一般正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：作业类型（F、P、G）；B：目标函数,4、排序常用的符号 Ji-工件i，i=1,2,n Mj -机器,j=1,2m di-工件i的交货期 pij-工件i在机器j上的加工时间,j=1,m Pi-工件i的加工时间,Wi-工件i在系统内的等待时间, wij-工件i在机器j前的等待时间, j=1,m,Ci-工件i的完成时间, 在工件都已到达的情况下
5、, Ci= Pi+ Wi Fi-工件i的流程时间，在工件都已到达的情况下, Fi= Pi+ Wi Li-工件i的延误时间, Li= Ci- di , Li0 延误 Ti-工件i的延期量, Ti=max0, Li Ei-工件i提前完成的时间,5、排序问题的假设条件 工件同时到达。 一个工件不能同时在几台不同的机器上加工。 工件在加工过程中采取平行移动方式。 不允许中断。 每道工序只在一台机器上完成。 每台机器同时只能加工一个工件。 工件数、机器数和加工时间已知，加工时间与加工顺序无关。,二、两台机器的排序问题,1、 两台机器排序问题的含义 n个工件都必须经过机器1和机器2的加工，即工艺路线是一致
6、的。,2、最长流程时间 最长流程时间（加工周期Fmax ）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。,假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。 计算Fmax的几个假定条件： 机器M1不会发生空闲； 对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。,3、 Fmax问题的算法 两台机器排序的目标是使Fmax最短。 假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。,Johnson算法：
7、从加工时间矩阵中找出最短的加工时间。 若最短时间出现在M1上，则对应的工件尽可能往前排。 若最短时间出现在M2上，则对应的工件尽可能往后排。 若最短时间有多个，则任选一个。 划去已排序的工件。 若所有工件都已排序，则停止，否则重复上述步骤。,例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。,解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单
8、位，它是出现在设备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,(b) J4 - J2 - J3- J5 - J1,可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺序总加工周期是26，显然后者的结果优
9、于前者。,N项任务、三台设备的排序 例：三台设备、8项任务，各任务的工艺顺序相同，资料如下：,求最优解条件，满足如下条件之一：,求解步骤： 1、把三台设备转换为两台假象设备，假想设备加 工时间按如下公式转换：,用约-贝规则求得排序结果如下：,J8-J2-J5-J6-J1-J3-J7-J4；(或：-J4-J7）,上例中，满足条件,转换两台假想设备，结果如下表：,三、一般n/m/P/ Fmax问题的启发式算法,对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。,1、Palmer法 计算工件斜度指标i ： m : 机器数 pik ：工件i
10、在机器k上的加工时间。 i=1,2,n 排序方法: 按i从大到小的顺序排列。 按排序的顺序计算Fmax,2、关键工件法： 计算Pi= Pij ，找出Pi最长的工件，将之作为关键工件C。 对其余工件，若Pi1Pim ，则按Pi1由小到大排成序列SA。若Pi1 Pim ，则按Pim由大到小排成序列SB。 顺序（SA，C，SB）即为近优解。,得到的加工顺序为 (1，2，3，4),关键工件法举例,找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6,确定排在关键工件前面的工件：满足步骤2条件的有J1, J4, J5, 所以有SA =J4 J5 J1,确定排在关键工件后面的工件：满足步骤3条
11、件的有J2, J3, 所以有SB = J2 J3,最后有：J4 J5 J1 J6 J2 J3,3、CDS法： CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。,L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28 L2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax29 取顺序(1，2，3，4）为最优顺序。,四、N个零件在某个加工中心的排序 排序的优先规则主要有： 先到的先服务（FCFS） 加工时间短的优先加工（SPT） 交货期早的先加工（EDD） 最短松弛时间先加工（LS） (某项任务距计划交货期的剩余时间与该任务的作业时间之差) 随机加
12、工,比较研究： 例：有5个任务到达，原始排序是,1、先到的先服务（FCFS）,2、加工时间短的优先加工（SPT）,3、交货期早的先加工（EDD）,4、最短松弛时间先加工（LS）,优先调度规则比较,零件在加工过程中的移动方式，包括： 顺序移动方式； 平行移动方式； 平行顺序移动方式。,五、相同零件、不同移动方式下加工周期的计算,1、顺序移动方式 一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。 优点：设备利用率高；移动次数少 缺点：加工周期长；管理工作复杂 常用于单件或成批生产过程工艺原则,T顺=n t1+ n t2 + +n tn = n ti,2、平行移动方式 每个零件在前道
13、工序加工完毕后立即转移到下道工序继续加工，形成前后工序交叉作业。 优点：加工周期短；管理工作简单 缺点：设备利用率低；移动次数多 常用于装配流水线、大量生产过程对象原则,T平= ti + （n-1）tl,n=4件， m=4 工序 t1=10分钟/件，t2=5分钟/件， t3=20分钟/件，t4=10分钟/件,3、平行顺序移动方式 要求： 每道工序连续进行加工； 各道工序尽可能平行地加工； 目的：综合顺序移动和平行移动的优点。,T平顺= n ti （n-1）min tj，tj+1,n=4件， m=4 工序 t1=10分钟/件，t2=5分钟/件， t3=20分钟/件，t4=10分钟/件,4、三种移动方式的比较 从生产周期、运输次数、设备利用、组织管理四个方面进行比较。,
