一种用于求解项目时间管理问题的前k个最优解的新算法
发布时间：2021-03-05 18:13
项目管理问题（Project Management Problcm,PMP）是一个多目标优化问题,它通常需要考虑三个相互冲突的优化目标:时间,质量和成本。大多数现存的方法只能为项目管理问题求解近似的Parcto前沿。理论上,如果能够针对每个单目标优化问题找出前k个单目标最优解,则基于所有单目标优化问题的前k个单目标最优解,就可以保证找到离散多目标优化问题（比如PMP）的完整Parcto前沿。因此,求解多目标优化问题的完整Parcto前沿的关键是要设计有效的方法以求解出每个单目标优化问题的前k个单目标最优解。本文针对如何计算项目时间管理问题（Project Time Management Problem,PTMP）的k个最优解,提出了一种涟漪扩散算法,该算法通过模仿自然涟漪扩散现象,从而确定管理项目的前k个最佳方案,使得项目总时间最短。对比实验证明了新方法的有效性。
【文章来源】：系统工程. 2020,38(06)北大核心CSSCI
【文章页数】：11 页
【部分图文】：
图２将项目网络转换为路由网络??新算法实际就是在２．２小节生成的路由网络中模拟??
模式结点２的涟漪同时到达结点５和结点６。??现在，工作任务２的涟漪和工作任务１的涟漪已经都到达??了结点５和结点６，因此在ｆ?＝?４时，结点５和结点６处触??发了两个新的涟漪。在ｆ?＝?５时，结点６的涟漪到达虚拟??结点７。在本例中，结点７只需要完成工作任务３，因此，??结点７在ｆ?＝?５时将产生一个新的涟漪。然后涟漪接力赛??停止，就可以得出第一最优解是三个工作任务都选择模式??２，最短的项目总时间是２５（真实时间单位??（ａ）相关路由网络??（ｂ）寻找第一最短项目时间??图３寻找第一个最短的项目时间的涟漪接力赛??３．２扩展ＲＳＡ以计算ＰＴＭＰ的前々个最优解??在３．１节提出的涟漪扩散过程中，每个结点最多只能??产生一个涟漪，所以它只能找到第一个最佳解决方案。但??如果允许每个结点产生多个涟漪，那么通过对ＲＳＡ进行??一些相应的修改，上述涟漪接力赛就可以被扩展用以解算??ＰＴＭＰ的前＆个最优解。首先将ｉＶｐ设置为没有前序结??点的模式结点的数量。对所有的ｉ?＝?ｌ，…，，进行初始??化，即?ｒ?（?Ｄ?＝?０，ＶｗＭＮ?（?Ｄ?＝?〇?和?Ｖｗｐ．ｖｉｎ?（ｆ）＝〇。然后令??，幻表示当前涟漪是在模式结点Ｇ处产生的第是??个链満１，？？？（ｉｊ？），其中Ｎｔｊ？（纟）表ＺＫ在模式结??点Ｇ处触发的涟漪总数。最后设为模式结点Ｇ??的所有输人涟漪的集合，并将其初始化，即Ｄｍ?（Ｇ）＝０．??假设我们需要找到个最优解，则步骤如下。??步骤１：同小节３．１?—样，初始化仿真参数，如??和ＭＰＡ?．并让ＪＶｐ记录当前涟漪的总数，ｒ（ｉ?）记录第ｆ??个涟漪的半径，ＶＷＭＮ（ｉ）记录产生第ｉ个涟漪的模式结点。??
式３??模式１??模式２??模式３??模式１??模式２??模式３??２Ｓ??３３??２５??２８??２１??３０??２５??３４??３２??任务７的时Ｉ＇ｆｌ??ｔ务８的时间??任务９的时间??模式１??模式２??模式３??模式１??模式２??模式３??模式１??模式２??模式３??２８??２３??３１??２０??２Ｓ??２５??３４??２８??３７??任务１０的时??司??模式１??模式２??模式３??３０??３６??３９??（ａ）任务和模式时间??（ｃ）转换成路由网络??图５测试用例中的项目网络??表３给出了?１００个随机测试用例的平均结果。对于??ＲＳＡ，将ｉＶｓｓ设置为２０；对于ＧＡ？，米用最后一＇代的肖！ｊ?２０??个最佳解决方案与ＲＳＡ进行比较。从表３中可以的出以??下结论：（１）根据每种算法找到的前２０个最佳解决方案，??ＲＳ八的平均项目时间比ＧＡ的平均项目时间短约５％．??（２）在１００个测试用例中，其中有９７个由ＲＳＡ发现的前??２０个最佳解决方案具有相同的项目时间，而由ＧＡ发现??的前２０个最佳解决方案大多数情况下具有不同的项目时??间。这说明ＧＡ很难可靠地找到具有相同的全局最小项??目时间的所有最佳解决方案。另外３个测试用例中，虽然??利用ＲＳＡ计算出来的２０个最佳解决方案具有不同项目??时间，但是通过手工计算进行验证，结果显示拥有全局最??小项目时间的最佳解决方案的数量确实少于２０个，并且??ＲＳＡ所给出的结果中包含了所有这些最佳解决方案。??（３）平均而言，一个测试用例中ＲＳＡ所找到的具有最小项??目时间的解决方案的数目比ＧＡ多约５０％．（４）在算法运??行时间上，ＲＳＡ比ＧＡ
【参考文献】：
期刊论文
[1]基于粒子群算法的项目工期—成本—质量—安全的综合优化[J]. 杜学美,赵文林,雷玮. 系统工程. 2019(04)
[2]基于改进遗传算法的工程项目多目标优化研究[J]. 王玫婷,张建坤,黄有亮. 建筑经济. 2017(11)
[3]有关时间管理对工程项目管理的作用探索[J]. 竺颖杰. 科技创新与应用. 2015(33)
[4]求解多目标优化问题的新遗传算法[J]. 韩丽霞. 计算机科学. 2013(S1)
[5]进化多目标优化算法研究[J]. 公茂果,焦李成,杨咚咚,马文萍. 软件学报. 2009(02)
[6]一种评估近似Pareto前沿多样性的方法[J]. 曾三友,蔡振华,张青,康立山. 软件学报. 2008(06)
本文编号：3065638
【文章来源】：系统工程. 2020,38(06)北大核心CSSCI
【文章页数】：11 页
【部分图文】：
图２将项目网络转换为路由网络??新算法实际就是在２．２小节生成的路由网络中模拟??
模式结点２的涟漪同时到达结点５和结点６。??现在，工作任务２的涟漪和工作任务１的涟漪已经都到达??了结点５和结点６，因此在ｆ?＝?４时，结点５和结点６处触??发了两个新的涟漪。在ｆ?＝?５时，结点６的涟漪到达虚拟??结点７。在本例中，结点７只需要完成工作任务３，因此，??结点７在ｆ?＝?５时将产生一个新的涟漪。然后涟漪接力赛??停止，就可以得出第一最优解是三个工作任务都选择模式??２，最短的项目总时间是２５（真实时间单位??（ａ）相关路由网络??（ｂ）寻找第一最短项目时间??图３寻找第一个最短的项目时间的涟漪接力赛??３．２扩展ＲＳＡ以计算ＰＴＭＰ的前々个最优解??在３．１节提出的涟漪扩散过程中，每个结点最多只能??产生一个涟漪，所以它只能找到第一个最佳解决方案。但??如果允许每个结点产生多个涟漪，那么通过对ＲＳＡ进行??一些相应的修改，上述涟漪接力赛就可以被扩展用以解算??ＰＴＭＰ的前＆个最优解。首先将ｉＶｐ设置为没有前序结??点的模式结点的数量。对所有的ｉ?＝?ｌ，…，，进行初始??化，即?ｒ?（?Ｄ?＝?０，ＶｗＭＮ?（?Ｄ?＝?〇?和?Ｖｗｐ．ｖｉｎ?（ｆ）＝〇。然后令??，幻表示当前涟漪是在模式结点Ｇ处产生的第是??个链満１，？？？（ｉｊ？），其中Ｎｔｊ？（纟）表ＺＫ在模式结??点Ｇ处触发的涟漪总数。最后设为模式结点Ｇ??的所有输人涟漪的集合，并将其初始化，即Ｄｍ?（Ｇ）＝０．??假设我们需要找到个最优解，则步骤如下。??步骤１：同小节３．１?—样，初始化仿真参数，如??和ＭＰＡ?．并让ＪＶｐ记录当前涟漪的总数，ｒ（ｉ?）记录第ｆ??个涟漪的半径，ＶＷＭＮ（ｉ）记录产生第ｉ个涟漪的模式结点。??
式３??模式１??模式２??模式３??模式１??模式２??模式３??２Ｓ??３３??２５??２８??２１??３０??２５??３４??３２??任务７的时Ｉ＇ｆｌ??ｔ务８的时间??任务９的时间??模式１??模式２??模式３??模式１??模式２??模式３??模式１??模式２??模式３??２８??２３??３１??２０??２Ｓ??２５??３４??２８??３７??任务１０的时??司??模式１??模式２??模式３??３０??３６??３９??（ａ）任务和模式时间??（ｃ）转换成路由网络??图５测试用例中的项目网络??表３给出了?１００个随机测试用例的平均结果。对于??ＲＳＡ，将ｉＶｓｓ设置为２０；对于ＧＡ？，米用最后一＇代的肖！ｊ?２０??个最佳解决方案与ＲＳＡ进行比较。从表３中可以的出以??下结论：（１）根据每种算法找到的前２０个最佳解决方案，??ＲＳ八的平均项目时间比ＧＡ的平均项目时间短约５％．??（２）在１００个测试用例中，其中有９７个由ＲＳＡ发现的前??２０个最佳解决方案具有相同的项目时间，而由ＧＡ发现??的前２０个最佳解决方案大多数情况下具有不同的项目时??间。这说明ＧＡ很难可靠地找到具有相同的全局最小项??目时间的所有最佳解决方案。另外３个测试用例中，虽然??利用ＲＳＡ计算出来的２０个最佳解决方案具有不同项目??时间，但是通过手工计算进行验证，结果显示拥有全局最??小项目时间的最佳解决方案的数量确实少于２０个，并且??ＲＳＡ所给出的结果中包含了所有这些最佳解决方案。??（３）平均而言，一个测试用例中ＲＳＡ所找到的具有最小项??目时间的解决方案的数目比ＧＡ多约５０％．（４）在算法运??行时间上，ＲＳＡ比ＧＡ
【参考文献】：
期刊论文
[1]基于粒子群算法的项目工期—成本—质量—安全的综合优化[J]. 杜学美,赵文林,雷玮. 系统工程. 2019(04)
[2]基于改进遗传算法的工程项目多目标优化研究[J]. 王玫婷,张建坤,黄有亮. 建筑经济. 2017(11)
[3]有关时间管理对工程项目管理的作用探索[J]. 竺颖杰. 科技创新与应用. 2015(33)
[4]求解多目标优化问题的新遗传算法[J]. 韩丽霞. 计算机科学. 2013(S1)
[5]进化多目标优化算法研究[J]. 公茂果,焦李成,杨咚咚,马文萍. 软件学报. 2009(02)
[6]一种评估近似Pareto前沿多样性的方法[J]. 曾三友,蔡振华,张青,康立山. 软件学报. 2008(06)
本文编号：3065638
本文链接：https://www.wllwen.com/guanlilunwen/xiangmuguanli/3065638.html
