Chapter 12 Network Plot.pptx

管理运筹学主讲教师：李愉心第12章排序与统筹方法12.1车间作业计划模型12.2绘制网络图12.3网络参数12.4网络的优化2016年12月17日星期六在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。2016年12月17日星期六§1　车间作业计划模型2016年12月17日星期六§1　车间作业计划模型一、一台机器、n个零件的排序问题例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？零件加工时间（小时）零件加工时间（小时）1231.82.00.54560.91.31.52016年12月17日星期六§1　车间作业计划模型例1解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有　　　　　　　　　Tj=P1+P2+…+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=2016年12月17日星期六可知这六个零件的停留时间为：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.那么各个零件平均停留时间为从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。2016年12月17日星期六各个零件平均停留时间为：零件加工时间停留时间零件加工时间停留时间30.50.561.54.240.91.411.86.051.32.732.082016年12月17日星期六二、两台机器，n个零件问题的提出：设有n个工件需要在Ａ、Ｂ机床上加工，每个工件都必须经过先Ａ后Ｂ两道加工工序，以ai、bj分别表示工件i(1≤i≤n)在Ａ、Ｂ上的加工时间，问如何安排在两机床上各工件的加工顺序，使在机床Ａ上加工第一个工件开始到在机床Ｂ上加工完最后一个工件为止，所用的加工总时间最少？2016年12月17日星期六例：问如何安排，使连续加工完所有工件的加工总时间最少？加工时间机床ＡＢ工件D1a1＝2b1=5D2a2=6b2=1D3a3=3b3=62016年12月17日星期六编号加工次序加工中时间衔接情况总时间①D1D2D3A:B:②D1D3D2A:B:③D3D1D2A:B:2653161723566114326561152016年12月17日星期六三种工件加工次序共有3!＝6种，以上表格列出三种情况；从表中可知，不论哪种次序，在机床Ａ上加工总时间都是11，比较①②可见，在机床Ｂ上加工时间最短的放在最后加工，可以节省等待时间，∴②的总时数要小。比较②③可见，在机床Ａ中加工时间最短的放在前面加工，就可较早地开始在机床Ｂ上加工，因而②总时数要小。2016年12月17日星期六最优排序规划：(1)先作工件的加工时间的工时矩阵;(2)在工时矩阵Ｍ中找最小元素(若不止一个，任取一个)，若它在上行，将相应的工件排在最前面加工，若它在下行，则将相应的工件排在最后加工。(3)将排定位置工件的对应列从Ｍ中划掉，然后对余下的工件重复(2)，直到所有工件排完。2016年12月17日星期六例：Ｍ＝加工次序：3745762734*D2*D1*D4*D3*D5总工时＝28：364775473212.2绘制网络图Drawnetworkplot2016年12月17日星期六用网络图编制的计划称为网络计划，网络计划技术由计划协调技术（ProgramEvaluationandReviewTechnique简写为PERT）与关键路径法（CriticalPathMethod简写为CPM）组成。12.2.1项目网络图的基本概念PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。12.2绘制网络图DrawnetworkplotCPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互