第九章 作业计划课件.ppt

;*;*;为什么会出现排队现象？;*;*;排序的目标;*;排 序 分 类;*;*; 作业排序的表示法 1967年，康维(Conway R. W.)等人首先提出用4个参数表示排序问题的方法，即4参数表示法：n/m/A/B 式中：n—作业数，m—作业中心数，A—车间类型，B—目标函数。 在A的位置若标以“F”，则表示流水作业排序问题，若标以了“p”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。在B的位置，通常是使目标函数达到最小。;*;四种排序方法的比较;按FCFS规则排序;按SPT规则;按EDD规则;按LPT规则;四种派工法则的绩效比较;*;*;*;*;*;设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。 以表示工件Si在机器 M k上的完工时间, 表示工件Si在 Mk上的加工时间，k= 1，2，…，m； i=1，2，…，n， 则可按以下公式计算： ＝ ＋ ＝max{ ， }＋ (9．1) k=2，3，…，m； i=1，2，…，n ；当ri =0， i=1 2，…，n 时 Fmax= (9.2) ; 式(9．1)是一个递推公式。当由式(9.1)得出时 ，Fmax就求得了。 例： 有一个6／4／p／Fmax 问题，其加工时间如表9-2所示。当按顺序S=(6，1，5，2，4，3)加工时，求 Fmax 。 表9-2 为其加工时间矩阵 i 1 2 3 4 5 6 Pi1 4 2 3 1 4 2 Pi2 4 5 6 7 4 5 Pi3 5 8 7 5 5 5 Pi4 4 2 4 3 3 1 ; ;解：按顺序S=(6，l，5，2，4，3)列出加工时间矩阵，如表9-7所示。按式(9．1)进行，将每个工件的完工时间标在其加工时间的右上角。对于第一行第一列，只需把加工时间的数值作为完工时间标在加工时间的右上角。对于第一行的其它元素，只需从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角。对于从第二行到第m行，第一列的算法相同。只要把上一行右上角的数字和本行的加工时间相加，将结果填在加工时间的右上角；从第2列到第n列，则要 ;从本行前一列右上角和本列上一行的右上角数字中取大者，再和本列加工时间相加，将结果填在本列加工时间的右上角。这样计算下去，最后一行的最后一列右上角数字，即为，也是Fmax。计算结果如表9-7所示。本例 Fmax=46。;Johnson法则; 步骤： 1.选择最短的作业时间； 2.如果最短时间的作业在第1个加工中心，则安排在最前面，若在第2个加工中心，则安排在最后； 3.在等待的队列中，取消第2步安排了的作业； 4.重复1，2，3步。 例9．2 求下表所示的6／2/F／Fmax 问题的最优解。 加工时间矩阵 ; 将工件2排第1位 2 将工件3排第6位 2 3 将工件5排第2位 2 5 3 将工件6排第3位 2 5 6 3 将工件4排第5位 2 5 6 4 3 将工件1排第4位 2 5 6 1 4 3 最优加工顺序为s=(2，5，6，1，4，3)。求得最优顺序下的Fmax=28。;作业排序方法： n/m/P/Fmax问题的启发式算法 对于3 台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。 对于一般的流水车间排列排序问题，可以用分支定界法。用分支定界法可以保证得到一般n/m/P/ Fmax问题的最优解。 启发式算法：Palmer、关键工件法、CDS法,这里就不再一一介绍;*;制造业作业排序;*;顺序移动方式;生产周期计算公式：; 平行移动方式;;平行顺序移动方式; 一是当t前﹥t后时,则前道工序上完工的零件,并不立即转移到后道工??,而是积累到一定数量,足以保证后道工序能连续加工时,才将完工的零件全部转移到后道工序去。这样可避免后道工序出现间断性的设备停歇时间，并把分散的时间集中起来加以利用。以前道工序最后一个零件的完工时间为基准，往前推移（n-1）× t后作为零件在后道工序的开始加工时间。 二是当t前≤t后时，则零件按平行移动方式移