基于DEA方法的多模式资源约束项目调度方案选择

摘要

多模式资源约束项目调度问题具有多可行解的特点。考虑到np困难的MRCPSP和复杂的多目标算法，在这些解中寻找最优结果似乎是不可能的。本文采用数据包络分析(DEA)方法对MRCPSP的一系列方案进行评价，并以客观的方式找到合适的方案选择。将该方法应用于一个典型的MRCPSP方案选择，结果验证了DEA方法是一种有效、客观的MRCPSP方案选择方法。

1.介绍

自20世纪60年代以来，资源约束项目调度问题（RCPSP）得到了广泛的研究，一个标准的RCPSP模型已被广泛接受用于完成调度任务。尽管标准的RCPSP模型具有优越性，但它很难覆盖所有的实际情况，并提出了许多有效的扩展。多模式RCPSP（MRCPSP）是其中之一。它最早是由Elmaghraby开发的[1，它允许活动选择多种模式，提供不同的资源和持续时间组合。

以前的研究大多集中在MRCPSP的解决方案上。布鲁克(2]总之，这些算法分为三类：精确算法、启发式算法和元启发式算法。科利希和德雷克勒[3.，证明MRCPSP是否有可行的解决方案是一个NP-hard问题，当两种或两种以上的可再生资源与无限的不可再生资源共存时。

Schnell和Hartl [4]提出了求解具有广义优先关系的MRCPSP的新的精确方法。他们实现了优化框架SCIP，该框架包含两个约束处理程序“cumulative emm”和“gprecedence emm”，并为MRCPSP建立了SCIP模型。他们的解决方案在施加27秒时间限制的情况下，尤其在50项活动中获得了优于预期的结果。最近也出现了一些新的元启发式算法，包括遗传算法杂交和完全知情粒子群[5];一种基于列生成的分布式调度算法[6];一种针对大规模工程的混合优化方法[j]。7]；以及一种有效的基于镜像的遗传算法[8]．在MRCPSP模型扩展方面，有学者考虑了可再生资源休假和活动分割[9]．nematii - lafmejani等人[10]提出了一个综合生物目标优化模型，同时处理MRCPSP和承包商选择（CS）问题。希尔等人[11]提出了一种新的水路船舶调度问题，作为MRCPSP的一种变体，除了任务的最早和最晚开始时间外，还考虑了与时间相关的资源容量。这个问题是通过整数规划解决的，使用了一个紧凑的数学公式。

通常，项目进度计划从三个方面实现最终目标：工期、成本和质量。这些多目标使得已经复杂的MRCPSP更加困难[12].研究人员寻找了不同的方法来解决这个问题。一些学者考虑了两个目标：成本和工期[13]; 一些人试图最大化净现值，最小化持续时间[14];另一些人将所有这三个目标(持续时间、成本和质量)作为优化的目标。15]．

在实践中，工期通常是项目最主要的目标，资源、成本和质量的优先级因项目执行者的不同而不同。对于具有不同优化目标的MRCPSP，可以有多个解决方案，如何以主观的方式对每个方案进行评价成为一个问题。

下面是一个典型的场景。一个项目经理提出了一系列的解决方案，所有的工期都符合公司的战略要求。但是，其他管理人员提出了各自的重点，并提出了不同的建议。例如，首席财务官关注资本投资，首席财务官关注资源，而首席营销官则预测会影响公司形象的质量。因为所有的解决方案都是合理可行的，所以CEO当时面临的困境是如何客观、令人信服地评估这些方案，然后再做出决定。

事实上，由于大量项目的可用性以及各种定性和定量标准的存在，项目选择是关键和复杂的。决策可能涉及企业的长期承诺。尽管文献中提出了各种项目选择方法，Naldi等人。 [16，他们采用背包型整数线性规划公式优化预算分配的质量指标，采用了相当广泛的公平措施选择。Liu等[17]，提出了一种新的基于球形模糊集的多属性决策方法，用于云南白药牙膏研发项目的选择。然而，上述方法虽然是有效的，但都是针对具体类型的项目选择，这也很复杂，需要事先进行大量的信息处理。

此外，这些方法中最引人注目的是数据包络分析(DEA)。DEA是一种衡量决策单元生产效率的非参数方法，涉及多输入多输出。该方法最早由Charnes等人提出[18]，但它植根于德布鲁的研究[19]，库普曼[20]，和法雷尔[21]关于生产效率的度量。由于其在绩效评估方面的专业知识，该方法在理论和实践上都取得了巨大的飞跃。研究人员已经应用DEA模型来解决运输系统、医疗保健、资源分配、能源和环境经济学、区域和国家可持续性问题以及与供应链相关的问题。最近对DEA的概述见Mahmoudi等人[22， Kohl等[23， Yang等人[24]，Mardani等人[25， Zhou等人[26， Soheilirad等人[27，库克和塞福德[28]和刘等人[29]．

迄今为止，DEA已被应用于建筑项目的方案选择[30]，以及研究及发展建议[31，资讯计划[32，33和六西格玛项目[34]．尽管MRCPSP是在受执行者主观直觉和意见影响的情况下客观地选择最有效的项目，但是如何评估和选择MRCPSP的解决方案却鲜有讨论。有两个主要区别。首先，项目选择问题涉及从大量的项目中选择一组最优的可行方案，并最大限度地利用可用资源，而MRCPSP方案选择是评估来自同一项目的不同方案。其次，每个项目使用不同的资源，产生不同的产出，而后者使用同一套可用但有限的资源，关注项目管理所涉及的时间、成本、质量。我们将DEA应用于MRCPSP的尝试是评估多可行解之间的优劣，为决策者提供可靠的参考。

本文主要研究MRCPSP溶液的选择问题。我们采用数据包络分析(DEA)来评估可用的解决方案。本文的贡献主要体现在两个方面。一是深化MRCPSP的应用研究，从相对效率的角度探讨方案选择。第二，拓展了DEA的应用领域，提出的DEA方法可以应用于MRCPSP。此外，它为项目经理客观地评估MRCPSP中一组类似的解决方案提供了一个新的视角和有用的工具。

论文的其余部分组织如下。部分2利用一个虚拟案例对MRCPSP进行了描述，并给出了MRCPSP的解决方案。部分3.介绍了为解决该问题而设计的求解方法DEA，给出并讨论了计算结果。最后，第节给出了结论4．

2.问题描述及其解决方案

假设有一个由20个活动组成的项目，其中包括两个虚拟的活动:“开始”和“终止”。其节点上的活动(AON)网络如图所示1．每个活动可以以两种模式中的一种运行，正常模式和快速模式;这两种模式成本不同，质量也不同。所有活动可分配三种可再生资源，分别为12、13、12。表中列出了项目的参数1．

这是一个典型的MRCPSP。一个项目包括J活动。并且添加了两个虚拟活动:开始活动0和终止活动J+ 1，两者都不需要追索权和处理时间。因此，可以将活动定义为一个集合 ．每个活动举行米替代模式。可再生资源被封装成一个集合 ，以及类型资源的数量可在每个期间使用的，由 ；类似地，有一个集合和它包含的消耗性资源类型资源 ． ，是活动的直接前辈的集合j，意思是活动j不能开始直到每一个活动 完成了。如果一项活动j过程模式米， ， 定义其处理时间，再生资源类型的数量 ，和类型的消耗性资源的数量 ．

最终目标是最小化项目的总工期，称为完工时间。因此，该问题可以描述如下： 受 在方程(1)定义得到最小处理时间的目标函数;式中的约束(2)定义一个活动在一种模式中只处理一次;方程(3.)限定活动之间的时间限制;方程(4)保持每个时期可使用的再生资源数量小于再生资源总量;与方程(5)确保所有使用的不可更新资源不能超过不可更新资源的总数。 在这些约束中，分别表示活动的最早时间窗口和最近时间窗口。表格2列出模型中使用的所有参数。

许多学者对MRCPSP提出了新的解决方案，如Van Peteghem和Vanhoucke [35]、王和方[36， Ballestin等人[37]，刘等人[38， Gutjahr [13]．本文作者采用了Liu等人开发的遗传算法来实现最终目标。该算法由JAVA编写，并运行在双cpu (Pentium 2.7 GHZ)和2.0 GB RAM的PC上。从1000天内提供非主导方案的结果中选出32个方案，如表所示3.．

数字2证明了项目工期的增加可以提高质量，但前者的边际效用正在减少。项目成本，如图所示3.，与持续时间呈非线性关系:快速的工作模式可以显著增加成本，但延长持续时间很难反过来降低成本。数字4进一步解释Figure的结果3.：由于持续时间缩短，不断增长的成本导致质量降低，而不是更高。

这些解决方案将处理时间放在首位，没有任何偏好建议，让决策者难以选择最合适的方案。因此，我们采用数据包络分析（DEA）来进一步评估这些解决方案。

3.DEA模型的结果与讨论

３．１．结果

在我们的DEA模型中，处理时间是一个反向输出。越小越好。所以为了简单起见，我们把加工时间和成本一起作为输入，把质量作为输出。考虑到传统的DEA模型，如CCR和BCC，无法对有效单元进行排序，从而选择最佳单元，我们使用超效率DEA模型来完成这些工作。表格4比较32种方案的4种效率，包括CCR、BCC、CRS超效率和VRS超效率。

3.2. 讨论

表格4表明CCR模型能产生13个有效单元;32种方法中效率最高的为1，最低的为0.8972。而BCC模型得到22个有效单元;最高为1，最低为0.9908。这些结果表明，虽然BCC和CCR的最低效率接近，但BCC在决定效率方面的能力较CCR弱。在超效率CRS模型中，决策单元(DMU) 28的结果最高，为1.0015，最低与CCR相似;VRS模型中，决策单元7的结果最高，为1.0057，最低与BCC相同。CRS的最大值和最小值均低于VRS。

值得注意的是，四个模型的最大值和最小值非常接近，这意味着从32个选项中找到最好的是一项艰巨的任务。但通过比较这四列，我们可以注意到，当传统模型的结果是低效的时，它等于相应的超高效模型的结果；否则，它比相应的超高效模型要小。这表明超高效模型可用于进一步对高效单元进行排序并找到最佳单元。此外，需要注意的是，DMU 28在VRS超效率模型中没有解决方案，这是因为我们采用了一种以投入为导向的超效率模型，DMU 28的产值（即工程质量值）是所有DMU中最大的。传统模型可以帮助决策者找到效率最低的DMU，但由于上限的限制，往往会提供具有相同效率的多效率DMU。超效率模型消除了这一限制，并提供了具有不同值的有效DMU；因此，最好的一个很容易被发现。在我们的研究中，CRS选择DMU 28为最佳，而VRS选择DMU 7。

超效率模型能有效、快速地找到MRCPSP的最佳解决方案。将超效率DEA模型应用于MRCPSP是一种可行的、较好的方法。

MRCPSP出现在许多现实世界的应用中，如建筑工程、地铁线路选择、医疗诊断、供应商定位、货物运输和软件开发。许多真正的mrcpsp面临的一个非常普遍的困难是如何以主观的方式评估每个解决方案。本文提出的DEA方法应该是一个很好的选择。

4.结论

由于项目调度通常针对多个目标，因此多模式资源约束的项目调度问题的解可以是多个的。如何根据客观原则选择合适的方案已成为实践中的一个问题。我们对一个典型的MRCPSP采用数据包络分析，并有效地提出了一系列客观的基准，可以帮助评估MRCPSP的解决方案，并确定一个合适的方案。我们的方法为决策者在选择合适的MRCPSP解决方案时提供了一个创新的视角和有效的方法。

数据可用性

用于支持这项研究结果的数据包括在文章中。

利益冲突

作者没有需要声明的利益冲突。

致谢

徐州医科大学优秀人才科研启动基金(no . 53591420);博士后科研基金资助项目(53470321);江苏省高校重点学科建设。

工具书类

1. S.E.Elmaghraby，活动网络:基于网络模型的项目计划和控制1977年，美国纽约，威利。
2. P.Brucker、A.Drexl、R.Möhring、K.Neumann和E.Pesch，“资源受限项目调度：符号、分类、模型和方法，”欧洲运筹学研究杂志，第112卷，第112期。第1页3-41页，1999。视图:出版商网站|谷歌学者
3. R. Kolisch和A. Drexl，“非抢占式多模式资源约束项目调度的局部搜索”，国际教育协会事务，第29卷，第2期11，第987-999页，1997。视图:出版商网站|谷歌学者
4. A.Schnell和R.F.Hartl，“关于具有广义优先关系的多模式资源受限项目调度问题的有效建模和解决方案，”或频谱，第38卷，第2期，第283-303页，2016年。视图:出版商网站|谷歌学者
5. M. H. Sebt, M. R. Afshar，和Y. Alipouri，“遗传算法和完全信息粒子群杂交求解多模式资源约束项目调度问题”，工程优化，第49卷，第49期。3, pp. 513-530, 2017。视图:出版商网站|谷歌学者
6. 刘灿灿，“基于列生成的多模式资源约束项目调度算法”，计算机与工业工程，第125卷，第258-278页，2018。视图:出版商网站|谷歌学者
7. “大规模多模式资源约束项目调度问题的混合优化方法”，工程管理学报，第32卷，第2期6、2016。视图:出版商网站|谷歌学者
8. R. Zamani，“用于调度多模式资源受限项目的基于镜像的有效遗传算法”，计算机与工业工程，第127卷，第914-924页，2019。视图:出版商网站|谷歌学者
9. F.Faghhi Mohammadi，A.Seifi和M.Khalighi Sikaroudi，“具有活动拆分的多模式资源约束项目调度问题的改进建模方法和启发式程序，”RAIRO-Operations研究，第50卷，第1期，第91-118页，2016年。视图:出版商网站|谷歌学者
10. R. nematii - lafmejani, H. Davari-Ardakani，和H. Najafzad，“多模式资源约束项目调度和承包商选择:数学公式和元启发式算法”，应用软计算，第81卷，第22页，2019年。视图:出版商网站|谷歌学者
11. A.Hill，E.Lalla Ruiz，S.Voß和M.Goycoolea，“水路船舶调度问题的多模式资源约束项目调度重新制定，”杂志的调度第22卷第2期2，页173-182,2019。视图:出版商网站|谷歌学者
12. B.O.Odedairo，“多目标资源约束项目调度问题的相关性和适用性：综述文章，”工程、技术与应用科学研究， vol. 1, no. 16, pp. 144-150, 2011。视图:谷歌学者
13. “风险规避下的双目标多模式项目调度”，欧洲运筹学研究杂志第二百四十六卷2, pp. 421-434, 2015。视图:出版商网站|谷歌学者
14. 李文杰，“基于pareto算法的多目标多模式资源约束项目调度问题”，《工程管理学报》，2018年第1期，第1期。计算，第101卷，第1期。6，第547-570页，2019。视图:出版商网站|谷歌学者
15. H. Maghsoudlou, B. af沙尔- nadjafi，和S. T. A. Niaki，“解决多技能多模式资源约束项目调度问题的多目标入侵杂草优化算法”，计算机与化学工程， 2016年，第88卷，第157-169页。视图:出版商网站|谷歌学者
16. M. Naldi, G. Nicosia, A. Pacifici，和U. Pferschy，“项目选择中的利润公平权衡”，社会经济规划科学，第67卷，第133-146页，2019。视图:出版商网站|谷歌学者
17. 刘鹏，朱斌，王鹏，“基于球面模糊集的云南白药研发项目选择问题的多属性决策方法”，国际模糊系统杂志第21卷第2期7, pp. 2168-2191, 2019。视图:出版商网站|谷歌学者
18. A. Charnes, W. W. Cooper和E. Rhodes，《衡量决策单元的效率》，欧洲运筹学研究杂志，第2卷，第6期，第429-444页，1978年。视图:出版商网站|谷歌学者
19. G. Debreu，《资源利用系数》费雪第19卷第2期3、经济计量学会学报，1951年。视图:出版商网站|谷歌学者
20. T.C.Koopmans，“作为活动有效组合的生产分析，”生产与分配的活动分析一九五一年第13卷第33-37页。视图:谷歌学者
21. M. J.法雷尔，《生产效率的衡量》，皇家统计学会杂志。系列(通用)号，第120卷。3，页253-290,1957。视图:出版商网站|谷歌学者
22. R. Mahmoudi, A. Emrouznejad, s.n。Shetab-Boushehri, S. R. Hejazi，“交通系统数据包络分析方法的起源、发展和未来方向”，社会经济规划科学，第69卷，2020年。视图:出版商网站|谷歌学者
23. S.Kohl、J.Schoenfelder、A.Fügener和J.O.Brunner，“数据包络分析（dea）在医疗保健中的应用，重点是医院，”医疗管理科学第22卷第2期2, pp. 245-286, 2019。视图:出版商网站|谷歌学者
24. 杨铁通、王培平和李福林，“基于数据包络分析模型的集中式资源分配和目标设定，”工程数学问题， 2018年第10卷。视图:谷歌学者
25. A. Mardani，“能源和环境经济学中的数据包络分析:最新发展趋势综述”，能量，第11卷，第8期，2018年。视图:出版商网站|谷歌学者
26. 周慧，杨勇，陈勇，“数据包络分析在可持续发展中的应用:起源、发展与未来方向”，《中国科学:信息科学》，2014年第4期。欧洲运筹学研究杂志，第264卷，第1期，第1-16页，2018年。视图:出版商网站|谷歌学者
27. S.Soheilirad、K.Govindan、A.Mardani、E.K.Zavadskas、M.Nilashi和N.Zakuan，“数据包络分析模型在供应链管理中的应用：系统回顾和元分析，”运筹学研究年鉴，第271卷，第2期，第915-969页，2018年。视图:出版商网站|谷歌学者
28. W.D.Cook和L.M.Seiford，“数据包络分析（DEA）——三十年前，”欧洲运筹学研究杂志，第192卷，第2期。1, pp. 1 - 17, 2009。视图:出版商网站|谷歌学者
29. 刘建生，吕丽颖，刘文敏。林b.j. y，“dea应用研究综述”，ω号，第41卷。5，第893-902页，2013。视图:出版商网站|谷歌学者
30. M. Kapelko，“使用数据包络分析衡量特定投入的低效率:来自西班牙和葡萄牙建筑业的证据”中欧运筹学杂志第26卷第2期1, pp. 43-66, 2018。视图:出版商网站|谷歌学者
31. E.Karasakal和P.Aker，“基于数据包络分析的研发项目选择问题多准则排序方法，”ω，第73卷，第79-922017页。视图:出版商网站|谷歌学者
32. M. Toloo, S. Nalchigar，和B. Sohrabi，《在用户主观意见存在的情况下选择最有效的信息系统项目:dea方法》，中欧运筹学杂志第26卷第2期4, pp. 1027-1051, 2018。视图:出版商网站|谷歌学者
33. M.Toloo和M.Mirbolouki，“使用数据包络分析的新项目选择方法，”计算机与工业工程，第138卷，2019年。视图:出版商网站|谷歌学者
34. “基于区间数据的六西格玛项目选择:一般权重dea模型，”Kybernetes，第47卷，第47期。7, pp. 1307-1324, 2018。视图:出版商网站|谷歌学者
35. V. Van Peteghem和M. Vanhoucke，“利用资源稀缺特性解决多模式资源约束项目调度问题”，杂志的启发式，第十七卷，第二期6，第705-728页，2011。视图:出版商网站|谷歌学者
36. L.Wang和C.Fang，“多模式资源约束项目调度问题的分布算法的有效估计，”计算机与运筹学第39卷第3期2, pp. 449 - 460,2012。视图:出版商网站|谷歌学者
37. F. Ballestín, A. Barrios和V. Valls，“寻找最佳模式有助于解决mrcpsp/max，”国际生产研究杂志第51卷第1期3, pp. 813-827, 2013。视图:出版商网站|谷歌学者
38. 刘世贤，陈东，王玉峰，“基于模因算法的多模式资源约束项目调度问题”，系统工程与电子杂志，第25卷，第2期4, pp. 609-617, 2014。视图:出版商网站|谷歌学者

版权

版权所有©2020张松。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。