生产作业排序的问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,),生产作业排序,一、基本概念,二、最长流程时间,三、n/2/F/F,max,问题的算法,四、一般n/m/P/F,max,问题的启发式算法,五、单件车间排序问题,生产作业排序一、基本概念,一、基本概念,1、排序,排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。,实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。,一、基本概念1、排序,一、基本概念,排序中常用的几个概念,工件（Job）：服务对象；,机器（Machine、Processor）：服务者。,如：,n个零件在机器上加工，则零件是工件，设备是机器；,工人维修设备，出故障的设备是工件，工人是机器。,一、基本概念排序中常用的几个概念如：,一、基本概念,所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。,如可用（1，6，5，4，3，2）表示加工顺序：J,1,J,6,J,5,J,4,J,3,J,2,。,一、基本概念 所以，作业排序也就是要确定工件在机器上的加,一、基本概念,2、作业计划（Scheduling）,作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。,如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。,一、基本概念2、作业计划（Scheduling）,一、基本概念,3、排序问题的分类与表示,1）单台机器与多台机器的排序问题。,2）流水车间与单件车间排序问题。,一、基本概念3、排序问题的分类与表示,一、基本概念,流水车间排序问题的基本特征：,每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。,不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。,一、基本概念流水车间排序问题的基本特征：,一、基本概念,单件车间排序问题的基本特征：,每个工件都有其独特的加工路线，工件没有一定的流向。,一、基本概念单件车间排序问题的基本特征：,一、基本概念,3）表示方法,一般正规的表示方法为：n/m/A/B,n：工件数；m：机器数；,A：车间类型（F、P、G）；B：目标函数,一、基本概念3）表示方法,一、基本概念,4）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。,一、基本概念4）一般来说，排列排序问题的最优解不一定是相应,一、基本概念,4、排序问题的假设条件,一个工件不能同时在几台不同的机器上加工。,工件在加工过程中采取平行移动方式。,不允许中断。,每道工序只在一台机器上完成。,每台机器同时只能加工一个工件。,工件数、机器数和加工时间已知，加工时间与加工顺序无关。,一、基本概念4、排序问题的假设条件,二、最长流程时间,最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。,假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。,二、最长流程时间最长流程时间（加工周期）：从第一个工件在第一,二、最长流程时间,计算Fmax的几个假定条件：,机器M1不会发生空闲；,对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。,二、最长流程时间计算Fmax的几个假定条件：,二、最长流程时间,二、最长流程时间,二、最长流程时间,i,p,i1,p,i2,p,i3,p,i4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,30,35,42,13,21,25,32,38,46,二、最长流程时间ipi1pi2pi3pi4615243255,三、n/2/F/Fmax问题的算法,Johnson算法：,假定：a,i,为工件J,i,在机器M1上的加工时间，b,i,为工件J,i,在机器M2上的加工时间，每个工件按M1M2的路线加工。,三、n/2/F/Fmax问题的算法Johnson算法：,三、n/2/F/Fmax问题的算法,Johnson算法的步骤：,从加工时间矩阵中找出最短的加工时间。,若最短时间出现在M,1,上，则对应的工件尽可能往前排。,若最短时间出现在M,2,上，则对应的工件尽可能往后排。,若最短时间有多个，则任选一个。,划去已排序的工件。,若所有工件都已排序，则停止，否则重复上述步骤。,三、n/2/F/Fmax问题的算法Johnson算法的步骤：,四、一般n/m/P/Fmax问题的启发式算法,对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。,四、一般n/m/P/Fmax问题的启发式算法 对于一般的,四、一般n/m/P/Fmax问题的启发式算法,1、Palmer法,计算工件斜度指标,i：,m:机器数,p,ik,：工件i在机器k上的加工时间。,i=1,2,n,排序方法:按,i,从大到小的顺序排列。,按排序的顺序计算Fmax,四、一般n/m/P/Fmax问题的启发式算法1、Palme,四、一般n/m/P/Fmax问题的启发式算法,2、关键工件法,：,计算P,i,=,P,ij,，找出P,i,最长的工件，将之作为关键工件C。,对其余工件，若P,i1,P,im,，则按P,i1,由小到大排成序列S,A,。,若P,i1,P,im,，则按P,im,由大到小排成序列S,B,。,顺序（S,A,，C，S,B,）即为近优解。,四、一般n/m/P/Fmax问题的启发式算法2、关键工件法,四、一般n/m/P/Fmax问题的启发式算法,得到的加工顺序为(1，2，3，4),四、一般n/m/P/Fmax问题的启发式算法得到的加工顺序,四、一般n/m/P/Fmax问题的启发式算法,3、,CDS,法,：,CDS法,是,Johnson算法,的扩展方法，从M-1个排序中找出近优解。,四、一般n/m/P/Fmax问题的启发式算法3、CDS法：,四、一般n/m/P/Fmax问题的启发式算法,L1，按Johnson算法得到加工顺序(1，2，3，4)，F,max,28,L2，按Johnson算法得到加工顺序(2，3，1，4)，F,max,29,取顺序(1，2，3，4）为最优顺序。,四、一般n/m/P/Fmax问题的启发式算法L1，按Jo,五、单件车间排序问题（n/m/G/F,max,）,1、,问题描述,(i，j，k)：表示工件i的第j道工序是在机器k上进行。,加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,五、单件车间排序问题（n/m/G/Fmax）1、问题描述D=,五、单件车间排序问题（n/m/G/F,max,）,加工时间矩阵T：与D相对应。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T=,4 6 3,5 7 4,五、单件车间排序问题（n/m/G/Fmax）加工时间矩阵T：,五、单件车间排序问题（n/m/G/F,max,）,加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,五、单件车间排序问题（n/m/G/Fmax）加工顺序矩阵S：,五、单件车间排序问题（n/m/G/F,max,）,用方块图表示：,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,T=,4 6 3,5 7 4,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,五、单件车间排序问题（n/m/G/Fmax）用方块图表示：D,五、单件车间排序问题（n/m/G/F,max,）,2、,能动作业计划的构成,各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。,符号说明：,O,t,第t步可以排序的工序的集合,S,t,t步之前已排序的工序构成的部分作业计划,T,k,O,t,中工序O,k,的最早可能开工时间,T,k,O,t,中工序O,k,的最早可能完工时间,五、单件车间排序问题（n/m/G/Fmax）2、能动作业计划,五、单件车间排序问题（n/m/G/F,max,）,能动作业计划的构成步骤：,设t1,，S,t,为空，O,t,为各工件第一道工序的集合。,求最小的最早完工时间 T,*,=minT,k,并,找到出现T,*,的机器M,*,，若有多台，任选一台。,从O,t,中跳出满足以下两条件的工序O,j,需要机器M,*,加工；,T,j,T,*,将确定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。,若还有未安排的工序，转步骤；否则，停止。,五、单件车间排序问题（n/m/G/Fmax）能动作业计划的构,一个实例：,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T=,2 4 1,3 4 5,i,1,O,t,Tk,Tk,T*,M*,Oj,1,1,1,0,2,2,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,3,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,7,M3,1,2,3,2,2,1,3,7,4,1,3,2,7,8,7,M1,2,2,1,2,2,1,3,7,5,1,3,2,7,8,8,M2,1,3,2,2,3,2,7,12,6,13,M2,2,3,2,2,3,2,8,13,一个实例：D=1,1,1 1,2,3 1,3,22,得到加工顺序矩阵：,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,8,13,得到加工顺序矩阵：S=1,1,1 2,2,11,3,2,五、单件车间排序问题（n/m/G/F,max,）,3、,无延迟作业计划的构成,没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。,构成步骤：,五、单件车间排序问题（n/m/G/Fmax）3、无延迟作业计,五、单件车间排序问题（n/m/G/F,max,）,无延迟作业计划的构成步骤：,设t1,，S,t,为空，O,t,为各工件第一道工序的集合。,求最小的最早完工时间 T,*,=minT,k,并,找到出现T,*,的机器M,*,，若有多台，任选一台。,从O,t,中跳出满足以下两条件的工序O,j,需要机器M,*,加工；,T,j,=T,*,将确定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。,若还有未安排的工序，转步骤；否则，停止。,五、单件车间排序问题（n/m/G/Fmax）无延迟作业计划的,一个实例：,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T=,2 4 1,3 4 5,i,1,O,t,Tk,Tk,T*,M*,Oj,1,1,1,0,2,0,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,0,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,3,M3