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

施工工序安排问题的数学模型 摘要 本问题是一个施工工序安排的问题，各道工序的完成时间不同，并且一些工序有顺序约束，要求是进行合理的安排，使得总工程的完成时间最短。对于第一问，即是求出关键路径和完成总工程的最短时间，可以直接建立图形（PT图或PERT图），通过最早开工时间算法完成。第二和第三问，是求某道工序的完成时间发生变化时，对整个工程进度的影响，可以通过改变原图中的参数，用相同的方法解答。对于第四问，是求某一道工序的最晚开工时间，可通过最晚开工时间算法求出。第五问是求应该采取何种措施才能使总的完成时间缩短到75d内，则应该全盘分析，综合考虑。 本文采用的是方法是画PT图解答。对于前面四个小问，我运用了PT图的相关结论和算法，计算出关键路径、最早开工时间、最晚开工时间。 本文假设在先行工序完成的情况下，某几项工序可以同时进??。而在实际中，安排工序还要考虑人力、物力、环境等问题。因此，可以对模型做进一步的改进，增加一些限制条件，比如最多可以同时进行几道工序，每一道工序的成本等，从而得出更合理的安排。 关键词：工序安排 PT图 最早开工时间 最晚开工时间 关键路径 问题重述 工程的实施，需要制定合理的计划。通过经验或者调查，得出各道工序的完成时间，从而制定高效的施工方案，可以节约时间和资源，对于社会发展有着重要意义。 本题给出了一个汽车库及引道的施工计划（所需工序以及每一道工序的完成时间、紧前工序），每一道工序都必须在它的紧前工序完成后才能开始。所给的条件如下： 工序名称时间/d紧前工序1 2 3 4 5 6 7 8 9 10 11 12 13 14清理场地，准备施工 备料 车库地面施工 墙及房顶桁架预置 车库混凝土地面保养 竖立墙架 竖立房顶桁架 装窗及边墙 装门 装天花板 油漆 引道混凝土施工 引道混凝土保养 清理场地，交工验收10 8 6 16 24 4 4 10 4 12 16 8 24 4— — 1,2 2 3 4,5 6 6 6 7 8,9,10 3 12 11,13 第一问要求出关键路径和该项工程的最短周期。第二问是在第一问的基础上，考虑工序12的施工工期拖延10d，对整个工程进度有何影响。第三问是考虑工序10的施工时间缩短4d，对整个工程进度的影响。第四问是在第一问的基础上（即总的完成时间最短），计算工序9的最晚开工时间。第五问是假设总的完成时间不超过75d，考虑是否应该采取措施，应该采取何种措施。 问题分析 每一道工序的完成时间都已在题目中列出，可以画PT图，把工序的先后顺序以及完成时间表示出来，简明直观，便于计算。 （一）对于问题一的分析 问题一是在给定PT图的情况下，计算关键路径和总工程的最短周期问题。采用最早开工时间算法。 引理：若有向图G中不存在有向回路，则可以将G的结点重新编号为，，...，，使得对任意的边，都有. 则最早开工时间的算法如下： 对结点重新编号为，，...，（本题中的工序编号已经满足此条件，无需再进行编号） 赋初值 依次更新 求出最早开工时间，则可计算出总工程的完成时间，也可以找出关键路径(通过计算过程，从逆推）。 （二）对于问题二、三的分析 二三问是在第一问的基础上进行分析的。第二问中，有，算出，比较与，以及关键路径. 第三问也是在第一问的基础上计算，比较. （三）对于问题四的分析 第四问是最晚开工时间的计算,运用的是逆推的方法. 最晚开工时间的算法如下： 赋初值 更新 . 注：可以计算允许拖延时间，. 若，表示工序j不可拖延，在关键路径上. （四）对于问题五的分析 问题五需要综合一、二、三、四问的结论进行合理分析. 模型假设 假设在紧前工序完成的情况下，所有工序可以同时进行 假设题目所给的数据属实合理 假设人力和物力充足，不考虑劳动力和成本问题 定义与符号说明 ：第j道工序（用点表示），，均为虚设结点，表示开始和结束. ：第j道工序的最早开工时间. ：第j道工序的最晚开工时间. ：第j道工序的允许拖延时间. 模型的建立与求解 作出PT图，如图①所示. 图① 箭头方向表示工序的先后顺序.每一条路径上的数字表示工序的完成时间，如到的箭头上的数字10表示工序1需要10d完成. 第一问：求出. ,, ,, , ,, , ,, , . 则该项工程从施工开始到全部结束的最短周期为80d，关键路径为 第二问：不在关键路径上.若按照第一问求出的最早开工时间来算，应该加10，即，， ， ， . 则，. 从以上计算，可以得出，工序12的工期拖延10d,并没有导致工程的总完成时间增加，关键路径也不变，只是导致工序13的工期拖延了10d. 第三问：工序10的施工时间缩短4d，则PT图上的权值改为8，其余不变，如图②. 图② 记此时