排序与统筹方法MNEW

1、第十一章 排序与统筹方法统筹方法11 车间作业计划模型车间作业计划的基本概念计划模型I计划模型II21.基本概念车间作业计划:指一个工厂生产工序的计划和安排.停留时间:现有n个零件需要加工,加工时间分别为Pj ,安排在第j位加工的零件在车间里总的停留时间Tj : Tj =P1+P2+Pj31.基本概念平均停留时间:前n个零件的总时间为:T1+T2+T3+Tn,平均停留时间为(T1+T2+T3+Tn)/n42.模型I一台机器,N个零件:零件加工时间(小时)零件加工时间(小时)11.840.922.051.330.561.5如何安排加工顺序,才能使得这六个零件在车间里停留平均时间为最少?5零件加工

2、时间Pi 停留时间Tj零件加工时间Pi停留时间Tj11.81.840.95.222.03.851.36.530.54.361.58按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为： (1.8+3.8+4.3+5.2+6.5+8)/6=4.93随意排:1234566零件加工时间Pi 停留时间Tj零件加工时间Pi停留时间Tj30.50.551.33.4+1.3=4.722.02.561.56.240.9.25+0.9=3.411.88按1、2、3、4、5、6顺序加工零件，各个零件平均停留时间为： (0.5+2.5+3.4+4.7+6.2+8)/6=4.22按324561的顺序加工:7零

3、件加工时间Pi 停留时间Tj零件加工时间Pi停留时间TjN1Pn1Pn1N4Pn4T3+pn4N2Pn2pn1+pn2N5Pn5T4+Pn5n3pn3T2+Pn3N6Pn6T5+pn6按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:8按n1、n2、n3、n4、n5、n6顺序加工零件，各个零件平均停留时间为：(T1+T2+T3+T4+

4、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:9本题加顺序: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.8103.模型II

5、两台机器,n个零件:先削后磨,如何安排加工顺序,才能使得完成这五个零件的总的加工时间为最少?11先车削,后车磨0.50.251.52.01.01.250.751.752.51.25按FCFS：先来先服务。1234512先车削,后车磨1.250.250.751.02.01.51.251.750.52.5按5321413如何确定加工顺序,才能总加工时间最少?事实上总费时多的原因是第二台机器需要等待,要延时多,而第一台并不需要延时。因此，要减少尽少磨车床中零件的加工等待时间。一方面要把短时间的车削加工往提前排，另一方面，要把磨床上加工时间短的越晚加工，把磨床上加工时间长的往后延。14加工顺序零件号5

6、34120.25,0.5,0.75,1.0,1.25,1.5,2.0,2.515两台机器,n个零件的排序问题1.在加工时间表上选出最短加工时间tij,其中i为工序,j为零件号,当为i=1时,将零件J的加工顺序尽量靠前,若i=2时,将零件j的加工顺序尽量靠后;2.在表上划去零件j的所在行，回到步骤16练习题：，New:p279. 1,217网络图1435cdbea262232182 统筹方法一、计划网络图二、网络时间与关键路线三、完成工序所需时间不确定时 的网络时间与关键路线四、网络优化19一、计划网络图网络计划技术的基本概念网络图的绘制20一、计划网络图基本概念：工程：一项施工任务、科研试制项

7、目、生产以及较复杂的工作任务，统称为工程。工序：为了完成某项工程，在工艺技术和组织管理上相对独立的活动称为工序。如：车床削、磨，两个工序，用a,b表示。21一、计划网络图基本概念：事件：表示一个工序的开始或结束，它是相邻工序在时间上的分界点，用编号表示。网络图：由工序、事件及标有完成各道工序所需时间等参数所构成的有向图，就是网络图。22例1：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。工序代号工序内容所需时间紧前工序A产品设计与工艺设计60-B外购配套零件15AC外购生产原料13Ad自制主件38Ce主配件可靠性试验8B,d23二、网络图的绘制网络图

8、的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。工作名称时间12A60ij24一个科研项目网络图12345a60c13e8b15d3825例2：某公司研制新产品的部分工序与所需时间以及它们之间的相互关系如下表：试画出其统筹方法网络图。26一个科研项目网络图12356a60c13e8b15d384f1027一个科研项目网络图12356a60c13e8b15d384f107h5g1628一个科研项目网络图12357a60c13e8b15d384f108h5g16629二、网络图的绘制从开始节点到结束节

9、点的一条路经叫做路线一个网络图的有多条路线，每条路线有一个总时间总时间最长的路线叫做关键路线，关键路线的总时间叫做工期看下面的例子30网络图的路线31当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是32网络图的画法作业的串联作业的并联33网络图的画法作业的交叉作业的合并3435绘制网络图的基本原则两事件间只能有一项作业改为36绘制网络图的基本原则网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编

10、号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线不能出现缺口尽量少交叉，采用暗桥；有层次性。3738使用暗桥39网络图的绘制步骤确定目标，做好准备工作任务分解和分析绘制网络图40表4-1 调查项目的任务分解和分析41绘制作业图的方法试探性绘制法计算机辅助绘制法流程图过渡绘制法42试探性绘制法：试探43试探性绘制法：修改44流程图过渡绘制法：流程图45流程图过渡绘制法：加事项46流程图过渡绘制法：去方框47流程图过渡绘制法：修改48二、网络时间与关键路线从网络图中求出：完成此工程项目所需的最少时间；每个工序的开始时间与结束时间；关键路线及其相应的关键工序；非关键工序在不影响

11、工程的完成时间的前提下，其开始时间与结束推迟多久。49例5 某公司装配一条新的生产线。工序代号工序内容所需时间紧前工序A生产线设计60-B外购零配件45AC下料、锻件10AD工装制造120AE木模40AF机械加工118CG工装制造230DH机械加工215D,eI机械加工325Gj装配调试35B,I,f,h5012457a60c10i25b45d206h158j35g303e40f1851寻找关键路线：（1）从网络起点按顺序计算出每个工序的最早开始时间（ES）和最早结束时间（EF）1260A0,60对同一个工序：EF=Es+t;对相邻工序：EF=ES（Max）+t521245760c10i25b

12、45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17053寻找关键路线：（2）从网络收点开始计算出每个工序的最迟（晚）开始时间（LS）和最迟（晚）结束时间（LF）对同一个工序：LS=LF-t;对相邻工序：LS=LF-t541245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,110i110,135h100,115j135,17035135,17025110,13515

13、120,1354080,1203080,11018117,1354590,13510107,1172060,80600,6055寻找关键路线：（3）计算出每个工序的时间差TS TS=LS-ES=LF-EF,对工序B来说，TS=90-60=30工序在60-90天之内任何时间内开工，都不会影响工期。称为非关键工序。对工序g来说，TS=80-80=0不能提前，也不能推后，否则会影响总工期。称为关键工序。56例5 某公司装配一条新的生产线。571245760c10i25b45d206h158j35g303e40f18A0,60d60,80e60,100b60,105c60,70f70,88g80,11

14、0i110,135h100,115j135,17035135,17025110,13515120,1354080,1203080,11018117,1354590,13510107,1172060,80600,60得关键路线： Adgij58三、完成工序所需时间不确定时的网络时间与关键路线：如果完成工序所需时间不确定的情况下怎样来求网络时间和关键路线？59例6。某培训中心准备对各部门领导干部进行培训。活动工序活动内容紧前活动A 制定培训计划-B选聘培训教师AC列出可选培训点-D确定培训点CE确定培训的日程安排B,dF落实教学设备、资料EG发培训通知及确定学员名单b,dh订旅馆房间Gi处理最后的

15、一些事务F,h60 通过调查的时间估计：活动工序乐观时间最可能时间悲观时间A1.52.02.5B2.02.56C123D1.522.5E0.511.5F123G33.57h345i1.522.561要求：绘出统筹方法的网络图，设法求出网络时间和关键路线。6212345678iabcdegfh 统筹方法网络图一、先画出网络图：63二、工序（活动）时间：乐观时间（全绿灯）：顺利情况下，完成活动所需时间-a 最可能时间（正常）：指正常情况下，完成活动所需时间-m悲观时间（很不顺）：指在不顺利情况下，完成工作所需时间-b。64作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间

16、估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差65工序时间计算方法amb平均时间66按期完成计划的概率每项作业的时间是一个随机变量，近似服从 分布，均值和标准差为工期也是一个随机变量，它的期望值为各关键作业时间期望之和。67按期完成计划的概率当作业数足够多时，工期近似服从正态分布68按期完成计划的概率其中按期完成的概率6912345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b0，22a0，222421224a7012345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b0，22e5，622421224ag5，9c0，2d2，4f

17、6，8h9，13i13，157112345678ia0，2bcdegfh 统筹方法网络图一、先画出网络图：2b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，923，521，332，520，272例5 某公司装配一条新的生产线。YesYesYesYesYes7312345678ia0，2bcdegfh关键路线：abghi:平均时间的总和：2+3+4+4+2=152b2，52e5，62421224ag5，9c0，2d2，4f6，8h9，13i13，15213，15211，1349，13110，1145，92

18、3，521，332，520，274由于完成培训工作所需时间是一个随机事件，是可变的，它服从一定的概率分布，根据概率论知识，各工序的时间服从分布，那么完成整个任务的时间和近似服从正态分布，从而可以估计不同守工时间的概率。例如，E(T)=Ta+Tb+Tg+Th+Ti=15, 2 =各方差之和=1.05那么完成整个工作的时间服从N(E(T), 2) 的正态分布.因此,可以利用此分布来估计在一定时间内完成整个工作的可能性.75培训工作的平均完成时间为E（T）（约15周），波动变化反映在幅度方差为2，具体完成的时间是动态变化不确定的。那么我们可以根据时间服从N(E(T), 2) 的正态分布来估算完成时间

19、的可能性（概率）即利用此分布来估计在一定时间内完成整个工作的可能性.如：上述平均时间是15周， 2=1.05,那么,培训工作能在16周内完成的可能性有多大?76如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?如果要以99%的把握来保证培训工作如期完成,那么应在几周前开始准备?77如果要以100%的把握来保证培训工作如期完成,那么应在几周前开始准备?78四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。工期限定，资源需要平衡资源有限，工期希望最短工期缩短，总费用最小79四、网络优化

20、 1.时间-资源优化 做法： 1）优先安排关键工序所需的资源。 2）利用非关键工序的时差，错开各工序的开始时间。 3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。 下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：80安排d-i各工序的总人数为65811245760c10i25b45d206h15天8j35g303e40f18d58人f22人g42人i26人h3982274635 f(22人）18h(39人)1558人64人80人81人42人26人65人60 80 100

21、120 130 d(58人） i(26人） g(42人）302025图12-171083dd+fF+ggG+hH+ii607080901001101201305880人644281人6526人84607080901001101201305880人644281人6526人85安排d-i各工序的总人数为6586idF+ggH+i607080901001101201305864426526人 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图

22、12-18所示，在不增加工人的情况下保证了工程按期完成。872.时间-费用优化工期不变，就是关键工作时间不能调整资源不平衡将导致资源不足利用时差，调整非关键路线上工作的开始时间，使资源实现平衡。882 统筹方法2.时间-费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。 直接费用：为了加快工程进度，必须设法缩短关键工序的时间，这样需要增加人力、设备和工作班次，从而需要增加一笔费用，成为直接费用。 间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说

23、工序越短，直接费用越多，间接费用越少。892 统筹方法 工序的最快完成时间：指完成时间的最高限度。 我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有 时间-费用优化问题可建立两个线性规划模型。 模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。 设工序（i ,j)的提前完工时间为Yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i ,j)的实际完工时间为：Tij-Yij。我们用Ci

24、j,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。902 统筹方法例7. 例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。 表12-17工序Tij正常完工Cij直接

25、费用Tij最快完工Cij直接费用直接费用变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-912 统筹方法 该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？12345678abfechgijd图12-19922 统筹方

26、法解：绘出如图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-y67932 统筹方法 x1 =0, y120, y2715, y23 5 y24 10

27、y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0，yij 0.（对一切可能的ij)运算得到结果：f=6400。942 统筹方法 模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为： 目标函数min f=d(xn-x1)+ s.t. xj-xi Tij-yij，对一切弧（i ,j) yijTij-Tij ，对一切弧（i ,j) xi 0， y

28、ij 0。952 统筹方法 例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.962 统筹方法x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y2