施工工序安排问题的数学模型.doc

1、施工工序安排问题的数学模型摘要 本问题是一个施工工序安排的问题，各道工序的完成时间不同，并且一些工序有顺序约束，要求是进行合理的安排，使得总工程的完成时间最短。对于第一问，即是求出关键路径和完成总工程的最短时间，可以直接建立图形（PT图或PERT图），通过最早开工时间算法完成。第二和第三问，是求某道工序的完成时间发生变化时，对整个工程进度的影响，可以通过改变原图中的参数，用相同的方法解答。对于第四问，是求某一道工序的最晚开工时间，可通过最晚开工时间算法求出。第五问是求应该采取何种措施才能使总的完成时间缩短到75d内，则应该全盘分析，综合考虑。 本文采用的是方法是画PT图解答。对于前面四个小问，

2、我运用了PT图的相关结论和算法，计算出关键路径、最早开工时间、最晚开工时间。本文假设在先行工序完成的情况下，某几项工序可以同时进行。而在实际中，安排工序还要考虑人力、物力、环境等问题。因此，可以对模型做进一步的改进，增加一些限制条件，比如最多可以同时进行几道工序，每一道工序的成本等，从而得出更合理的安排。关键词：工序安排 PT图 最早开工时间 最晚开工时间 关键路径一、 问题重述工程的实施，需要制定合理的计划。通过经验或者调查，得出各道工序的完成时间，从而制定高效的施工方案，可以节约时间和资源，对于社会发展有着重要意义。本题给出了一个汽车库及引道的施工计划（所需工序以及每一道工序的完成时间、紧

3、前工序），每一道工序都必须在它的紧前工序完成后才能开始。所给的条件如下：工序名称时间/d紧前工序1234567891011121314清理场地，准备施工备料车库地面施工墙及房顶桁架预置车库混凝土地面保养竖立墙架竖立房顶桁架装窗及边墙装门装天花板油漆引道混凝土施工引道混凝土保养清理场地，交工验收1086162444104121682441,2234,566678,9,1031211,13第一问要求出关键路径和该项工程的最短周期。第二问是在第一问的基础上，考虑工序12的施工工期拖延10d，对整个工程进度有何影响。第三问是考虑工序10的施工时间缩短4d，对整个工程进度的影响。第四问是在第一问的基础上

4、（即总的完成时间最短），计算工序9的最晚开工时间。第五问是假设总的完成时间不超过75d，考虑是否应该采取措施，应该采取何种措施。二、 问题分析每一道工序的完成时间都已在题目中列出，可以画PT图，把工序的先后顺序以及完成时间表示出来，简明直观，便于计算。（一）对于问题一的分析 问题一是在给定PT图的情况下，计算关键路径和总工程的最短周期问题。采用最早开工时间算法。引理：若有向图G中不存在有向回路，则可以将G的结点重新编号为，.，使得对任意的边，都有.则最早开工时间的算法如下：1. 对结点重新编号为，.，（本题中的工序编号已经满足此条件，无需再进行编号）2. 赋初值3. 依次更新 求出最早开工时间

5、，则可计算出总工程的完成时间，也可以找出关键路径(通过计算过程，从逆推）。（二）对于问题二、三的分析二三问是在第一问的基础上进行分析的。第二问中，有，算出，比较与，以及关键路径.第三问也是在第一问的基础上计算，比较.（三）对于问题四的分析 第四问是最晚开工时间的计算,运用的是逆推的方法. 最晚开工时间的算法如下： 1. 赋初值2. 更新 .注：可以计算允许拖延时间，.若，表示工序j不可拖延，在关键路径上.（四）对于问题五的分析 问题五需要综合一、二、三、四问的结论进行合理分析.三、 模型假设1. 假设在紧前工序完成的情况下，所有工序可以同时进行2. 假设题目所给的数据属实合理3. 假设人力和物

6、力充足，不考虑劳动力和成本问题四、 定义与符号说明：第j道工序（用点表示），均为虚设结点，表示开始和结束.：第j道工序的最早开工时间.：第j道工序的最晚开工时间.：第j道工序的允许拖延时间.五、 模型的建立与求解作出PT图，如图所示.图箭头方向表示工序的先后顺序.每一条路径上的数字表示工序的完成时间，如到的箭头上的数字10表示工序1需要10d完成. 第一问：求出.,.则该项工程从施工开始到全部结束的最短周期为80d，关键路径为第二问：不在关键路径上.若按照第一问求出的最早开工时间来算，应该加10，即，.则，.从以上计算，可以得出，工序12的工期拖延10d,并没有导致工程的总完成时间增加，关键路

7、径也不变，只是导致工序13的工期拖延了10d.第三问：工序10的施工时间缩短4d，则PT图上的权值改为8，其余不变，如图.图记此时各工序的最早开工时间为，则，.经过计算对比，发现工序10的施工时间缩短4d,工序11、14的开工时间都可以缩短4d，整个工程的总完成时间也缩短4d.关键路径不变.第四问： 计算最晚开工时间.，.则工序9最晚应从第56d开工.检验第一问中求出的关键路径.计算，得,.则关键路径为，与第一问得出的结论相符.第五问：第一问计算出，该工程需要80d完成，因此，需要采取措施，才能在75d内完工.需要时间最长的工序是5和13，其中5处于关键路径中，13不在关键路径中.因此，有一种

8、措施是缩短工序5（即车库混凝土地面保养）的时间.如果把工序5的时间缩短到19d,则工序6、7、8、9、10、11、14都可提前5天开工，总的施工时间为75d.如果关键路径不变，则如果要使总施工时间减少，就应该使关键路径上的某一道或者某几道工序的时间缩短.而其中比较好的方案，是使原来花费时间比较长的工序的时间缩短.比如，受第三问的启发，可以把工序10的施工时间缩短5d.上一段提到的缩短工序5的时间，也是一种方法.也可以把需要缩短的5d分散到某几道工序中.六、 对模型的评价按照题目所给的条件和要求，前四个小问，本模型得出了正确的结论，第五问的分析也比较合理。应该说，题目考虑的因素很简单，实际上，制定一个施工计划，不仅仅是考虑每一道工序的时间，还要考虑人力物力、成本、污染等问题，可以在模型中增加一些约束条件，使模型更符合实际。本模型运用的算法比较容易理解，PT图也直观明了，这样的算法可以推广。在实际问题中，如果其他因素对施工时间的影响不大，可以运用本模型的相关算法和结论。七、 参考文献【1】任兴龙，数学建模中图论的知识5 【2】数学建模（本科册），华中科技大学出版社