第十一章 排序与统筹方法.ppt

时间 60 70 80 90 100 110 120 130 65 d58 g42 i26 f 22 h 39 f 22 h 39 时间－费用优化 对于工程建设而言： 直接费用：指由直接参与工程的人力、设备、材料等费用。 间接费用：管理人员工资，办公等费用。 一般要加快工程进度，就需要缩短关键工序时间，增加投入人力，设备等直接费用，而另一方面，则可减少办公等间接费用。 工序的最快完成时间： 直接费用 工序的正常完成时间： 直接费用 直接费用变动率： 模型一 在既定的时间T前完工的前提下，问各活动（工序）的完成时间为多少（即各项活动如何加速）才使因缩短工期而增加的直接费用最少。 为工序（i,j）提前完工时间； 分别表示工序的正常完工时间与最快完成时间 表示点i的时间 模型二 设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么总费用与工程最优完成时间T与各工序的最优完成时间的模型： 作业：P261 2 P262 4、5 * * 第十一章 排序与统筹方法 车间作业计划问题 一、一台机器、几个零件的排序问题 例：某车间只有一台高精度的磨床，常常出现很多零件同时要求加工的情况，现有六个零件同时要求加工，这六个零件所需加工时间如表： 零件 1 2 3 4 5 6 加工时间（H） 1.8 2.0 0.5 0.9 1.3 1.5 应按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间最少？ Pi表示安排在第i位加工的零件加工所需时间；Tj表示安排在第j位加工的零件在车间总停留时间。 Tj＝P1+P2+…+Pj= 因为 6个零件停留的总时间： 每个零件平均停留时间： 要MIN 系数最大与加工时间最少匹配。 最优安排：按加工时间排序，加工时间越少的排在前面。 例1要总停留时间最少，则加工顺序为：3，4，5，6，1，2 零件 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 平均停留时间： 二、两台机器，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 0.75 应如何安排加工顺序，才能使总时间最少？ 解：由于每个零件都先经过车床加工再经过磨床加工，所以在车床上加工顺序和磨床上是一致的。 假设按1，2，3，4，5的顺序进行加工 0 3 1 4 2 10 9 8 7 6 5 1 2 3 4 5 1 2 3 4 5 可以看出时间的耽误，主要是由于第二道工序停工待料造成的。减少停工待料的时间，就要车床上需时间越少的越早加工，而磨床上时间越少的越晚加工。 车床 磨床 零件 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 加工顺序： 先早出加工时间最短的零件工序，如果是第一工序，该零件排在前面，如果是第二到工序，排在后面，依次类推。 5 3 4 1 2 0 3 1 4 2 10 9 8 7 6 5 5 3 4 1 2 车床 磨床 5 3 4 12 关于两台机器n个零件的排序问题，使得全部任务的总时间最短的排序算法。 ????1.在加工所需时间表上选出最短加工时间tij，第i工序加工j零件所需时间，当i＝1时，将零件的加工顺序尽量靠前，当i＝2，将零件的加工顺序尽量靠后。 2.在表上划去零件j的所在行或列，返回步骤1。 统筹方法 统筹方法在20世纪50年代末发展起来. 1956年，美国杜邦公司提出关键路线方法（CPM）。 1958年，美国海军武装部提出图解评审法（PERT）。 60年代，我国开始应用这种方法——统筹方法。 一、计划网络图 绘制计划网络图是统筹方法的第一步，即将工序或者活动进度表转换为统筹方法的网络图。 例.某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如下表所示,绘出统筹方法的网络图。 工序代号 工序内容 所需时间（天） 紧前工序 a b c d e 产品设计与工艺设计 外购配套零件 外购生产原料 自制主讲 主配件可靠性试验 60 15 1