管理运筹学第十二章 排序与统筹方法

管理运筹学第十二章排序与统筹方法2第十二章排序与统筹方法

本章包含车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。

3车间作业计划模型统筹方法本章内容124§1车间作业计划模型一、一台机器、n个零件的排序问题二、两台机器、n个零件的排序问题车间作业计划是指一个工厂生产工序的计划和安排。5§1车间作业计划模型例1.某车间只有一台高精度的磨床，现有六个零件同时要求加工，六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工，才能使得这六个零件在车间里停留的平均时间为最少？一、一台机器、n个零件的排序问题零件加工时间（小时）零件加工时间（小时）1231.82.00.54560.91.31.56§1车间作业计划模型设Pi表示安排在第i位加工的零件所需的时间，Tj表示安排在第j位加工的零件在车间里总的停留时间，则例1解：可知这六个零件的停留时间为：

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.7§1车间作业计划模型那么各个零件平均停留时间为总结：一台机器n个零件的排序问题

只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。例1中按照3,4,5,6,1,2的顺序加工零件，则各个零件的平均停留时间最少8§1车间作业计划模型二、两台机器、n个零件的排序问题例2.某工厂定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如下表所示。应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？零件车床磨床123451.52.01.01.250.750.50.251.752.51.259§1车间作业计划模型解：如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用下面的线条图来表示各零件加工的开始时间与完成时间。

123451车床磨床2345010由图得，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。10§1车间作业计划模型在该表中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2所在行。如表中红色线条所示。

零件车床（第一工序）磨床（第二工序）零件车床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25接着，又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把表中的零件1所在的行划去。如表中黄色线条所示。

下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所示。下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。寻找例2的最优解：⑤④①②11§1车间作业计划模型总结：关于两台机器n个零件的排序问题

步骤1：在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。步骤2：在表上划去零件j的所在行，回到步骤1。12车间作业计划模型统筹方法本章内容1213§2统筹方法

统筹方法可以应用在各种不同的项目计划上，特别适用于生产技术复杂，工作项目繁多且联系紧密的一些跨部门的工作计划，例如，新产品的研制开发，工厂、大楼、高速公路等大型工程项目的是建设，大型复杂设备的维修以及新系统的设计与安装等计划。

统筹方法包括绘制计划网络图、进度安排、网络优化等环节

14§2统筹方法一、计划网络图

统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。工序代号工序内容所需时间（天）紧前工序abcde产品设计和工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb，d例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。表12-8

15§2统筹方法用网络图表示上述的工序进度表点表示一个事件弧表示一个工序

１２４５３abcde601383815图12-4１２４５３abcde601383815图12-4１２４５３abcde601383815１２４５３abcde601383815１２４５３abcde601383815１２４５３abcde60138381516§2统筹方法

例４、把例３的工序进度表做一些扩充，如表12-9，请画出其统筹方法的网络图。

表12-9

工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338-aacefgh810165b,ddde,f,g17§2统筹方法解：引入虚工序虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。

152643a60b158e1013dc38f图12-518§2统筹方法

接着在网络图上添加ｇ、ｈ工序得网络图12-6。

601256734a15bec13d388h510fg16图12-619§2统筹方法在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图12-7，即例4的最终统筹方法网络图。

1257834a6015bec13d388h510f616g图12-7

注意：在绘制统筹方法的网络图时，图中不能有缺口和回路。20§2统筹方法二、网络时间与关键路线

在绘制出网络图之后，我们可以由网络图求出：

完成此工程项目所需的最少时间每个工序的开始时间与结束时间关键路线及其应用的关键工序非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久21§2统筹方法例5、某公司装配一条新的生产线，具体过程如表12-10,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。

表12-10工序代号工序内容所需时间（天）紧前工序abcdefghij生产线设计外购零配件下料、锻件工装制造1木模、铸件机械加工1工装制造2机械加工2机械加工3装配调试60451020401830152535-aaaacdd，egb，i，f，h22§2统筹方法解：据表12-10,绘制网络图如图12-8。

12346785a60b45echj35i1030d204025f1815关键路线：网络中最长的路线，决定了完成整个工程所需的最少时间此图中①-②-③-⑦-⑧为关键路线,由工序a，c，f，j组成。图12-823§2统筹方法下面给出找关键路线的办法

工序a的最早开始时间工序a的最早完成时间12a[0，60]60图12-9首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有EF=ES+t。例该题中的工序a，如图12-9所示。24§2统筹方法

依照上述最早开始时间法则以及EF=ES+t的关系，可以依次算出此网络图中的各弧的最早开始时间与最早完成时间，如图12-10所示

6123785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015图12-106123785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015图12-1025§2统筹方法

其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一工序有LS=LF-t，且任一工序的最晚结束时间等于其所有紧后工序的最晚开始时间中的最早时间。

运用上述法则，从收点开始可计算出每个工序的LF与LS如图12-11所示。

图12-1165i[110.135]25[110,135]12378a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]f[70,88]18[117,135]410[107,117]15[120,13526§2统筹方法接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为Ts，有Ts=LS-ES=LF-EF例，对于工序b来说，其时差为Ts=LF-EF=90-60=30

对于工序g来说，其时差为Ts=LF-EF=80-80=0

由此可知工序b是非关键工序，工序g为关键工序，一般说关键工序的时差都为0。27§2统筹方法

最后将各工序的时差，以及其他信息构成工序时间表如表12-11所示。

这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。工序最早开始时间（ES）最晚开始时间（LS）最早完成时间（EF）最晚完成时间（LF）时差（LS-ES）是否为关键工序abcdefghij0606060607080100110135090107608011780120110135601057080100881101151351706013511780120135110135135170030470204702000是否否是否否是否是是28§2统筹方法例6.长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制出统筹方法的网络图，求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。活动（工序）活动（工序）内容紧前活动（工序）abcdefghi制定培训计划选聘培训教师列出一些可供选择的培训地点确定培训地点确定培训的日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最后的一些事务-a-cb，dcb，dgf，g表12-12三、完成工序所需时间不确定时的网络时间与关键路线29§2统筹方法解：由表12-12，绘出统筹方法的网络图如图12-12所示12356487abecdfghi

图12-1230§2统筹方法由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。如表12-13所示：

活动乐观时间最可能时间悲观时间abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5表12-13单位：周31§2统筹方法显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从β分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差

例如：完成工作g所需平均时间：

同时求出方差为32§2统筹方法同样可以求出每个活动的完成所需平均时间及方差，如表12-14：表12-14

活动T（平均时间）方差abcdefghi2322124420.0280.4450.1110.0280.0280.1110.4450.1110.02833§2统筹方法

下面用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-14所示。12345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]322214242图12-1434§2统筹方法

同样也可以标上最晚开始时间和最晚完成时间等，如图12-15所示。12345876a[0,2]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]2[1,3]1[10,11]4[5,9]4[9,13]2[3,5]2[0,2]3[2,5]2[13,15]2[11,13]图12-15g[5,9]35§2统筹方法

求出时差Ts=LF-EF，把这些填入工序时间表12-15中表12-15活动最早开始时间（ES）最晚开始时间（LS）最早完成时间（EF）最晚完成时间（LF）时差（LS-ES）是否为关键工序abcdefghI0202565913021310115913252468913152535111391315001155000是是否否否否是是是由上表得关键路线是由关键工序a，b，g，h，i组成的。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）由上表得关键路线是由关键工序a，b，g，h，i组成的。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）36§2统筹方法四、网络优化1.时间-资源优化做法：

1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。37§2统筹方法列举一个拉平资源需要量最高峰的实例。在例5中，若完成工序d，f,g,h,i加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：工序需要工人人数最早开始时间所需时间时差d5860200f22701847g4280300h391001520i2611025038§2统筹方法若上述工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人人数如图12-17所示。

642人42735f(22人）18h(39人)1558人64人80人81人26人65人6080100120130d(58人）i(26人）g(42人）302025图12-17时间/天39§2统筹方法

应优先安排关键工序所需的工人，再利用非关键工序的时差错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。608010012013065人58人42人64人26人65人246753f(22人）h(39人）d(58人）i(26人）g(42人）工人数图12-18时间/天40§2统筹方法2.时间-费用优化

在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj；直接费用为cj；完成工序j的最快完成时间为T`j,直接费用为c`j。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有

费用又分