排序与统筹方法

第十二章排序与统筹方法§1车间作业计划模型§2统筹方法在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。1§1车间作业计划模型车间作业计划是指一个工厂生产工序的计划和安排。一、一台机器、n个零件的排序问题二、两台机器、n个零件的排序问题2§1车间作业计划模型一、一台机器、n个零件的排序问题例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。

应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？零件加工时间（小时）零件加工时间（小时）1231.82.00.54560.91.31.53§1车间作业计划模型

例1解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有

Tj=P1+P2+…+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=可知这六个零件的停留时间为：

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个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。4§1车间作业计划模型二、两台机器、n个零件

例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表12-5所示。表12-5

应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。零件车床磨床零件车床磨床1231.52.01.00.50.251.75451.250.752.51.255§1车间作业计划模型图12-1从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。123451车床磨床23450106§1车间作业计划模型寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2所在行。如表12-6中红色线条所示。

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

同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间最短的排序算法。在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。在表上划去零件j的所在行，回到步骤1。§1车间作业计划模型8§2统筹方法统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：一、计划网络图统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。表12-8工序代号工序内容所需时间（天)紧前工序abcde产品设计与工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb,d9§2统筹方法解:用网络图表示上述的工序进度表网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数．

１２４５３abcde601383815图12-410§2统统筹方法法例４、把把例３的的工序进进度表做做一些扩扩充，如如表12-9，，请画出出其统筹筹方法的的网络图图。表12-9工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ11§2统统筹方法法解：我们们把工序序ｆ扩充充到图12-4发生了了问题，，由于ｄｄ是ｆ的的紧前工工序，故故ｄ的结结束应该该是ｆ的的开始，，所以代代表ｆ的的弧的起起点应该该是④，，由于工工序ｂ的的结束也也是④，，所以工工序ｂ也也成了工工序ｆ的的紧前工工序，与与题意不不符。为此我们们设立虚虚工序。。虚工序序是实际际上并不不存在而而虚设的的工序，，用来表表示相邻邻工序的的衔接关关系，不不需要人人力、物物力等资资源与时时间。152643a60b158e1013dc38f图12-512§2统统筹方法法在网络图图上添加加ｇ、ｈｈ工序得得网络图图12-6。在统筹方方法的网网络图中中不允许许两个点点之间多多于一条条弧，因因此增加加了一个个点和虚虚工序如如图12-7。。1256734a6015bec13d388h510fg16图12-613§2统统筹方法法在绘制统统筹方法法的网络络图时，，要注意意图中不不能有缺缺口和回回路。1257834a6015bec13d388h510f616g图12-714§2统统筹方法法二、网络络时间与与关键路路线在绘制出出网络图图之后，，我们可可以由网网络图求求出：1、完成成此工程程项目所所需的最最少时间间。2、每个个工序的的开始时时间与结结束时间间。3、关键键路线及及其应用用的关键键工序。。4、非关关键工序序在不影影响工程程的完成成时间的的前提下下，其开开始时间间与结束束时间可以推推迟多久久。例5、某某公司装装配一条条新的生生产线，，具体过过程如表表12-10,求：完完成此工程的最最少时间间，关键键路线及及相应的的关键工工序，各各工序的的最早开开始时间间和非关键工工序在不不影响工工程完成成时间的的前提下下，其开开始时间间与结束束时间可可以推迟多久久。15§2统统筹方法法表12-10工序代号工序内容所需时间（天）紧前工序abcdefghij生产线设计外购零配件下料、锻件工装制造1木模、铸件机械加工1工装制造2机械加工2机械加工3装配调试60451020401830152535/aaaacdd,egb,i,f,h16§2统统筹方法法解：据表表12-10,绘制网网络图如如图12-8。。图12-8如图12-8,①-②-③③-⑦-⑧就是是一条关关键路线线，我们们要干完完所有的的工序就必须走走完所有有这样的的路线，，由于很很多工序序可以同同时进行行，所以以网络中中最长的路线线就决定定了完成成整个工工程所需需的最少少时间，，这条路路线称为为关键路路线。12346785a60b45echj35ig1030d204025f181517§2统统筹方法法下面我们们给出找找关键路路线的办办法首先，从从网络的的发点开开始，按按顺序计计算出每每个工序序的最早早开始时时间（ES)和最最早结束束时间（（EF)，设设一个工工序所需需的时间间为t，，这对于于同一个工序来来说，有有EF=ES+t。。工序a的的最早开始时间间工序a的的最早完成时间间11a[0，，60]60图12-918§2统统筹方法法图12-10其次,从从网络的的收点开开始计算算出在不不影响整整个工程程最早结结束时间间的情况下各个个工序的的最晚开开始时间间(缩写写为LS)和最最晚结束束时间（（缩写为为LF),显然对同同一工序序有LS=LF-t1236785a[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]184101519§2统统筹方法法运用此法法则，可可以从首首点开始始计算出出每个工工序的LF与LS，如如图12-11所示。接着，可可以计算算出每一一个工序序的时差差，把在在不影响响工程最最早结束束时间的条件下下，工序序最早开开始（或或结束））的时间间可以推推迟的时时间，成成为该工工序的时差，，对每个个工序来来说其时时差记为为Ts有Ts=LS-ES=LF-EF1236785a[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]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,13520§2统统筹方法法最后将各各工序的的时差，，以及其其他信息息构成工工序时间间表如表表12-11所所示。这样就找找到了一一条由关关键工序序a,d,g,i和j依次连连接成的的从发点点到收点点的关键路线线。21三、完成成工序所所需时间间与关键键路线当完成工工序所需需时间不不确定的的情况下下如何求求网络时时间和关关键路线线？例6.长长征征研究院院培训中中心负责责明年春春天的各各干部的的工商管管理培训训，培训训中心列列出有关关培训组组织的各各项活动动的信息息如表12-12所示示，要求求绘制出出统筹方方法的网网络图，，设法求求出网络络时间和和关键路路线，并并确定开开始这个个组织工工作的时时间以保保证培训训工作如如期举行行。解：由表表12-12，，绘出统统筹方法法的网络络图如图图12-12所所示。12356487abecdfghi图12-12§2统统筹方法法22§2统统筹方法法

活动（工序）活动（工序）内容紧前活动（工序）abcdefghi制定培训计划选聘培训教师列出一些可供选择的培训地点确定培训地点确定培训的日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最后的一些事务-a-cb,deb,dgf,g23§2统统筹方法法由于是第第一次搞搞培训，，缺乏统统计来确确定完成成每个活活动所需需时间，，但对所需需时间做做了三种种估计：：1.乐观观时间。。指所需需最少时时间，用用a表示示。2.最可可能时间间。指正正常时间间，用m表示。。3.悲观观时间。。指不顺顺利情况况下，最最多时间间，用b表示。。如表12-13所示示：表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.524§2统统筹方法法显然这三三种完成成活动所所需时间间都具有有一定概概率，由由经验，，我们可可以可以假定定这些时时间的概概率分布布近似服服从分分布布。我们们可以用用如下公公式计算出完成成活动所所需的平平均时间间：以及方差差例如：完完成工作作g所需需平均时时间：同时求出出方差为为25§2统统筹方法法同样可以以求出每每个活动动的完成成所需平平均时间间及方差差，如表表12-14：：表12-14活动T（平均时间）方差活动T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02826§2统统筹方法法下面就用用平均时时间代替替完成活活动所需需时间，，并在网网络图上上标上每每个活动最早开开始时间间和最早早结束时时间，如如图12-14所示。。12345876同样也可以以标上最晚晚开始时间间和最晚完完成时间等等。a[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]32221424212345876a[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]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-14图12-1527§2统筹筹方法从表12-15上我我们找到了了一条从发发点到收点点由关键工工序a,b,g,h,i组成成的关键路线，，用双线标标出来。则则完成培训训工作所需需的平均时时间为各关关键路线的时间之和和：=2+3+4+4+2=15（周）同时完成时时间近似服服从一定的的概率分布布正态分布布，则均值值为关键路路线上各关键活活动之均值值之和15，方差也也为关键路路线上各关关键活动方方差之和1.05。。由此我们可可以计算出出此项培训训组织工作作不同完工工时间的概概率，如16周内完工的概概率。为求此概率率，可以先先求u值。。式中的T为为预定完工工时间16，E（T）=15，算得u=0.976。查正态态分布函数数表可知概概率为0.8355。即16周内完工工的概率为83.55%.28§2统筹筹方法其正态分布布图如图12-16所示：16图12-1629§2统筹筹方法四、网络优优化得到初始的的计划方案案，但通常常要对初始始方案进行行调整与完完善。根据据计划目标，综综合考虑资资源和降低低成本等目目标，进行行网络优化化，确定最最优的计划方案。1.时间-资源优化化做法：1）优先安安排关键工工序所需的的资源。2）利用非非关键工序序的时差，，错开各工工序的开始始时间。3）统筹兼兼顾工程进进度的要求求和现有资资源的限制制，多次综综合平衡。。下面列举一一个拉平资资源需要量量最高峰的的实例。在在例5中，，若加工工工人为65人，，并假定这这些工人可可完成这5个工序任任一个，下下面来寻求求一个时间间-资源最优方方案。如表表12-16所示：：30§2统筹筹方法表12-16工序需要人数最早开始时间所需时间时差d5860200f22701847g428030h391001520i26110250若上述工序序都按最早早开始时间间安排，那那么从第60天至第第135天天的75天天里，所需需的机械加加工工人人人数如图12-17所示。31§2统筹筹方法在图的上半半部中，工工序代号后后的数字是是人数，线线下面的数数字是非关关键工序时差长长度。图的的下半部表表示从第60天至135天内内的75天天里，所需需机械加工工人数数，这样的的图称为资资源负荷图图。274635f(22人人）18h(39人人)1558人64人80人81人42人26人65人6080100120130d(58人人）i(26人人）g(42人人）302025图12-1732§2统筹筹方法同时我们应应优先安排排关键工序序所需的工工人，再利利用非关键键工序的时时差，错开各各工序的开开始时间，，从而拉平平工人需要要量的高峰峰。经过调调整，我们让非关键键工序f从从第80天天开始，工工序h从第第110天天开始。找找到了时间间-资源优化的方案案，如图12-18所示，在在不增加工工人的情况况下保证了了工程按期期完成。246753f(22人人）h(39人人）d(58人人）i(26人人）g(42人人）工人数65人608010012013058人42人64人26人65人图12-1833§2统筹筹方法2.时间-费用优化化需要考虑时时间与费用用的问题：：在既定的的时间前工工程完工的的前提下，，使得所需的费费用最少，，或者在不不超工程预预算的条件件下使工程程最早完工工。这些是时间-费费用优化要要研究和解解决的问题题。直接费用：：为了加快快工程进度度，需要增增加人力、、设备和工工作班次，，这需要增加一一笔费用，，成为直接接费用。间接费用：：由于工程程早日完工工，减少了了管理人员员的工资办办公费等费费用称为间接费费用。一般般说工序越越短，直接接费用越多多，间接费费用越少。。34§2统筹筹方法工序的最快快完成时间间：指完成成时间的最最高限度。。我们设完成成工序j的的正常所需需时间为Tj;直接费用用为cj;完成工序序j的最快快完成时间为T`j,直接费用用为c`j。这样我们们可以计算算出缩短工工序j的一一天工期所所增加的直直接费用，用kj表示，称为为直接费用用变动率。。有时间--费费用优化问问题可建立立两个线性性规划模型型。模型一，在在既定的时时间T完工工的前提下下，问各工工序的完成成时间为多多少才使因因缩短工期而而增加的直直接费用最最少。设工序（i,j)的提前完完工时间为为Yij,我们用Tij,T`ij分别表示正正常完工时时间与最快快完工的时间间，则有工工序（i,j)的的实际完工工时间为：：Tij-Yij。我们用Cij,C`ij表示用正常完工时间间和最快完完成时间完完成工序所所需要的费费用，Kij为工序（i,j)的直接费费用变动率。得得到这个问问题的线性性规划模型型如下：minf=（Kij*Yij)（i,j)j-XiTij-Y`ij,对一切弧弧（i,j)YijTij-T`ij,对对一切弧弧（i,j)Xn-X1T,Xi0，Yij0。35§2统筹筹方法例7.例例5所所提供的信信息都作为为本例的信信息，另外外还给出了了在装配过过程中各道道工序所需需正常完工工时间与最最快完工时时间，以及及对应正常常完工时间间与最快完完工时间的的所需的直直接费用和和每缩短一一天工期所所需增加的的直接费用用，如表12-17所示。表12-17工序Tij正常完工Cij直接费用T`ij最快完工C`ij直接费用直接费用变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-36§2统筹筹方法该工程要求求在150天内完工工，问每个个工序应比比正常完工工时间提前前多少天完成，才能能使整个工工程因缩短短工期而增增加的直接接费用为最最少。如果果工期要求在140天完工呢呢？12345678abfechgijd图12-1937§2统筹筹方法解：绘出如如图12-19所示示，根据此此网络图建建立数学模模型。设此网络图图上第i点点发生的时时间为xi，工序提前前完工的时时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.2-x160-y12,x7-x24