基于列生成的云平台资源约束项目调度研究.pdf

2023 年第 8 期16计算机应用信息技术与信息化基于列生成的云平台资源约束项目调度研究黄志彬1 许燕青1HUANG Zhibin XU Yanqing 摘要 随着云计算技术的不断发展，越来越多的实验室以及办公环境都采用云平台来获取计算资源。但是，在对云平台相关技术的研究过程中，发现对于云平台资源约束项目的调度问题一直都是一个比较大的挑战。主要原因就是，对资源约束项目进行调度需要考虑资源利用率以及调度的时间成本。根据问题建立了资源约束项目资源库调度模型和一种基于列生成算法的云平台资源约束项目算法。通过与拉格朗日技术、数字优化技术及自适应遗传算法等进行实验对比。结果表明，该方法在问题的解决上是具有明显优势的，也验证了该方法的有效性。关键词 云计算技术；资源约束项目；资源利用率；时间成本；列生成算法doi：10.3969/j.issn.1672-9528.2023.08.0041.闽南理工学院 福建泉州 362700 基金项目 福建省教育厅中青年教师教育科研项目(JAT200748)0 引言目前，在新基建中最为关键的技术就是云计算，它在数字化经济中占据着非常大的作用。而随着云服务器池的不断扩张，需要的处理的数据资源更加庞大。在这种大规模项目的运作中，如何实现以最优的方法去完成相关资源的处理，将成为项目管理人员重点解决的问题。在云平台项目的运作过程中，越来越多的科研工作者正在对 RCPSP 进行广泛的研究，也出现了各种优化技术。目前，解决 RCPSP 的方法主要有两种，第一种是致力于取得最优解的精确算法1，另一种就是启发式算法。在求解 RCPSP 常用的启发式方法中有模拟退火、禁忌搜索和遗传算法2等。启发式算法被认为是在性能、可扩展性和可实现性等方面的最佳方法，也是目前学者们普遍在研究的方法。Singh 和 Ernst(2011)正是在 Barahona 和 Anbil(2000)的理论基础上提出了基于拉格朗日松弛(LR)的启发式算法。在通过实例的验证可以得到 LR 与 CPLEX 相比性能更好。但是，在验证的过程中也可以看出，LR 算法在遇到更大的问题时，它需要处理的时间会更长。CG 算法最早就是被用来解决大规模线性规划问题的。它将问题转化为具有某种特殊结构的又有现成方法求解的问题，并且将问题简化为规模较小的子问题。目前，CG已经被更多人应用在解决资源调度的问题上。如 A column generation approach for resource-constrained project scheduling with fl exible resource constraints3（Hodosi G,Van Woensel T,Boender C G E 2011 年），他们提出了一个基于列生成的方法来解决具有灵活资源限制的 RCPSP 问题4，实验结果表明该方法可以在较短的时间内得到高质量的解决方案。A hybrid branch-and-price algorithm for the resource-constrained project scheduling problem5（Della Croce F,Salassa F.2012），这篇文章提出了一种基于混合启发式算法和列生成技术的求解 RCPSP 问题的分支定价算法6。实验结果表明该算法能够在有限的时间内得到高质量的解。A branch price and cut algorithm for the resource constrained project scheduling problem with minimum and maximum time lags7（Alcaraz J,Delorme X,Luttgens D.2010），这篇文章利用分支定界方法和列生成技术构建一个解决具有最小和最大时间滞后的RCPSP 问题的分支定价算法8。本文研究的 CG 算法，是在上界选择线程模式 leader-follower 进行改进。改进后的 CG算法可以提高计算的效率9。1 问题描述在云平台资源调度中，有若干个项目需要对一定数量的处理器进行调度。每个项目都有一个固定的开始时间和结束时间，需要在规定的时间范围内完成。同时，每个项目有不同的任务数量和处理时间10。因此，需要分配适当的处理器数量以保证在规定时间内完成。定义集合：m 个服务器集合为 M1,Mm；每个服务器都有 Ni个作业集，并且是在规定时间内完成的有限集 Ji；作业任务索引及集合为 j Ji；在作业任务时刻表中正在处理或已开始的集合 St。已知参数：服务器作业的释放时间 tj；每个作业完成需要的时间 hj；作业任务到期时间 ej；完成作业的重要性权重 2023 年第 8 期17计算机应用信息技术与信息化值 wj；作业任务时刻表；作业任务开始时间 sj()，sj()tj；作业任务完成的时间 Cj=sj()+hj；完成单个作业所需要的资源数量 Mj；最大可用资源数量 Mmax；作业任务在时刻表中的延迟期 Tj()。条件假设：（1）不考虑两个作业之间的跳转时间。（2）每个服务器只能完成自己所设定的作业任务。（3）每个服务器一次有且只能完成一个作业任务。（4）每个作业任务必须在上一个作业任务的释放时间之后，才可以进行下一个作业任务。（5）同一个服务器内的作业任务之间可以有任意优先级关系，但是，必须遵循优先级关系执行任务。在调度程序中，在时间 t 时的所有作业集合 St。所以：（1）在作业时刻表中，所有作业任务使用的资源数量不可以超过设定的最大可用资源数量。所以：,0tjmaxj SMMt （2）最终，通过问题的描述可以获得一个资源可行的调度处理机制，这个机制可以让所有作业任务之间的 TWT 最小化。所以，可以定义为：（3）还可以表示为 NP-hard：1,jjjje tprecw T。2 一个整数线性调度程序在完成问题的描述之后，接下来需要将问题转化成整数线性调度。定义集合：所有作业任务集合1miiJ=J=；作业任务索引及集合为ijJ。已 知 参 数：在 t 时 间 完 成 作 业 任 务 需 要 的 成 本,0jtjjcw max td=；完成作业的重要性权重值 Zj；作业任务结束的时间范围：T。决策变量：zjt为 0-1 变量，当作业任务 j 在 t 时间内完成时为 1，否则为 0。将问题最小化 TWT 之后，得到的目标函数为：(),10jtjtj tj J tZminczz=（4）在得到目标函数（4）之后，需要对目标函数进行条件约束，以保证调度程度的正确执行。约束如下所示：约束（5）表示所有的服务器一次只能处理一个作业任务：(),1,jij t hjtj Jzzi t+（5）约束（6）表示在发布作业任务之前，任何作业都无法自行开始：0,0,1jtjjzjJ tth=+（6）约束（7）表示作业任务完成之后，需要将作业任务的状态转为完成：,1,jtj tzzjJt （7）约束（8）表示作业任务需要在结束的时间范围内完成工作：ZjT=1,（8）约束（9）表示如果有更高级别的优先关系，需要先满足：,kktj t hzzjkt （9）约束（10）表示所有作业任务在同一时刻内消耗的资源数量不能够超出设定的最大资源数量：(),jjj t hjtmaxj JMzzMt+（10）3 列生成算法求解模型在这之前有学者利用拉格朗日松弛这种启发式算法来解决此类问题。但是，通过实验证明这种方法存在收敛缓慢，不适合去解决大问题。所以，寻找一种更加高效的方法来解决这类问题就显得尤为重要。而通过提出的列生成算法可以解决求解空间过大等问题，从而提高了求解效率。本文提出的列生成算法主要是由主问题（MP）和子问题（SPs）组成的。MP 致力于通过选择最优的列，从而获得全局可行的解。而 SPs 作为所有服务器的调度计划，通过自身的解决方案来形成 MP 的列。但是，在求解的过程中，会发现 MP 的解空间可以非常大。所以，将要介绍一种受限的MP（RMP），RMP 中包含了更小的列子集以及一种更新解决方案的机制，并且能够降低 MP 的复杂性。当然，不同的MP 解决方案也意味着不同的作业任务安排。3.1 主问题模型主问题的最终目的是能够选择到最佳列，这就要求调度程序严格遵循资源约束（10）的规定，并且让 TWT 最小化。定义参数：列为索引 c,每列 c 为 Si的一个解;第 i 个服务器的 c 列的值为 Vic；在 t 时刻 c 列第 i 个服务器的资源量为ticQ；迭代 k 的 RMP 表示为 RMPk。决策变量：xic为 0-1 的变量，当在第 i 个服务器中的第 c列被选中时为 1，否则为 0。(),10,iicjtjtj tj J tVczzi=（11）(),jiticjj t hjtj JQMzzi t+=（12）目标函数（13）表示让所选择到的列总值最小化：icicicVminV x=（13）为了让目标函数（13）所选列的总值最小化，需要对目标函数进行条件约束。约束如下所示：约束（14）表示服务器在作业执行的过程中，只能选择一列并为 1：1,iccxi=（14）从约束（10）中可以知道，已经设定了最大资源数量。因此，所有的资源约束都应该小于或等于最大量，得到约束（15）：,ticicmaxicQ xMt （15）从决策变量xic中，可以获得基础约束（16），在RMP中，还要以对基础约束（16）进一步定义为约束（17）：0,1,icxi c （16）,1,jtj tzzjJt 2023 年第 8 期18计算机应用信息技术与信息化01,icxi c （17）所以，从 MP 中获得的最优解在整个调度过程中，对于所有的服务器都具有一定的可行性。3.2 子问题模型如果调度程度没有遵循资源约束（15）设定的条件，代价就是会让 RMP 对其进行双倍惩罚并传递给 SPs。假设 t为违反规则的处罚。则问题就变成：（18）s.t.约束（14）约束（17）由于 Mmax是一个固定的常量，SPi的目标函数可被更新如下：（19）将 Vic和ticQ代入到公式中，化简后：（20）子问题模型的意义在为当前主问题的最优解下，利用公式求解每个 SP，再调用 CPLEX 进行求解。3.3 下界在上面的算法中已经获得目标函数的表达形式。但是，目标函数的复杂程度导致求解过程过于困难。为了让 RMP计算可以获得更加理想的下界（LB），通过对下界函数的优化，来逐步优化目标函数。改进迭代算法，假定初始模型为等概率的均匀分布，用第 K 次迭代的模型来估算信息，在迭代 K 中，L(K)需要小于或等于 VRMP。这里需要做一些限定，如果它们相等，算法也会强制退出。并且 SPs 也会停止向解决方案池中添加解决列。将第 K 次迭代的下界定义为：（21）3.4 上界由于所有的服务器约束一次只能处理一个作业任务，为了提高性能，增强 CPU 调整缓存相似性，以及消除动态内存分配和作业任务之间的数据交换。因此，在上界中引入leader-follower 机制。当有一个作业任务事件产生时，Leader线程会设定一个 Leader，其他作业任务加入 Follower 线程中等待。为了实现更好的 UB，改进启发式算法，从而得到全局可行解。下面提出三种舍入启发式方法来选择 RMP 中的列：第一种：当 RMP 中 xic=1 时，只选择最开始的列。第二种：在最开始的列中选择所有具有 xic0.5 的决策变量。第三种：应用一种随机策略，其中每个列在最开始值中被选择在 RMP 的最优解中，再以概率等于 xic的值求解。在前面的章节中，设定了服务器作业资源数量的约束（10），它是所有服务器之间能够合理有效处理作业任务的重要因素。为了让服务器能够更好地利用资源，就需要对其他服务的调度任务进行修复，从而来制定一个全局可行性的调度。因此，将约束（10）更新为：(),jjj t hjtmaxjMzZMt+（22）通过对约束（22）的求解，可以让 SPs 获得全局可行性解的可能。本文针对某些服务器使用上面的三种求解方式来获得列，并且，可以为其他服务器获得一个调度。这个时候，新获得的列就可以添加到解决方案池中，以此来达到改进 UB。4 实验结果分析4.1 实验案例规则本文的实验数据是根据云平台的实际问题出发，采用随机生成案例的方式。为了应对在不同教学场景下，对于服务器数量的使用情况等，设计 500 个带有 3 到 12 个服务器的随机问题实例，每个实例平均有 10 个作业任务，每个系列有100 个实例。参考 Kolisch 等提出的规则生成项目网络，为了让后续的算法对比结果比较有说服力，还需要对所有序列的随机产生的实例设定公共属性，如表 1 所示。表 1 实验序列公共属性表服务器数量I/个最大可用资源数量Mmax/个延迟期T/次3810041010051312061512071815082015092315010251804.2 验证算法性能方案通过对改进的 CG、ILP、LR 和 GA 等算法的求解，从而来验证 CG 算法的有效性。CG：为了加快解决时间，让其能够与 LR 进行公平比较，需要让 SPs 在最优的 0.2%终止。终止条件设置为 3600 s 的CPU 时间，或绝对间隙限制的 0.1%，以先到者为准。ILP：终止条件设置为 3600 s 的 CPU 时间，或绝对间隙限制的 0.1%，以先到者为准。LR：SPs 也在最优的 0.2%终止。如果，在连续迭代中得到相同的解。但是，最优性差距仍然不够小的时候，update=0.5。终止条件设置为 3600 s 的 CPU 时间，或绝对间隙限制的 0.1%，以先到者为准。GA：算法的目标是最小化 TWT，而不是最小化解决问题的时间。种群大小设置为 100，算法迭代 10 000 次后终止。4.3 分析实验结果首先，在小规模数据问题上进行算法性能的比较。为了更加客观地反映出算法之间的性能差别，在比较的过程中针对的是相对性能，利用两个算法之间的最佳性能差与最好的相除。相对性能比（d）定义为：2023 年第 8 期19计算机应用信息技术与信息化()()ABTWT ATWT B100%max LB,LBd=（23）在对 ILP 进行简单实验发现，在 6 个以上的 CPU 后，所有的实例都没有办法在规定的时间内得到一个可行的解。在分析 36 个 CPU 之后发现，随着 CPU 数量的不断增多，ILP获得的可行解越来越少了，最优差距小于 10%的就更少了。因此，ILP 找到了比 GA、LR 和 CG 更好的解决方案，就不再对ILP进行算法之间的对比工作。ILP实验结果如图1所示。图 1 ILP 实验结果图CG 算法的差异一直都是小于 GA 和 LR 方法的。这证明了，在36个CPU的情况下，CG比LR和GA有着更好的性能，并且，随着 CPU 数量的上涨，RD 值也有增加的趋势。由于 ILP 对于 6 个以上 CPU 数量的情况下，无法找到可行的解。因此，在针对大规模问题的情况下，只做 CG 和 LR和 GA 算法之间的对比。从图 2 中可以看出，CG 算法总是能够找到比 GA 更好的解决方案。并且，随着 CPU 数量的不断增加，CG 算法的优势就变得更加明显了。CG 与 GA 的对比结果如图 2 所示。图 2 CG 与 GA 的对比图在与 LR 算法的性能比较上，主要是针对在 LB 和 UB 上的比较。对于 LB 和 UB，在 d 的定义与公式（23）一样。在计算 LB 时，如果 d 是正比的话，表示 CG 算法更好。因为，它的 LB 更大。反之，在计算 UB 时，如果 d 是负比的话，表示 CG 算法更好。因此，它的 UB 更小。从图 4 中可以看出，CG 算法确实比 LR 算法来得更好。因为，它可以获得更好的LBs 和 UBs。从而，表明 CG 算法比 LR 算法更适合解决此类问题。LB、UB 的性能比图如图 3 所示。图 3 LB、UB 的性能比图5 结语针对云平台中RCPSP问题，提出一个整数线性数学模型，将问题描述分解成主问题和子问题。在对相关文献进行研究的基础上，提出一种基于 CG 的算法来解决这类问题。为了获得更好的 UB，本文还引入了 Leader-Follower 机制。根据实验结果可知，对于小规模问题，ILP 是这几个算法当中最好的。但是，CG算法也比LR和GA更好。对于大规模的问题，CG 算法总能找到比 GA 更好的解决方案，还可以得到比 LR更好的LB和UB解。通过与ILP、LR和GA算法的实验对比，提出的 CG 算法在一些方面存在一定的优势。参考文献：1 徐华,于勇.一种实用的启发式资源平衡优化算法的改进J.哈尔滨商业大学学报(自然科学版),2004(4):459-461+471.2 乔晓辉.飞机除冰地面运行博弈研究 D.天津：中国民航大学,2011.3 HODOSI G,VAN WOENSEL T,BOENDER C G E.A column generation approach for resource-constrained project scheduling with fl exible resource constraintsJ.Omega,2011,39(4):399-409.4 刘林可.建设工程项目的计划管理研究 D.成都：西南交通大学,2015.5 DELLA C,SALASSA F.A hybrid branch and price algorithm for the resource-constrained project scheduling problemJ.INFORMS journal on computing,2012,24(1):64-76.6 何涛.基于改进最大熵算法的煤矿安全监测系统设计 J.计算机仿真,2012,29(9):132-135.7ALCARAZ J,DELORME X,LUTTGENS D.A branch price and cut algorithm for the resource-constrained project scheduling problem with minimum and maximum time lagsJ.Journal of scheduling,2010,13(5):575-588.8 赵轩.求解 RCPSP 问题的迭代局部搜索算法研究 J.现代计算机（专业版）,2016(8):3-9.9 何小丽.考虑时间转换约束的净现值最大项目进度研究D.郑州：郑州大学,2012.10 黄志彬.基于虚拟化技术的民办高校计算机实验室管理平台的设计与实现 D.泉州：华侨大学,2020.【作者简介】黄志彬(1988)，男，福建南安人，硕士,实验师，研究方向：云计算、VR、数字媒体技术。许燕青(1982)，女，福建石狮人，硕士,高级实验师，研究方向：C+、网页设计、数字媒体技术。（收稿日期：2023-03-10 修回日期：2023-04-28）