《11章作业排序ppt课件.ppt》由会员分享，可在线阅读，更多相关《11章作业排序ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。
1、第11章制造作业计划与控制,第一节 排序问题的基本概念第二节 流水作业排序问题第三节 单件作业排序问题第四节 生产作业控制,第一节 作业计划和排序问题的基本概念,作业计划与作业排序是一回事么？,作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。编制作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。,根据排序规则对每一个到达的工件安排作业顺序,工作地,工件排队等待加工,来自上游工作地的工件,加工完毕的工件流向下一工作地,排序的概
2、念,排序的概念,生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货,名词术语(略),“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、钻、冲、磨的路线加工，我们可以用M1,M2,M3,M4来表示。“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题,排序问题的分类,参数表示法:,n /m /A /B。 其中, n 零件数； m 机器数； A 作业类型；在A的位置若标以“F”，则代表流水
3、作业排序问题。若标以“P”，则表示流水作业排列排序问题,即同顺序排序，所有零件在每台机器上的加工顺序相同。若标以“G”，则表示一般单件作业排序问题。当m1，则A处为空白 B目标函数，通常是使其值最小。,参数表示法:,n /m /P / Fmax所有零件在每台机器上的加工顺序相同。如在M1上都是第一道工序，M2上都是第二道工序。n /m /F / Fmax不同零件在每台机器上的加工顺序不同。如零件1在M1上不加工，在M2上才是第一道工序；而零件2在M1上是第一道工序。,第二节 流水作业排序问题,流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.只要加工路线一致：M1， M2,
4、 M3，.，Mm,不要求每个零件都经过每台机器加工我们要讨论的是排列排序问题。它不是流水线排序问题的最优解，但是比较好的解。,一、最长流程时间Fmax的计算,最长流程时间又称作加工周期例题：6/4/p/ Fmax问题，当按顺序S( 6,1,5,2,4,3)加工时，求Fmax.,加工周期为46,表2顺序S下的加工时间矩阵,i,6 1 5 2 4 3,i1,P,2,2,4,6,4,10,2,12,1,13,3,16,i2,5,7,4,11,4,15,5,20,7,27,6,33,5,12,5,17,5,22,8,30,5,35,7,42,1,13,4,21,3,25,2,32,3,38,4,46,
5、P,一、最长流程时间Fmax的计算,加工周期为37,表3顺序S下的加工时间矩阵,i,1 2 3 4 5 6,i1,P,3,3,3,6,4,10,2,12,1,13,3,16,i2,2,5,5,11,4,15,3,18,7,25,6,31,5,10,4,15,5,20,7,27,5,32,4,36,1,11,2,17,3,23,2,29,3,35,1,37,P,课堂作业：求Fmax.,二、n/2/F/Fmax问题的最优算法,（一）Johnson算法：从加工时间矩阵中找出最短的加工时间。若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后
6、，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个若所有零件都已排序，停止。否则，转步骤。,例题：求表11-3所示的6/2/F/Fmax问题的最优解。,最优加工顺序为S=（2，5，6，1，4，3）。,课堂作业： P345第1题,（二）算法步骤的改进,把Johnson算法作些改变，改变后的算法按以下步骤进行：将所有aibi的零件按ai值不减的顺序排成一个序列A。将所有aibi的零件按bi值不增的顺序排成一个序列B。将A放到B之前，就构成了最优加工顺序,序列A为 (2， 5，6，1)，序列B为(4，3)，构成最优顺序为 (2，5，6，1， 4，3)，与Johnson算法结
7、果一致。,表,11,-,4,改进算法,i,1,2,3,4,5,6,ai,5,1,8,5,3,4,bi,7,2,2,4,7,4,i,1,3,ai,5,8,bi,7,2,4,aibi， bi值不增,aibi， ai值不减,Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。对于一般的流水车间排列排序问题，可以用分支定界法。,三、求一般n/m/P/ Fmax问题近优解 (Near optimal so
8、lution)的启发式算法,1、Palmer法：按斜度指标排列工件的启发式算法 工件的斜度指标按下式计算：,m为机器数；Pik 为工件i在Mk 上的加工时间，k是机器编号，按照各工件i不增的顺序排列工件,可得出满意顺序,例：有一个4/3/P/ Fmax 问题，其加工时间如下表所示，用Palmer法求解。,=(1-2) Pi1+(2-2) Pi2+(3-2) Pi3=- P i1 + P i3,解,K=1,1 = - P 11 + P 13= -1+4 = 3 2 = -P21 + P23= -2 + 5= 3 3 =- P31 + P33 = -6 + 8 = 2 4 =-P 41+P43 =
9、 -3 + 2 = -1,按i不增的顺序排列，得到加工顺序（1，2，3，4）和（2，1，3，4）， 两者均为最优顺序，Fmax=28。,i =- P i1 + P i3,作业：P345第2题用Palmer法求解,2、关键工件法（1）计算每个工件的总加工时间，找出加工时间最长的工件C，将其作为关键工件；（2）对于余下的工件若Pi1Pim，则按Pi1不减的顺序排成一个序列Sa，若Pi1Pim，则按Pim不增的顺序排列成一个序列Sb。（3）顺序（ Sa，C，Sb）即为所求顺序。,关键工件法求近优解举例,表11-6用关键零件法求解,i2,P,i3,p,i,1、找出最长时间2、 Pi1Pim，则按Pi1
10、不减3、若Pi1Pim，则按Pim不增4、组成（ Sa，C，Sb）,1，2,3,5 ，4,作业：P345第3题用关键工件法求解,3、CDS法,Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(1)个加工顺序，取其中优者。,CDS法可以总结为： L=1时，求第1道和最后一道工序的加工时间矩阵L=2时，求前2道和后2道工序的加工时间和的矩阵L=3时，求前3道和后3道工序的加工时间和的矩阵L=4时，求前4道和后4道工序的加工时间和的矩阵L=m-1，求前m-1道和后m-1道工序的加工时间和的矩阵,如：用C
11、DS求机器数M为3时的加工顺序。首先，计算L=1时的加工时间，,再计算L=2时的加工时间，,和,当L1时，按Johnson算法得到加工顺序(1，2，3，4)，相应的Fmax28。 当L2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax29。所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。,表,11-7,用,CDS,法求解,i,1 2 3 4,P,i1,1 2 6 3,L=1,P,i3,4 5 8 2,P,i1,+P,i2,9 6 8 12,L=2,P,i2,+P,i3,12 9 10 11,四、相同零件、不同移动方式下加工周期的计算,零件在加工过程
12、中可以采用三种典型的移动方式： 顺序移动 平行移动 平行顺序移动,例：一批制品，批量n =4件，须经四道工序加工，各工序时间分别为：t1=10, t2=5, t3=15, t4=10。,n加工批量；m工序数目；ti工件在第i工序的单件工时；,四、相同零件、不同移动方式下加工周期的计算,一批零件在上道工序全部加工完毕后,才整批转移到下道工序加工。,n加工批量；m工序数目；ti工件在第i工序的单件工时；,工序,M1,M2,M3,M4,T顺序,t2,t1,t3,t4,时间,1、顺序移动方式:,顺序移动方式下的加工周期计算,顺序移动方式下的加工周期计算,每个零件在前道工序加工完毕后，立即转移到后道工序
13、去继续加工，形成前后工序交叉作业。,工序,T平行,时间,M1,M2,M3,M4,2、平行移动方式,t1,t2,t4,平行移动方式下的加工周期计算,要求每道工序连续进行，但又要求各道工序尽可能平行地加工。,工序,M1,M2,M3,M4,T平顺,t2,t1,t3,t4,时间,3、平行顺序移动方式,工序,M1,M2,M3,M4,T平顺,t2,t1,t3,t4,时间,第1种情况：ti ti+1 考虑平行性，实现交叉作业,按平行移动方式的原则加工，即工件加工完成后立刻转移到下一个工序，此处，第2个工序的第1个工件加工完成后立刻转移到第3个工序进行加工。,3、平行顺序移动方式,工序,M1,M2,M3,M4
14、,T平顺,t2,t1,t3,时间,第2种情况：ti ti+1 考虑设备加工的连续性,第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为第2个工序的开始时间。即从红线开始向前推3个作为第2个工序的开始时间。,3、平行顺序移动方式,x,T=nt1+t2+x+t4,X=nt3-(n-1)t2,T=n(t1+t2+t3+t4)-(n-1)(t2+t2+t4),Min(tj,tj+1)前后相邻两工序中单件工时之较小者,T=4(10+5+15+10)-(4-1) (5+5+10)=100分钟,工序,M1,M2,M3,M4,M5,T平顺,t2,t1,t3,时间,加工周期的计算,Min
15、(tj,tj+1)前后相邻两工序中单件工时之较小者,3、平行顺序移动方式,零件三种移动方式的比较,第三节 单件作业计划问题,是十分复杂的一种作业计划问题，内容和方法描述 n个零件在m台机器上进行作业，使加工时间最短的单件作业排序结果表示实质是任务分配问题：匈牙利算法,一、任务分配：匈牙利算法流程,例：如右表，请用匈牙利法求出任务分配 解：,例题,1、每行所有元素减去该行最小元素。,2、每列所有元素减去该列最小元素。,3、划出能覆盖尽可能多的0元素的直线，如果线条数等于矩阵列数，则找到最优解。否则继续。,4、没被线条穿过的元素减去这些元素中的最小数。并将这个最小数加到直线交叉的元素上。然后重复3
16、、4,5、从仅有一个0元素的行或列开始，最后使每行和每列都有一个0元素。,0元素对应的就是最优分配方案。,结果矩阵表示：零件1由机器3加工（J1M3） 零件2由机器2加工 (J2M2) 零件3由机器4加工 (J3M4) 零件4由机器1加工 (J4M1),结果,二、单件作业排序问题的描述,用（i，j，k）表示工件i 的第j道工序在机器k上进行。i表示工件代号j表示工序号k表示完成任务的机器代号。如加工描述矩阵D。,三、优先派工法则,按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。 迄今，人们已提出了100多个优先调度法则，其
17、中主要的有下4个：FCFS(First Come First Served)法则优先选择最早进入可排工序集合的工件。SPT(Shortest Processing Time)法则优先选择加工时间最短的工序。EDD(Earliest Due Date)法则优先选择完工期限紧的工件。LPT(Longest Processsing Time)法则优先选择加工时间最长的工件。,四、一般n/m/G/Fmax问题的算法,1、符号说明Stt步之前已排序工序构成的部分作业计划； Ot 第t步可以排序的工序的集合；Tk Ot 中工序Ok的最早可能开工时间；Tk Ot 中工序Ok的最早可能完工时间。,作业计划构成
18、分类,能动作业计划：各工序按最早可能完工时间安排的作业计划。无延迟作业计划：各工序按最早可能开工时间安排的作业计划。,2、能动作业计划的构成步骤:,设t1，S1为空集，O1为各工件第一道工序的集合。求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。Tk最早完成时间.从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TkT*。 Tk最早开工时间.将确定的工序Oj放入St，从 Ot 中消去Oj，并将Oj的紧后工序放入 Ot ，使tt1。若还有未安排的工序，转步骤；否则，停止。,例题：,有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：,试构成一
19、个能动作业计划。,2,3,2,M2,13,13,8,2,3,2,6,1,3,2,M2,8,812,77,1,3,22,3,2,5,2,2,1,M1,7,87,73,1,3,22,2,1,4,1,2,3,M3M1,7,77,33,1,2,32,2,1,3,2,1,3,M3,3,63,20,1,2,32,1,3,2,1,1,1,M1,2,23,0 0,1,1,12.1.3,1,Qj,M*,T*,Tk,Tk,Qt,t,解：Tk最早开工时间；Tk=最早完成时间；T*=最早完工时间中的最小者,1,1,1 1,2,3 1,3,2,D,2,1,3 2,2,1 2,3,2,最优作业计划为：1,1,1 2,1,
20、3 1,2,3 2,2,1 1,3,2 2,3,2,3、无延迟作业计划的构成步骤:,设t1，S1为空集，O1为各工件第一道工序的集合。求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选一台。Tk最早开始时间.从Ot中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TkT*。将确定的工序Oj放入St，从 Ot 中消去Oj，并将Oj的紧后工序放入 Ot ，使tt1。若还有未安排的工序，转步骤；否则，停止。,1,3,2,M2,12,13,12,1,3,2,6,2,3,2,M2M2,77,812,77,1,3,22,3,2,5,2,2,1,M1,3,87,73,1,3,22,2,1
21、,4,1,2,3,M3M1,33,77,33,1,2,32,2,1,3,2,1,3,M3,0,63,20,1,2,32,1,3,2,1,1,1,M1M3,00,23,0 0,1,1,12.1.3,1,Qj,M*,T*,Tk,Tk,Qt,t,解：,Tk最早开工时间；Tk=最早完成时间；T*=最早开工时间中的最小者,最优作业计划为：1,1,1 2,1,3 1,2,3 2,2,1 2,3,2 1,3,2,三类启发式算法,1、MWKR(Most Work Remaining)法则优先选择余下加工时间最长的工件。2、LWKR(Least Work Remaining)法则优先选择余下加工时间最短的工件。3、MOPNR(Most Operations Remaining)法则优先选择余下工序数最多的工件。4、SCR(Smallest Critical Ratio)法则优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。5、RANDOM法则随机地挑一个工件,判断题第2小题除外；选择题第1、2、4题。计算第2题。,
