十一章 排序与统筹.ppt

《十一章 排序与统筹.ppt》由会员分享，可在线阅读，更多相关《十一章 排序与统筹.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、十一章 排序与统筹（p234)1.车间作业计划模型一、一台机器、几个零件的排序问题例1 应该按照什么样的加工顺序来加工零件，使所有零件在车间停留的平均时间最少。零 件加工时间（小时）1234561.82.00.50.91.31.5 设第j次加工零件在车间停留的时间为Tj,第i次加工零件的加工时间Pi，择有 Tj=P1+P2+Pj-1+Pj所有零件在车间停留的平均时间为 T1+T2+T3+T4+T5+T6=P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)=6P1+5P2+4P3+3P4+2P5+P6两

2、台机器，n个零件例2 零件车窗磨床123451.52.01.01.250.750.50.251.752.51.25顺序12345零件534122.统筹方法一 计划网络图(p241)例3工序代号工序内容所需时间（天）紧前工序abcde产品与工艺设计外购配套零件外购生产原料自制主件可靠性测试601513388-aacb,d12345abcde601513388例4（p242)工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338-aacefgh810165b,ddde,f,g12356abcde601513388410f习题4工序代号紧前工序工序代号紧前工序abcd-

3、a，ba，befgbcd,e13467acdeb5gf2二、网络时间与关键路线在绘制出网络图后，我们可以根据网络图求出：1.完成此工程项目所需的最少时间。2.每个工序的开始时间与结束时间。3.关键路线及其相应的关键工序。4.非关键工序在不影响工程进度的前提下，其开始时间与机务时间可以推迟多久。例5.工序代号工序内容所需时间（天）紧前工序abcdefghij生产线设计外购零配件下料、锻件工装制造1木制、锻件机械加工1工装制造2机械加工2机械加工3装配调试60451020401830152535-aaaacdd,egb,i,f,h12846acdeb5gf73451810602040hij3025

4、3515路线：在网络图上从出发点开始，沿着弧的方向连续地到达 收点的一条路。关键路线：网络图中最长的路线。12781237812578124678长度=140长度=123长度=150长度=170寻找关键路线的方法 用ES表示一个工序最早开工时间，用EF表示一个工序最早完工时间，用t表示一个工序所需时间。我们有 EF=ES+t 用ES,EF放在工序的上面来记录一个工序的最早开工时间和最早完工时间。12846acdeb5gf73451810602040hij302535150,6060,105135,170110,13580,11060,8070,8860,10060,70100,115用LS表示

5、一个工序最晚开工时间，用LF 表示一个工序最晚完工时间。用LS,LF放在工序的下面来记录一个工序的最晚开工时间和最晚完工时间。12846acdeb5gf73451810602040hij302535150,6060,105135,170110,13580,11060,8070,8860,10060,70100,115107,11790,135117,135135,170110,13580,11060,800,6080,120120,135用Ts表示工序的时差 Ts=LS-ES=LF-EF 如，对于B工序，Ts=90-60=30 对关键路线上的所有工序，其时差都为零。例5工序所需时间紧前工序工序

6、所需时间紧前工序abcd2454-a,ba,befg324bcd,e13256acdeb4gf2524434关键路线最早完工时间12天最晚开工时间和完工时间13256acdeb4gf25244340,24,90,44,74,88,129,111234613256acdeb4gf2524340,24,90,44,74,88,129,118,124,810,125,102,45,80,44网络优化1.时间资源优化 为了使工程进度与资源利用都得到比较合理安排，可采取以下的做法：1)优先安排关键工序所需要的资源。2)利用非关键工序曲时差，错开各工序的开始时间，拉平资源需要量的高峰。3)要统筹兼顾工程进

7、度的要求和现有资源的限制往往要经过多次综合平衡，才能得到比较合理的计划方案。工人人数65工序加工工人人数最早开工时间所需时间时差dfghi582242392660708010010020183015250470200347fgd6i218203025(58人）(22人）(42人）(26人）(39人）155h2.时间-费用优化 在既定时间完成工程的前提下，使得费用最少，或者在不超过工程预算的条件下，使得工程最早完工。缩短工序的作业时间的限度称为工序的最快完成时间。设完成工序j的正常所需时间为Tj;直接费用为cj；最快完成时间为 ，直接费用为 。缩短工序一天工期所减少的直接费用，我们用kj表示，有 kj=模型一 设网络图上点i发生的时间为xi。T表示既定的时间。对一个工序，我们既可以用工序的代号来表示，也可以用表示这个工序的弧(i,j)来表示。设工序(i,j)的提前完工时问为ij，则有工序(i,j)的实际完工时间为：Tij-ij性规划模型如下：min f=s.t.xj-xi Tij ij ,对一切弧(i,j)ij Tij ,对一切弧(i,j)Xn T,xi,ij 0