排序与统筹方法MNEW.ppt

第十一章 排序与统筹方法,车间作业计划模型统筹方法,1 车间作业计划模型,车间作业计划的基本概念计划模型I计划模型II,1.基本概念,车间作业计划:指一个工厂生产工序的计划和安排.停留时间:现有n个零件需要加工,加工时间分别为Pj,安排在第j位加工的零件在车间里总的停留时间Tj:Tj=P1+P2+Pj,1.基本概念,平均停留时间:前n个零件的总时间为:T1+T2+T3+Tn,平均停留时间为(T1+T2+T3+Tn)/n,2.模型I,一台机器,N个零件:,如何安排加工顺序,才能使得这六个零件在车间里停留平均时间为最少?,按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为：(1.8+3.8+4.3+5.2+6.5+8)/6=4.93,随意排:123456,按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为：(0.5+2.5+3.4+4.7+6.2+8)/6=4.22,按324561的顺序加工:,按n1、n2、n3、n4、n5、n6顺序加工零件，各个零件平均停留时间为：(T1+T2+T3+T4+T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6),任意顺序:n1,n2,n3,n4,n5,n6:,按n1、n2、n3、n4、n5、n6顺序加工零件，各个零件平均停留时间为：(T1+T2+T3+T4+T5+T6)/6=(p1+(p1+p2)+(p1+p2+p3)+(p1+p2+p3+p4)+(p1+p2+p3+p4+p5)+(p1+p2+p3+p4+p5+p6)=(1p6+2P5+3P4+4P3+5P2+6P1)/6=(6p1+5P2+4P3+3P4+2P5+1P6)/6要使平均停留时间最少,只要系数大的时间短即可.即要对加工时间排序:短时间加优先!,任意顺序:n1,n2,n3,n4,n5,n6:,本题加顺序:3,4,5,6,1,2时间:0.5,0.9,1.3,1.5,1.8,2.0停留时间:0.5,1.4,2.7,4.2,6.0,8.0各个零件平均停留时间为:3.8,3.模型II,两台机器,n个零件:,先削后磨,如何安排加工顺序,才能使得完成这五个零件的总的加工时间为最少?,先车削,后车磨,0.5,0.25,1.5,2.0,1.0,1.25,0.75,1.75,2.5,1.25,按FCFS：先来先服务。12345,先车削,后车磨,1.25,0.25,0.75,1.0,2.0,1.5,1.25,1.75,0.5,2.5,按53214,如何确定加工顺序,才能总加工时间最少?事实上总费时多的原因是第二台机器需要等待,要延时多,而第一台并不需要延时。因此，要减少尽少磨车床中零件的加工等待时间。一方面要把短时间的车削加工往提前排，另一方面，要把磨床上加工时间短的越晚加工，把磨床上加工时间长的往后延。,0.25,0.5,0.75,1.0,1.25,1.5,2.0,2.5,两台机器,n个零件的排序问题,1.在加工时间表上选出最短加工时间tij,其中i为工序,j为零件号,当为i=1时,将零件J的加工顺序尽量靠前,若i=2时,将零件j的加工顺序尽量靠后;2.在表上划去零件j的所在行，回到步骤,练习题,：，New:p279.1,2,网络图,2 统筹方法,一、计划网络图二、网络时间与关键路线三、完成工序所需时间不确定时 的网络时间与关键路线四、网络优化,一、计划网络图,网络计划技术的基本概念网络图的绘制,一、计划网络图,基本概念：工程：一项施工任务、科研试制项目、生产以及较复杂的工作任务，统称为工程。工序：为了完成某项工程，在工艺技术和组织管理上相对独立的活动称为工序。如：车床削、磨，两个工序，用a,b表示。,一、计划网络图,基本概念：事件：表示一个工序的开始或结束，它是相邻工序在时间上的分界点，用编号表示。网络图：由工序、事件及标有完成各道工序所需时间等参数所构成的有向图，就是网络图。,例1：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。,二、网络图的绘制,网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。,一个科研项目网络图,1,2,3,4,5,例2：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。,一个科研项目网络图,1,2,3,5,6,4,一个科研项目网络图,1,2,3,5,6,4,7,一个科研项目网络图,1,2,3,5,7,4,8,6,二、网络图的绘制,从开始节点到结束节点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间最长的路线叫做关键路线，关键路线的总时间叫做工期看下面的例子,网络图的路线,当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为,以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是,网络图的画法,作业的串联作业的并联,网络图的画法,作业的交叉作业的合并,绘制网络图的基本原则,两事件间只能有一项作业,改为,绘制网络图的基本原则,网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线不能出现缺口尽量少交叉，采用暗桥；有层次性。,使用暗桥,网络图的绘制步骤,确定目标，做好准备工作任务分解和分析绘制网络图,表4-1 调查项目的任务分解和分析,绘制作业图的方法,试探性绘制法计算机辅助绘制法流程图过渡绘制法,试探性绘制法：试探,试探性绘制法：修改,流程图过渡绘制法：流程图,流程图过渡绘制法：加事项,流程图过渡绘制法：去方框,流程图过渡绘制法：修改,二、网络时间与关键路线,从网络图中求出：完成此工程项目所需的最少时间；每个工序的开始时间与结束时间；关键路线及其相应的关键工序；非关键工序在不影响工程的完成时间的前提下，其开始时间与结束推迟多久。,例5 某公司装配一条新的生产线。,1,2,4,5,7,6,8,3,寻找关键路线：,（1）从网络起点按顺序计算出每个工序的最早开始时间（ES）和最早结束时间（EF）,1,2,60,A0,60,对同一个工序：EF=Es+t;对相邻工序：EF=ES（Max）+t,1,2,4,5,7,6,8,3,A0,60,d60,80,e60,100,b60,105,c60,70,f70,88,g80,110,i110,135,h100,115,j135,170,寻找关键路线：,（2）从网络收点开始计算出每个工序的最迟（晚）开始时间（LS）和最迟（晚）结束时间（LF）,对同一个工序：LS=LF-t;对相邻工序：LS=LF-t,1,2,4,5,7,6,8,3,A0,60,d60,80,e60,100,b60,105,c60,70,f70,88,g80,110,i110,135,h100,115,j135,170,35135,170,25110,135,15120,135,4080,120,3080,110,18117,135,4590,135,10107,117,2060,80,600,60,寻找关键路线：,（3）计算出每个工序的时间差TS TS=LS-ES=LF-EF,对工序B来说，TS=90-60=30工序在60-90天之内任何时间内开工，都不会影响工期。称为非关键工序。对工序g来说，TS=80-80=0不能提前，也不能推后，否则会影响总工期。称为关键工序。,例5 某公司装配一条新的生产线。,1,2,4,5,7,6,8,3,A0,60,d60,80,e60,100,b60,105,c60,70,f70,88,g80,110,i110,135,h100,115,j135,170,35135,170,25110,135,15120,135,4080,120,3080,110,18117,135,4590,135,10107,117,2060,80,600,60,得关键路线：Adgij,三、完成工序所需时间不确定时的网络时间与关键路线：,如果完成工序所需时间不确定的情况下怎样来求网络时间和关键路线？,例6。某培训中心准备对各部门领导干部进行培训。,通过调查的时间估计：,要求：绘出统筹方法的网络图，设法求出网络时间和关键路线。,1,2,3,4,5,6,7,8,i,a,b,c,d,e,g,f,h,统筹方法网络图,一、先画出网络图：,二、工序（活动）时间：乐观时间（全绿灯）：顺利情况下，完成活动所需时间-a 最可能时间（正常）：指正常情况下，完成活动所需时间-m悲观时间（很不顺）：指在不顺利情况下，完成工作所需时间-b。,作业时间的确定,对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差,工序时间计算方法,a,m,b,平均时间,按期完成计划的概率,每项作业的时间是一个随机变量，近似服从 分布，均值和标准差为工期也是一个随机变量，它的期望值为各关键作业时间期望之和。,按期完成计划的概率,当作业数足够多时，工期近似服从正态分布,按期完成计划的概率,其中按期完成的概率,1,2,3,4,5,6,7,8,i,a0，2,b,c,d,e,g,f,h,统筹方法网络图,一、先画出网络图：,2,b0，2,2,a0，2,2,2,4,2,1,2,2,4,a,1,2,3,4,5,6,7,8,i,a0，2,b,c,d,e,g,f,h,统筹方法网络图,一、先画出网络图：,2,b0，2,2,e5，6,2,2,4,2,1,2,2,4,a,g5，9,c0，2,d2，4,f6，8,h9，13,i13，15,1,2,3,4,5,6,7,8,i,a0，2,b,c,d,e,g,f,h,统筹方法网络图,一、先画出网络图：,2,b2，5,2,e5，6,2,4,2,1,2,2,4,a,g5，9,c0，2,d2，4,f6，8,h9，13,i13，15,213，15,211，13,49，13,110，11,45，9,23，5,21，3,32，5,20，2,例5 某公司装配一条新的生产线。,Yes,Yes,Yes,Yes,Yes,1,2,3,4,5,6,7,8,i,a0，2,b,c,d,e,g,f,h,关键路线：abghi:平均时间的总和：2+3+4+4+2=15,2,b2，5,2,e5，6,2,4,2,1,2,2,4,a,g5，9,c0，2,d2，4,f6，8,h9，13,i13，15,213，15,211，13,49，13,110，11,45，9,23，5,21，3,32，5,20，2,由于完成培训工作所需时间是一个随机事件，是可变的，它服从一定的概率分布，根据概率论知识，各工序的时间服从分布，那么完成整个任务的时间和近似服从正态分布，从而可以估计不同守工时间的概率。例如，E(T)=Ta+Tb+Tg+Th+Ti=15,2=各方差之和=1.05那么完成整个工作的时间服从N(E(T),2)的正态分布.因此,可以利用此分布来估计在一定时间内完成整个工作的可能性.,培训工作的平均完成时间为E（T）（约15周），波动变化反映在幅度方差为2，具体完成的时间是动态变化不确定的。那么我们可以根据时间服从N(E(T),2)的正态分布来估算完成时间的可能性（概率）即利用此分布来估计在一定时间内完成整个工作的可能性.如：上述平均时间是15周，2=1.05,那么,培训工作能在16周内完成的可能性有多大?,如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?,如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?,如果要以100%的把握来保证培训工作如期完成,那么应在几周前开始准备?,四、网络优化,得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。工期限定，资源需要平衡资源有限，工期希望最短工期缩短，总费用最小,四、网络优化,1.时间-资源优化 做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：,安排d-i各工序的总人数为65,1,2,4,5,7,6,8,3,d58人,f22人,g42人,i26人,h39,2,7,4,6,3,5,f(22人）,18,h(39人),15,58人,64人,80人,81人,42人,26人,65人,60 80 100 120 130,d(58人）,i(26人）,g(42人）,30,20,25,图12-17,10,d,d+f,F+g,g,G+h,H+i,i,60,70,80,90,100,110,120,130,58,80人,64,42,81人,65,26人,60,70,80,90,100,110,120,130,58,80人,64,42,81人,65,26人,安排d-i各工序的总人数为65,i,d,F+g,g,H+i,60,70,80,90,100,110,120,130,58,64,42,65,26人,同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。,2.时间-费用优化,工期不变，就是关键工作时间不能调整资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。,2 统筹方法,2.时间-费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。直接费用：为了加快工程进度，必须设法缩短关键工序的时间，这样需要增加人力、设备和工作班次，从而需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,2 统筹方法,工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有 时间-费用优化问题可建立两个线性规划模型。模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。设工序（i,j)的提前完工时间为Yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：minf=（Kij*Yij)（i,j)S.t.Xj-Xi Tij-Yij,对一切弧（i,j)Yij Tij-Tij,对一切弧（i,j)Xn-X1 T,Xi 0，Yij 0。,2 统筹方法,例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。表12-17,2 统筹方法,该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？,1,2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,图12-19,2 统筹方法,解：绘出如图12-19所示，根据此网络图建立数学模型。设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x1 60-y12,x7-x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40虚拟弧（4，5）x7-x515-y57 x7-x625-y67,2 统筹方法,x1=0,y120,y2715,y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0，yij 0.（对一切可能的ij)运算得到结果：f=6400。,2 统筹方法,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为：目标函数min f=d(xn-x1)+s.t.xj-xi Tij-yij，对一切弧（i,j)yijTij-Tij，对一切弧（i,j)xi 0，yij 0。,2 统筹方法,例8 如果在例7中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。解：决策变量的含义同例7。此数学模型的目标函数为：min f=330(x8-x1)+120y27+300 y23+400y24+500y25+230y37+350y46+290y67 此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去掉x8 150就得到了例8模型的约束条件了。计算得到以下结果：f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0.,2 统筹方法,x3=125,y23=0,x4=107,y24=0,x5=110,y25=0,x6=110,y37=0,x7=125,y46=0,x8=160,y57=0,也就是说整个工程工期为160天时总费用最少为55700元，各个工序开始时间如解所示，工序 i 要提前10天完工，其余的工序按正常时间完工。,习题P281 习题 1-7本章结束。Thanks,一个例子,各工作都按最早开始时间开始,调整非关键工作的开始时间,资源有限，要求工期最短,下图表示的项目只有10人工作,第一次调整,第二次调整,工期缩短，总费用最少,一般情况下，若采取措施缩短工期，则间接费用将减少，直接费用将增加，总费用由一个最低点。,直接成本的处理,按线性处理，作业的费用率为,图4-52 一个例子,解题思路,以正常时间进行网络分析，求得关键路线在关键路线上，寻找最小费率的工作，缩短其时间，使工期最多到次长路线的长度。缩短工期必须对所有关键路线进行，此时应选择费率总和最小的组合方案。,第一步求关键路线,工期=11天,第二步选择(2,3)缩短工期,工期=10天增加费用1,第三步按第I方案缩短工期,工期=9天增加费用1+2=3,再按方案III缩短周期,工期=8天增加费用3+3=6,第四步按第I、II方案缩短4天,工期=4天增加费用6+16=22,调整(1,2)与(2,3)，并缩短(3,4),工期=3天增加费用22+5=27,总合算费用，绘制直接费用图,总费用最小的优化,一般应考虑间接费用，工期缩短，总的间接费用减少例如，上例中，间接费用率为：4.5/天，则因为最后一部直接费率5/天4.5/天，因此最后一步的工期不能缩短，工期应为4天，此时可节省费用3.5+1.5+4*0.5=7。,事项参数的计算,事件（项）最早时间事件（项）最迟时间,i,i,图上计算法,矩阵法计算事项时间,作业时间参数的计算,作业开始最早时间作业结束最早时间作业开始最迟时间作业结束最迟时间总时差单时差,作业最早时间,作业最迟时间,时差,总时差,单时差,时差之间的关系,表4-3 作业时间参数计算,关键路线的确定方法,总时差为零的作业即是关键作业，关键作业构成关键路线破圈法也可采用最长路线法。,