十一章 排序与统筹

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,十一章 排序与统筹（,p234),1.,车间作业计划模型,一、一台机器、几个零件的排序问题,例,1,应该按照什么样的加工顺序来加工零件，使所有零件在车间停留的平均时间最少。,零 件,加工时间（小时）,1,2,3,4,5,6,1.8,2.0,0.5,0.9,1.3,1.5,设第,j,次加工零件在车间停留的时间为,T,j,第,i,次加工零件的加工时间,P,i,，择有,T,j,=P,1,+P,2,+,+P,j-1,+P,j,所有零件在车间停留的平均时间为,T,1,+T,2,+T,3,+T,4,+T,5,+T,6,=P,1,+(P,1,+P,2,)+(P,1,+P,2,+P,3,)+(P,1,+P,2,+P,3,+P,4,),+(P,1,+P,2,+P,3,+P,4,+P,5,)+(P,1,+P,2,+P,3,+P,4,+P,5,+P,6,),=6P,1,+5P,2,+4P,3,+3P,4,+2P,5,+P,6,两台机器，,n,个零件,例,2,零件,车窗,磨床,1,2,3,4,5,1.5,2.0,1.0,1.25,0.75,0.5,0.25,1.75,2.5,1.25,顺序,1,2,3,4,5,零件,5,3,4,1,2,2.,统筹方法,一 计划网络图,(p241),例,3,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,产品与工艺设计,外购配套零件,外购生产原料,自制主件,可靠性测试,60,15,13,38,8,-,a,a,c,b,d,1,2,3,4,5,a,b,c,d,e,60,15,13,38,8,例,4,（,p242),工序代号,所需时间（天）,紧前工序,工序代号,所需时间（天）,紧前工序,a,b,c,d,60,15,13,38,-,a,a,c,e,f,g,h,8,10,16,5,b,d,d,d,e,f,g,1,2,3,5,6,a,b,c,d,e,60,15,13,38,8,4,10,f,习题,4,工序代号,紧前工序,工序代号,紧前工序,a,b,c,d,-,-,a,，,b,a,，,b,e,f,g,b,c,d,e,1,3,4,6,7,a,c,d,e,b,5,g,f,2,二、网络时间与关键路线,在绘制出网络图后，我们可以根据网络图求出：,1.,完成此工程项目所需的最少时间。,2.,每个工序的开始时间与结束时间。,3.,关键路线及其相应的关键工序。,4.,非关键工序在不影响工程进度的前提下，其开始时间与机务时间可以推迟多久。,例,5.,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,f,g,h,i,j,生产线设计,外购零配件,下料、锻件,工装制造,1,木制、锻件,机械加工,1,工装制造,2,机械加工,2,机械加工,3,装配调试,60,45,10,20,40,18,30,15,25,35,-,a,a,a,a,c,d,d,e,g,b,i,f,h,1,2,8,4,6,a,c,d,e,b,5,g,f,7,3,45,18,10,60,20,40,h,i,j,30,25,35,15,路线：在网络图上从出发点开始，沿着弧的方向连续地到达,收点的一条路。,关键路线：网络图中最长的路线。,1,2,7,8,1,2,3,7,8,1,2,5,7,8,1,2,4,6,7,8,长度,=140,长度,=123,长度,=150,长度,=170,寻找关键路线的方法,用,ES,表示,一,个工序最早开工时间，用,EF,表示,一,个工序最早完工时间，用,t,表示,一,个工序所需时间。我们有,EF=ES+t,用,ES,EF,放在工序的上面来记录,一,个工序的最早开工时间和最早完工时间。,1,2,8,4,6,a,c,d,e,b,5,g,f,7,3,45,18,10,60,20,40,h,i,j,30,25,35,15,0,60,60,105,135,170,110,135,80,110,60,80,70,88,60,100,60,70,100,115,用,LS,表示一个工序最晚开工时间，用,LF,表示一个工序最晚完工时间。用,LS,LF,放在工序的下面来记录,一,个工序的最晚开工时间和最晚完工时间。,1,2,8,4,6,a,c,d,e,b,5,g,f,7,3,45,18,10,60,20,40,h,i,j,30,25,35,15,0,60,60,105,135,170,110,135,80,110,60,80,70,88,60,100,60,70,100,115,107,117,90,135,117,135,135,170,110,135,80,110,60,80,0,60,80,120,120,135,用,T,s,表示工序的时差,T,s,=LS-ES=LF-EF,如，对于,B,工序，,T,s,=90-60=30,对关键路线上的所有工序，其时差都为零。,例,5,工序,所需,时间,紧前,工序,工序,所需时间,紧前,工序,a,b,c,d,2,4,5,4,-,-,a,b,a,b,e,f,g,3,2,4,b,c,d,e,1,3,2,5,6,a,c,d,e,b,4,g,f,2,5,2,4,4,3,4,关键路线,最早完工时间,12,天,最晚开工时间和完工时间,1,3,2,5,6,a,c,d,e,b,4,g,f,2,5,2,4,4,3,4,0,2,4,9,0,4,4,7,4,8,8,12,9,11,1,2,3,4,6,1,3,2,5,6,a,c,d,e,b,4,g,f,2,5,2,4,3,4,0,2,4,9,0,4,4,7,4,8,8,12,9,11,8,12,4,8,10,12,5,10,2,4,5,8,0,4,4,网络优化,1.,时间,资源优化,为了使工程进度与资源利用都得到比较合理安排，可采取以下的做法：,1),优先安排关键工序所需要的资源。,2),利用非关键工序曲时差，错开各工序的开始时间，拉平资源需要量的,高峰。,3),要统筹兼顾工程进度的要求和现有资源的限制往往要经过多次综合,平衡，才能得到比较合理的计划方案。,工人人数,65,工序,加工工人人数,最早开工时间,所需时间,时差,d,f,g,h,i,58,22,42,39,26,60,70,80,100,100,20,18,30,15,25,0,47,0,20,0,3,4,7,f,g,d,6,i,2,18,20,30,25,(58,人）,(22,人）,(42,人）,(26,人）,(39,人）,15,5,h,2.,时间,-,费用优化,在既定时间完成工程的前提下，使得费用最少，或者在不超过工程预算的条件下，使得工程最早完工。,缩短工序的作业时间的限度称为工序的最快完成时间。,设完成工序,j,的正常所需时间为,T,j,;,直接费用为,c,j,；最快完成时间为 ，直接费用为 。缩短工序一天工期所减少的直接费用，我们用,k,j,表示，有,k,j,=,模型一,设网络图上点,i,发生的时间为,x,i,。,T,表示既定的时间。,对一个工序，我们既可以用工序的代号来表示，也可以用表示这个工序的弧,(,i,j,),来表示。,设工序,(,i,j,),的提前完工时问为,ij,，则有工序,(,i,j,),的实际完工时间为：,T,ij,-,ij,性规划模型如下：,min f=,s.t,.,x,j,-x,i,T,ij,ij,对一切弧,(,i,j,),ij,T,ij,对一切弧,(,i,j,),X,n,T,xi,ij,0,