集装箱调度技术综述与评价-沙特国王大学学报

制作和主办：Elsevier沙特国王大学学报集装箱调度技术综述与评价Imtiaz Ahmad，Mohammad Gh.Al-FailakawiAl-Shahan，Asayel Al-Muhahan，Al-Shahfa Alsalman科威特大学石油工程学院计算机工程系Box 5969，safat，13060，Kuwait阿提奇莱因福奥文章历史记录：收到2020年2021年2月4日修订2021年3月5日接受2021年3月11日网上发售保留字：集装箱技术优化技术调度算法资源管理和绩效评价A B S T R A C T容器由于其灵活的部署，可移植性和可扩展性，特别是在微服务，智能车辆，物联网和雾/边缘计算中，已成为提供云服务的最有前途的轻量级虚拟化技术。由于工作负载和云资源的多样性，调度器的组件在云容器服务中扮演着重要和至关重要的角色，以优化性能并降低成本。尽管容器在云计算中具有巨大的吸引力，但还没有涵盖容器调度技术的全面调查。在这个及时的调查中，我们调查了最先进的集装箱调度技术的景观，旨在激发更多的研究工作在这个活跃的研究领域。该调查的结构是围绕分类调度技术分为四类的基础上，采用的优化算法，即数学建模，算法，元算法和机器学习生成的时间表。然后，对于每一类调度算法，我们分析和确定的主要优点和缺陷，以及基于性能指标的可用技术的关键挑战。最后，本文强调了未来丰富的研究机会，以充分发挥应急容器技术的潜力。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。内容1.导言. 39352.调度分类和性能指标39362.1.调度分类39362.2.性能指标39363.集装箱调度技术3.1.数学建模技术39373.2.启发式技术39383.3.元启发式技术39393.3.1.基于ACO的技术39393.3.2.基于GA的技术39413.3.3.基于PSO的技术39413.3.4.其他元启发式技术39413.4.机器学习39424.挑战和未来研究方向39425.结论3944*通讯作者。电子邮件地址：Imtiaz. ku.edu.kw（I.Ahmad），alfailakawi. ku.edu.kw（M.Gh.AlFailakawi），asayel. grad.ku.edu.kw（A.Al-Mujah），latifah. alsalman@grad.ku.edu.kw（L.Alsalman）。沙特国王大学负责同行审查https://doi.org/10.1016/j.jksuci.2021.03.0021319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comI. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3935竞争利益声明确认3945参考文献39451. 介绍云计算已成为近年来最流行的技术之一，通过互联网为经济、社会和个人提供按需计算服务（Varghese和Buyya，2018）。随着物联网（IoT）设备、机器学习驱动的应用程序、流媒体音频/视频服务和云存储等各种复杂的云工作负载的增长，对各种云服务的需求急剧增加。此外 ， 由 于 微 服 务 的 日 益 普 及 ， 预 计 云 服 务 的 增 长 将 进 一 步 扩大（Jamshidi等人，2018年）、自动驾驶汽车（Wang和Bao，2019年）和智能基础设施（Jaiswal等人，2018年）。虚拟化技术被认为是云计算的支柱，这种技术能够通过共享资源（CPU，内存和网络）将应用程序与底层基础设施分离，以隔离的方式运行各种应用程序（Alouane和ElBakkali，2016）。作为一种新兴的虚拟化解决方案，容器近年来越来越受欢迎（Pahl等人，2017年），并正在取代传统的虚拟机（VM），这是由于许多有前途的属性，如共享主机操作系统，快速启动时间，便携性，可扩展性和快速部署（Chae等人， 2019年）。容器使应用程序能够将所有必要的依赖关系（代码、运行时、系统工具和系统库）封装到沙箱中，以便构建独立于平台的运行时环境，从而提高生产力和可移植性（Watada et al.， 2019年）。存在多种容器技术，包括Docker，LXC和Kubernetes等（Bernstein，2014）。此外，一些云服务提供商正在虚拟机上运行容器，以改善容器隔离，增强功能并简化系统管理（Mavridis和Karatza，2019）。 容器技术在开发人员中的普及程度以及部署各种微服务和应用程序（如智能车辆，物联网和雾/边缘计算）的普及程度正在飙升（Cascadchio和Iannucci，2020;Jamshidi 等人，2018; Morabito 等人，2017; Santo 等人，2019;Wang和Bao，2019）。因此，许多云服务提供商已经开始提供基于容器的云服务，以满足其不断增长的需求。示例包括GoogleContainerEngine （ cloud.google.com ） 、 AmazonElasticContainer Service （ zon.com ） 和 Azure Container Service（azure.micorsoft.com）。容器技术正在彻底改变云计算范例（Buyya等人，2018年）。从云服务提供商Docker Swarm（ https://docker.com ） 和 GoogleKubernetes （ https ：//kubernetes. IO）是主要的容器编排平台，用于为基于容器的基础设施提供容器在底层集群上的自动部署、缩放和操作容器集群的典型结构由管理器和工作节点组成工作节点负责运行包含用户提交的工作负载的容器;另一方面，管理器节点负责协调工作节点上的集群和容器部署此外，管理器节点通过持续检查以下各项来维护群集的状态正在输入节点状态。调度器的组件在容器编排中扮演着重要而关键的角色容器调度问题是影响云服务性能和成本的重要因素。调音台通常是管弦乐队的可插入组件。在Docker Swarm和Kuber-netes编排平台中，通常存在三种主要的调度策略用于在计算节点上部署容器。装箱策略通过在负载最大的节点上调度集装箱来使用尽可能多的节点来装载尽可能多的集装箱，该节点仍然有足够的资源来运行给定的集装箱。另一方面，随机策略在任何随机选择的节点上调度容器。稀疏策略将容器调度在负载最小的节点上，以便在集群中均匀分布负载。最近，DockerSwarm中基于类提出了新的调度策略（Cérin et al.，2017年）。关于编 配 平 台 中 的 分 类 和 分 类 的 更 多 细 节 可 以 在 Rodriguez 和 Buyya（2019）的工作中找到。容器在提供云服务中的广泛使用给运行时资源调度领域带来了许多新的挑战。根据底层技术的不同，容器调度可以采用不同的形式。例如，图1示出了集装箱调度的一般化框图。取决于实现细节，来自用户的传入任务（Ti）可以直接调度在物理机（PM）上运行的容器（Cj）上或在物理硬件上运行的虚拟机（VM）上。尽管如此，调度程序的责任是确定这些传入任务的最佳位置，以通过考虑各种性能指标（如利用率、完工时间、功率等）来找到最佳可能的调度。. 等由于工作负载和可用云资源的多样性，容器调度已经成为云上现代应用的成本有效操作的关键部分（Fazio等人，2016年）。研究人员提出了许多先进的调度算法，以实现不同的性能Fig. 1.图1框图。I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3936目标，例如可靠性、响应时间、能耗、成本、负载平衡、可用性和资源利用率等。存在许多讨论VM调度的调查（Arunarani等人，2019; Kumar等人，2019; Adhikari等人， 2019年），而只有有限的调查涉及基于容器的系统中的资源管理（Maenhaut等人，2019年）。尽管集装箱非常受欢迎，但没有涵盖集装箱调度技术的全面调查，以确定改善集装箱调度所需的研究领域。因此，为了推进这一重要且不断发展的研究领域的研究，研究现有集装箱调度技术的现状并了解其优势和局限性至关重要。这项及时的调查突出了现有的集装箱调度技术，重点是研究趋势和差距。首先，我们根据用于生成调度的优化算法的类型对现有调度技术进行分类，并描述适用于云环境的相关性能指标。然后，对于每一类的调度算法，我们分析和报告这些算法的性能指标方面的主要优点和局限性。这项工作的主要目标是使研究人员熟悉集装箱调度的最新趋势。然而，设计一个有效的通用集装箱调度技术是一项具有挑战性的任务，由于各种因素，如动态工作负载和不同的资源需求，等等。基于对最先进的集装箱调度技术的详细分析，我们报告了几个挑战，为未来的工作打开了有趣的研究机会本文其余部分的结构如下。第2节讨论了容器调度的分类和常见的性能指标。调度技术的调查和评估在第3节。挑战和未来的研究方向在第4节中描述。最后，第五部分对本文进行了总结。2. 调度分类和性能指标这项工作总结了2017年1月至2021年1月期间在科学期刊（包括IEEE、ACM、Elsevier、Springer以及其他国际期刊和会议）上完成的工作。我们检索了与集装箱调度相关的不同关键词来收集论文。最后，根据与主题的相关性，选择了55篇论文进行审查。 入选论文中，2021年1篇，2020年10篇，2019年23篇，2018年14篇，2017年7篇。在本节中，我们首先根据用于找到解决方案的优化方法对调查的调度技术进行分类。然后，我们描述了用于评估质量的解决方案的常见性能指标。2.1. 调度分类调查调度技术被发现来自四个不同的类别，具有不同的特点，在解决方案的质量和运行时的性能。大多数研究工作都提出了适合以下四个类别之一的算法：1. 数学建模2. 试探法3. 元语言学4. 机器学习数学建模技术将调度问题建模为一组约束方程，例如编程（ILP）公式，然后使用标准技术找到问题的最佳解决方案（Sierksma和Zwols，2015）。然而，由于其高昂的计算成本，ILP配方只能用于小尺寸的问题。由于集装箱调度问题是一个NP难问题，目前还没有多项式复杂度的算法来求解大型集装箱的最优调度问题。因此，大多数报告的技术都是应用一些算法来找到问题的近似解（Christensen等人，2017年）。启发式算法通常具有低复杂度，并在合理的时间内生成令人满意的调度。元算法是一类受自然界中产生的智能过程和行为启发的流行的基于群体的优化算法（Hussain等人， 2019年）。这种算法的两个元算法被广泛应用于多个学科的优化问题求解。机器学习是一个活跃的研究领域，在许多学科的广泛应用中具有很多成功，并且在用于集装箱调度时非常有前途（Pouyanfar等人，2018年）。机器学习算法之所以成功，是因为有大数据来训练模型。然而，这些算法还没有被充分探索的集装箱调度。与其他调度方法相比，可以从机器学习技术中受益，通过做出智能调度决策来提高解决方案的准确性和有效性2.2. 性能度量为了设计有效的集装箱调度，以往的研究都是利用某种类型的目标来量化性能的实现的解决方案，并评估所提出的方法的效率。所使用的一些众所周知的优化目标包括能源效率、可用性、资源利用率、负载平衡、可扩展性、成本和完工时间/延迟。存在可以用于某些应用环境或具有特定数据中心特征的其他优化目标。读者可以参考最近的调查，以检查这些特定领域的优化目标（Gill和Buyya，2018）。优化目标用于测量由算法生成的解决方案的某些方面在一些论文中，优化目标可以由单个目标组成，而其他目标可以是多个目标，这取决于手头问题所需的一般来说，所考虑的优化问题的成本函数中使用的目标越多因此，不同的权衡通常被设置在适当的位置，以平衡所提出的算法的性能和生成的解决方案的质量以下是集装箱调度问题的成本函数定义中最常见的目标能源效率：能源消耗是指在工作节点上部署容器时消耗的电量。此目标试图找到最小化群集的最大限度地减少功耗可以降低能源和冷却成本，从而降低数据中心的运营成本，从而增加微软和谷歌等大型公司的收入。此外，能源效率也是减少碳足迹和提高可持续性方面的关键指标（Gill和Buyya，2018）。因此，许多调度技术试图通过整合容器部署和/或尽可能使用可再生能源来优化能量使用，以增强所生成的解决方案的能量特性。成本：应用程序执行的总体成本取决于各种服务的成本，如计算、存储和I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3937沟通成本。计算成本是指在集群中的可用核心上运行应用程序所花费的时间应用程序在处理器上花费的时间越多，成本就越高。此外，通信成本是指为提供运行应用程序所需的电信服务而向网络提供商支付的成本节点/集群之间所需通信的增加增加了通信成本。可用性：它是指应用程序对用户可用的时间量。可用性是云计算最重要的方面之一，用户应该随时可以访问应用程序/服务这样的目标必须保证所生成的调度表必须为应用程序提供的各种服务提供某种类型的容错，这需要部署的容器数量的冗余。资源利用率：该指标是指在核心、内存和网络带宽方面利用工作节点上可用资源的效率对于该度量，工作节点资源的利用率越高，节点变得越节能和成本效益越高。负载均衡：它是在计算资源之间均匀分布工作负载的过程，这样当其他计算节点空闲时，没有计算节点过载。此目标还影响响应时间、成本和吞吐量。此度量由于工作负载的动态波动，在使用微服务架构的容器应用程序中尤其重要。可伸缩性：容器的可伸缩性是另一个关键指标，它涉及即使系统需求增加，也能持续提供所需服务的能力，该指标衡量了系统重新配置以增加可用资源或在集群上部署额外容器以适应工作负载变化的能力Makespan/Latency：从开始到结束运行应用程序所需的总时间。一个好的调度程序总是试图减少完工时间。该指标影响吞吐量和/或成本，并且被认为是需要低延迟或具有硬截止日期的实时应用的关键指标。吞吐量：此指标是通过将应用程序的任务总数除以执行任务所需的时间来计算的。吞吐量提供了系统（处理器、内存或网络）性能的总体视图，但不能保证降低延迟和成本。安全性：它是编排通过加密和访问控制机制保护数据和服务免受恶意攻击或软件错误的能力。该指标在在线交易处理、中央金融服务和生产力应用中更有效。对于集装箱，必须特别小心，因为它们会受到严重的安全威胁。网络带宽：它是在网络上一秒钟内传输的比特数该度量可以帮助评估容器间通信时的网络延迟和处理网络拥塞。碳足迹：它是由于特别是通过燃烧化石燃料产生的能源消耗而释放到大气中的二氧化碳（CO2）的量。这一指标对于可持续性方面很重要。因此，减少能源消耗和利用清洁能源以减少碳足迹和化石燃料的使用3. 集装箱调度技术在本节中，我们回顾了过去四年中提出的最新集装箱调度技术，并报告了它们的优势，在适当的情况下，限制和任何独特的特征。 在下面的讨论中，技术的限制是指在问题公式化中缺少优化目标，并且可能影响调度器的性能。3.1. 数学建模技术线性规划（ILP）是一种数学建模技术，它使用一组线性约束来表示线性函数的优化。分支定界法是求解ILP问题的主要方法集装箱调度问题的ILP公式在复杂性上是因此，很多时候，为了及时实现解决方案，通常优先选择化学方法而不是ILP公式。Zhang et al.（2017）提出了第一个用于将容器部署到计算节点的线性规划模型。该模型考虑了不同的优化标准，如能源消耗和网络成本。与Docker Swarm binpack策略相比，结果显示成本降低了大约45%Zhou等人（2018）提出了一个基于ILP的调度框架，用于基于容器的云服务。该公式考虑了任务的截止日期，资源约束，并允许部分任务执行，以最小化功能值。所提出的技术是鲁棒的，但是不解决能量减少或其他优化目标。类似地，Wan et al. （2018）报告了一种ILP公式，以最大限度地降低Docker容器环境中基于微服务的应用程序的部署成本。该方法考虑了网络成本，以分布式方式解决调度问题.然而，这种技术导致计算复杂性增加，并且没有考虑其他重要的优化标准，如能量或响应时间。Kaur等人（2020）提出了一种基于多目标ILP的公式，可最大限度地减少边缘计算系统中物联网应用的碳足迹、干扰和能耗。与Kubernetes调度器找到的解决方案相比，所提出的技术大大减少了能耗Lu et al.（2019）设计了一种高效的离线和在线调度技术，确保基于截止日期的任务以最小的开销延迟完成抢占式任务。结果表明，所提出的方法在满足最后期限，并在减少总的任务中断开销的有效性。Alahmad等人（2019）提出了一种ILP技术，通过满足五个特定约束来最大化可用性，即：平均故障时间（MTTF），平均修复时间（MTTR），亲和性，反亲和性和冗余性。实验结果表明，与三种Docker调度技术相比，该技术实现了较高的应用可用性。同一作者早些时候提出（Alahmad等人，2018年）也是一种启发式方法来提高服务可用性。Rodrigues等人（2019）提出了一种多目标MILP（混合线性规划）方法，通过将容器合并到少数节点来最大限度地减少能耗，并最大限度地提高资源和链路带宽利用率。两个GPU加速的多目标算法也被报道用于大规模场景。表1中给出了本节中描述的基于ILP的技术的总结。没有一种技术是可扩展的，也没有一种技术考虑了所有的优化目标。此外，由于解决这些公式所需的时间随着问题大小的增加而大大增加，因此这些技术仅适用于小尺寸问题I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3938对于大规模问题，启发式是ILP的首选方法，然而，ILP有利于衡量启发式解决方案的质量。3.2. 启发式技术如前所述，已经提出了几种算法来解决集装箱调度问题。大多数这些算法使用装箱技术，或者Docker Swarm和Kubernetes中现有技术的组合来将容器映射到计算节点。算法通常是可扩展的，并且在生成时间表时非常快Wu和Chen（2017）开发了一种可保证可靠性的缓冲层优先级调度器（ABP），以减少Docker Swarm中的网络流量并缩短服务扩展延迟。ABP与Docker Swarm中的默认算法之间的通信显示了启动时间的减少和更快的任务分配。Mao等人（2017）在Docker Swarm中为一组异构节点实现了动态和资源感知放置方案（DRAPS）。该方案基于可用资源和对该节点的需求来选择部署容器的节点其他服务。与Swarm套件的性能比较显示了更有效和平衡的资源使用。然而，网络消费很高。Havet等人（2017）提出了Docker环境的GENPACK容器调度框架。它利用运行时监控和垃圾收集在集群节点上部署容器，Pongsakorn等人（2017年）提出了一种主动容器再平衡技术，以有效利用LXC集群中的资源。在他们的方法中，容器首先被分类为短寿命和长寿命的容器，当达到某个预设的资源阈值利用率时，只有长寿命的容器才被考虑迁移。该迁移策略速度快，但优化目标有限，缺乏真实环境下的适当测试。Dziurzanski和Indrusiak（2018）提出了一种市场价值启发式启发式算法，用于在Docker Swarm中分配容器，目标是最大化从工作负载中获得的总价值。在他们的方案中，容器的执行值随作业的值曲线定义的时间而变化然而，他们的方案不处理内存使用或网络利用率来提高性能。Zhang et al.（2018）提出了一种基于拉伸和压缩技术的集装箱调度算法。与Docker相比，所提出的算法节省了网络带宽，并且需要更少的执行此外，该计划还照顾到在调度期间任务之间的依赖性Liu et al.（2018）提出了一种多目标算法，即Multiopt，它结合了Docker Swarm三种调度策略的优点，spread，binpack和random，使容器调度更高效。此外，Multiopt考虑了五个优化标准，以生成更好的调度，包括CPU利用率，内存使用率，网络延迟，容器和节点之间的关联以及容器集群。与Docker Swarm策略的比较显示了优越的性能，但是该方案不具有容错性。Song等人（2018）提出了一种基于拓扑的GPU调度算法，称为Gaia for Kubernetes。为了提高资源利用率和计算效率，作者利用在腾讯生产环境中的实验结果表明，资源利用率提高了10%，表1介绍集装箱调度数学方法的论文摘要参考容器技术Docker目标限制优势可用性能源U负载平衡利用扩展性成本U网络U完工时间- 第一个ILP配方- 多目标- 处理最后期限- 允许部分执行- 基于微服务的应用程序- 降低部署成本- 有效的能源- 物联网边缘计算- 考虑最后期限- 优先任务- 正式可用性- 多目标- 坚固耐用Zhang等人（2017年）- 同类资源Zhou等人（2018年）- 不考虑能源–UUDockerWan et al.（2018年）- 计算复杂度- 不考虑能源不使用清洁能源UUUKubernetesKaur等人（2020年）UUUU–Lu等人（2019）- 很少的优化标准- 未在实际环境中测试- 不考虑能源UUAlahmad等人（2019年）DockerUUUURodrigues等人（2019年）- 计算密集型- 需要GPU–UUUUI. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3939网络开销。然而，Gaia调度器仅适用于GPU集群环境。Lv等人（2019）提出了一种两阶段调度技术，其目标是降低通信成本以及平衡资源利用率。 在第一阶段，一组新到达的容器被放置在服务器上的目标，以提高资源利用率和最小化的通信成本，通过使用通信感知最差拟合递减（CAWFD）算法。 在第二阶段，容器迁移服务器之间，以提高性能，通过使用扫描&搜索算法。在百度数据中心上的实验结果Mendes等人（2019）提出了一种增强的Docker Swarm调度算法，以提高其在雾/边缘计算环境中的能效。由于在这些环境中的资源稀缺，超额认购策略被选择，以提高资源的使用和节省能源消耗。从所获得的结果中，发现所建议的解决方案实现了更好的资源利用，从而降低了能量。然而，由于决策过程的复杂性，调度程序需要更多的时间来生成解决方案，以符合Docker Swarm策略。Chen等人（2019）提出了一种基于流行的Min-Min启发式的容器调度技术，以提高边缘计算系统的能源效率。对Min-Min算法进行了改进实验结果表明，与First-Fit容器放置策略相比，能耗降低了56%Hu等人（2019）提出了一种基于向量装箱的多目标成本函数集装箱调度算法。目标包括资源利用率、负载平衡和网络依赖性.与Kubernetes调度器相比，该技术将依赖关系的容器放在同一个主机上，从而提高了整体性能。Menouer和Darmon（2019）报告了一种调度技术，该技术利用Docker Swarm工具包中的spread和bin packing策略，使用一种多标准算法，称为与Docker Swarm默认策略（如装箱、散布和随机）相比，所提出的技术证明了其增强性能的潜力。Xu等人（2018，2019）提出了一种基于掉电的节能技术。在限电时，在过载情况下，一些可选服务被暂时停用，以减少能耗。作者提出了三种不同的集装箱调度策略的基础上的brownout范例，导致10-40%的节能相比，现有的技术。然而，他们的方法没有考虑到网络拥塞和可再生能源。Kumar等人（2018）提出了一种基于可再生能源的集装箱调度方案。在所提出的技术中，传入的工作负载首先被分为三类，根据他们的优先级，负载和可用性。然后，在使用可再生能源感知主机选择方案选择的节点上调度工作负载此外，设计了一个容器合并方案，以减少计算节点的能量消耗。所提出的方法已经使用谷歌的工作负载跟踪和结果表明，高达15%的节能可以实现作为与First-Fit或随机主机选择方案的兼容性James和Schien（2019）为Kubernetes设计并实施了一种低Fu等人（2019）提出了ProCon，这是一种考虑即时资源利用率以及估计以减少应用程序的响应时间。与Kubernetes相比，整体性能提高了23%。Khan等人（2019）介绍了一套执行容器整合的技术，旨在降低数据中心的能耗并提高性能提出的技术包括一个能源消耗估计模型和一个迁移方法，该方法考虑到性能和成本。最终解决方案的质量和能量特性Hu等人（2020）将并发多资源容器调度问题表述为最小成本流模型。实验结果表明，所提出的技术在资源效率和性能方面都优于最先进的容器调度技术DockerSwarm和Kubernetes然而，在他们的方法中没有考虑容器依赖性Menouer（2020）提出了一种多标准Kubernetes容器调度策略，称为KCSS，其目标是优化最大完工时间和功耗。在KCSS中，作者扩展了他早期的方法（Menouer和Darmon，2019），考虑了六个标准，试图找到一种改进的方法来选择集装箱调度的节点。但是，KCSS没有考虑容错和容器整合，以进一步提高功耗。Rodrigues 等人（2020 ）提出了一种GPU 加速容器调度算法（GPUACS），其中将具有服务质量（QoS）要求的网络和容器的联合分配建模为图嵌入问题。作者在调度决策中考虑了多标准，并使用GPU使调度更快和可扩展。GPUACS能够在不到3.5 s的时间内在拥有20，000多台服务器的数据中心上调度各种大规模请求，即使考虑到网络和时间要求。然而，作者没有考虑调度的负载平衡和容错方面。本节中所有研究的化学品总结见表2。据观察，只有少数几个物流集中在系统可用性的优化启发式通常是快速生成的解决方案，并可以与其他优化技术，以进一步提高生成的时间表的质量集成。3.3. 元启发式技术近年来，元启发式算法已成为解决具有挑战性的优化问题在不同领域的主导地位Meta-启发式算法可以分为进化算法（EA），例如遗传算法（GA）或群智能算法，例如蚁群优化（ACO）、粒子群优化（PSO）和鲸鱼优化（Whale Optimization）等。在本节中，我们根据用于生成解决方案的元启发式的类型对调度技术进行了3.3.1. 基于ACO的技术蚁群优化算法是一种基于蚁群的搜索算法，它利用了蚂蚁在寻找食物时的信息素跟踪行为Kaewkasi和Chuenmuneewong（2017）提出了第一个用于集装箱调度的蚁群优化算法，其目标是通过适当的负载平衡来提高资源利用率。该算法在Docker Swarm上进行了集成和测试。与Swarm贪婪方法相比，结果显示性能提高了15%。然而，该算法只考虑了资源利用率和负载均衡等少数优化目标。Burvall（2019）提出了一种多目标集装箱放置蚁群优化（MOCP-ACO）算法，该算法修改了表2介绍集装箱调度启发式方法的论文摘要参考目标容器优势限制能源可用性利用负载平衡扩展性成本完工时间网络技术吴和陈（2017）UUDocker- 减少延迟- 提高可用性- 同质资源- 不考虑能源Mao等人（2017年）UUUDocker- 性能- -更多的网络消费- 迁移容器Havet等人（2017年）UUUDocker- 基于- 集装箱拼箱- 需要监测- 同质资源Pongsakorn等人（2017年）UULXC- 快速容器迁移- 集装箱分类- 需要多目标- 需要更多测试Dziurzanski和Indrusiak（2018）UUDocker- 考虑价值曲线- 市场启发式- 无内存占用大小- 无网络成本Zhang等人（2018年）UUUUDocker-DAG流模型- 减少网络带宽- 同质资源- 未考虑Liu等人（2018年）UUUUDocker- 多目标模型基于Docker Swarm- 不容错- 不减少Song等人（2018年）UUUKubernetes- 有效- 考虑网络成本- 适用于GPU集群Lv等人（2019）UUUUU百度- 最不合适的装箱- 集装箱迁移- 两阶段配方- 未考虑Mendes等人（2019年）UUDocker- 雾/边缘计算- 复杂的决策过程- 超额认购策略- 计划生成Chen等人（2019年）U–- 使用min-min算法- 边缘计算领域- 优化单个目标- 同质资源Hu等人（2019年）UUUUKubernetes- 使用容器合并- 矢量装箱- 未在真实系统- 时限限制梅努和达蒙（2019）UUDocker- 传播+ 装箱- 多标准决策- 不容错- 未在真实设置Xu等人（2018）和Xu和Buyya（2019）UUUUDocker- 第一次限电计划- 节能- 无网络拥塞- 触发阈值Kumar等人（2018年）UUU–- 整合+迁移- 迁移开销- 使用可再生能源詹姆斯和希恩（2019）UUKubernetes- 考虑碳密度- 选择最环保的数据中心- 需要考虑价格- 迁移需要时间Fu等（2019年）UUUKubernetes- 提高业绩- 预测资源使用情况- 需要监测- 不考虑能源Khan等人（2019年）UUCloudSim- 开发能源模型- 使用容器迁移- 估计运行时间- 可再生能源Hu等人（2020年）UUUUUKubernetes- 最小成本流量模型- 异构资源- 未考虑- 减少梅努埃（2020）UUKubernetes- 六项标准办法- 无集装箱合并- 易于扩展- 无容错Rodrigues等人（2020年）UU- 图嵌入公式- 多标准办法- 无容错- 无负载平衡I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3940I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3941改进了标准的蚁群实现，以使用其他目标，如网络使用率和成本。与Docker Swarm中的分散调度策略相比，MOCP-ACO通过改变工作负载和容器数量（16-1024）在所有测试用例中表现更好Lin等人（2019）提出了一种多目标蚁群算法，可以优化基于微服务的应用程序的资源利用率（CPU和内存）、网络传输和故障率。实验结果与现有的技术，如传播和遗传算法为基础的方法表明，改进的资源平衡和可靠的服务。然而，该算法没有考虑能量消耗。3.3.2. 遗传算法技术遗传算法是受自然进化理论启发的进化搜索技术在进化过程中，个体是根据它们的适应性来选择的，以产生下一代的后代。Guerrero等人（2018）是第一个提出基于NSGA-II的集装箱调度技术的人。NSGA-Ⅱ是一种多目标优化算法。作者在他们的公式中考虑了四个优化目标，包括网络通信开销、负载平衡、故障率和资源利用率。与Kubernetes调度算法相比，该技术在大多数目标上都有40Zhang等人（2019）提出了一种改进的遗传算法，使用非线性能量模型来减少能耗。设计了两种新的变异算子，有效地搜索最优解。然而，所提出的方案考虑了一个单一的目标，即能量优化。Tan等人（2019）提出了一种两级混合算法来降低能耗。与遗传算法类似，遗传规划是一种基于种群的进化计算技术。在该方案中，容器首先被映射到虚拟机（VM），然后VM被分配到物理机（PM）。 实验结果表明，与仅基于启发式的方法（例如，第一拟合、最佳拟合、最佳匹配等）相比，混合方法显著降低了能量消耗。. 等Imdoukh等人（2019）提出了一种基于NSGA-III的多目标遗传算法（MOGAS）。 NSGA-III是NSGA-II的改进版本，可以处理更多的目标函数。作者考虑了五个优化标准，包括功耗，可用性，资源利用率，负载平衡和可扩展性。与基于蚁群算法的调度技术进行比较，验证了该方法的有效性。Tan等人（2020）扩展了他们早期的工作（Tan等人， 2019），通过应用协同进化遗传编程（CCGP）超启发式方法来解决两级容器分配问题。CCGP方法同时为两个级别（容器-VM和VM-PM级别）生成分配规则，以最大限度地减少整体能耗。实验表明，相当大的改善，能源消耗相比，国家的最先进的算法。Dhumal和Janakiram（2020）提出了C-Balancer，这是一种利用容器的运行时指标在集群环境中进行有效放置的框架。在所提出的方案中，容器运行时的指标定期收集，然后发送到基于遗传算法的优化器，以找到最稳定和最佳的容器节点放置。该方法背后的关键思想是通过使用运行时指标跨多个节点迁移来重新平衡容器在Swarm集群上进行的实验表明，C-Balancer在提高资源利用率和吞吐量方面是有效的3.3.3. 基于粒子群算法的技术粒子群优化算法的灵感来自于鸟类的行为，由于其强大的特性，它是一种Li等人（2018）提出了一种PSO算法，可以提高资源利用率和负载平衡。在他们的实现中，作者使用模拟退火算法与粒子群算法，以逃避局部极小值。实验结果表明，与Docker Swarm的传播策略相比，该实现将性能提高了20%Guo和Yao（2018）提出了一种基于PSO的调度算法，该算法利用邻域划分思想来调整PSO算法的参数，以生成更好的质量解决方案。该算法综合考虑了响应时间和负载均衡两个方面来提高系统性能。在所提出的实现中，具有依赖关系的容器被放置在相邻的主机上，以减少通信成本。结果表明，20-25%的提高相比，传播的粒子群算法和传统的粒子群算法。所产生的解决方案的一个缺点是功耗增加Shi等人（2018）使用两阶段多类型粒子群优化（TMPSO）算法解决集装箱合并问题。TMPSO算法结合启发式和贪婪技术，以提高解决方案的质量。实验结果表明，与标准PSO算法和二进制PSO算法相比，该算法在能量消耗上有显著的节省。Adhikari和Srirama（2019）报告了一种加速的多目标粒子群算法，用于为物联网任务调度容器，目标是最大限度地减少能耗和计算时间。此外，该方法还考虑了最小化CO2排放量和计算节点温度Liu等人（2020）提出了一种基于粒子群优化的容器调度算法，用于Kuber- netes的大数据应用，称为K-PSO。为了提高粒子群算法的收敛速度和解的质量，对标准粒子群算法进行了改进，增加了动态惯性权重和学习因子。基于改进的粒子群算法，对Kubernetes原生调度器的谓词调度过程和优先级调度过程进行了改进。实验结果表明，与Kubernetes默认的配置策略相比，资源利用率提高了20%。然而，所提出的方案可以扩展到包括多标准优化目标。Fan等人（2020）提出了一种基于PSO的延迟、可靠性和负载平衡感知调度（LRLBAS）算法，以确定边缘计算范式中基于容器的微服务部署。实验结果与PSO变体的比较证明了LRLBAS算法在边缘计算微服务调度中作者计划在未来的制定中纳入更多的目标3.3.4. 其他元启发式技术Tao等人（2017）提出了一种基于模糊接口系统（FIS）的集装箱调度算法。在他们的实现中，作者在将容器部署到节点时考虑了CPU、内存、I/O和基于网络使用的成本函数等因素与Round-Robin调度算法相比，该算法具有更好的调度效果，但没有考虑能耗优化问题。Salp swarm是一种基于种群的元启发式算法，它模仿了Salpswarm的捕食行为。Ma等人（2019）报告了一种用于冗余容器部署问题的salp群算法的增强版本。提出的技术的目的是优化服务的可用性和响应时间。Docker调度策略和其他元数据的结果显示了该方法的效率。I. 艾哈迈德AlFailakawi，A.Al-Muhman et al.沙特国王大学学报3942Wei-guo et al.（2018）提出了一种混合调度技术，将ACO与PSO结合起来用于Kubernetes调度器，以通过适当的负载平衡来降低资源成本。Vhatkar和Bhole（2019）报告了一种新的多目标资源分配方案