云计算环境下基于匈牙利算法的任务调度

沙特国王大学学报云计算环境下基于对的任务调度算法Sanjaya Kumar Pandaa，b，Shradha Surachita Nandab，Sourav Kumar Bhoica计算机科学与工程系，印度理工学院（ISM），Dhanbad 826004，印度bVeer Surendra Sai University of Technology，Burla 768018，Indiac计算机科学与工程系，Parala Maharaja工程学院，Brahmapur 761003，印度阿提奇莱因福奥文章历史记录：2018年3月31日收到2018年9月21日修订2018年10月2日接受在线发售2018年保留字：云计算任务调度匈牙利算法行机会矩阵列机会矩阵停留时间A B S T R A C T在云计算环境中，调度算法对于寻找任务的可能调度方案具有重要作用。已有文献表明，任务调度问题是NP完全问题因为目标是获得最小的总执行时间。在本文中，我们解决了一组l任务的调度问题，|G|分组为一组m个云，使得总体停留时间最小化。请注意，总停留时间是成对任务之间的时间间隔之和。在此，我们提出了一种基于对的云计算环境下的任务调度算法，它是基于著名的优化算法，称为匈牙利算法。该算法考虑了云和任务数量不等的情况，将任务配对进行调度决策。我们在22个不同的数据集上对该算法进行了仿真，并与现有的先到先服务算法、带租赁时间的匈牙利算法和带逆租赁时间的匈牙利算法进行了比较。性能评估表明，该算法产生更好的停留时间相比，现有的算法。 理论分析表明，该算法k次迭代，p次重复，l次任务时间复杂度为O（kpl2）©2018作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍云计算是通常通过互联网提供各种计算服务，诸如网络、服务器、应用和存储（Buyya等人，2009; Zhang等人，2016; Panda和Jana，2015; Mishra等人，2018年）。这些服务由云服务提供商（CSP）按需提供，并代表客户进行管理。客户仅需要按照每次使用付费（按需付费）或订阅基础（Mashayekhy等人， 2016年）。为了使用云，客户向CSP请求具有一组需求的服务（例如，基础设施即服务（IaaS））此外，客户通常需要虚拟机（VM）实例来在数据中心部署其应用程序，这通过CSP提供*通讯作者。电子邮件地址：sanjayauce@gmail.com（S.K.Panda）。沙特国王大学负责同行审查制作和主办：Elsevier（Haidri等人，2017; Roy等人， 2017年）。因此，客户不采购任何物理基础设施。因此，云计算在企业界得到了更广泛的采用这种采用也是通过以下事实/预测建立的根据Forrester研究（美国市场研究公司）（Cloud Computing Predictions，2018），公共云市场总额将从2017年的1460亿美元增加到2018年的1780亿美元，复合年增长率为22%。据预测，流行的CSP、亚马逊网络服务（AWS）、微软和谷歌将在2018年占据76%的收入，到2020年将收入增加到80%（云计算预测，2018年）。随着基于云的服务的快速增加，云资源管理和调度非常具有挑战性（ Zhang 等 人 ， 2016; Panda 和 Jana ， 2015; Mishra 等 人 ，2018;Mashayekhy等人，2016年）。有效的策略帮助调度器分配云资源（即，CPU周期、存储器、带宽等），以使得客户请求或任务的总执行时间最小化的方式。调度策略首先将客户请求映射到云资源，并且监视先前分配的客户请求（如果有的话）在云资源上的执行。然后根据客户需求和资源监控选择资源。最后，它将客户请求分发到选定的资源。基于https://doi.org/10.1016/j.jksuci.2018.10.0011319-1578/©2018作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comS.K. Panda等人 /沙特国王大学学报-计算机与信息科学34（2022）1434-14451435这些，在云计算环境中已经提出了许多任务调度算法（Panda和Jana，2015; Mishra等人，2018; Mashayekhy等人， 2016; Haidri等人，2017; Roy等人，2017; Panda等人，2017; Pande等人， 2016，2018;Penner等人，2014 a，b; Li等人，2014; Bassa，2012; Li等人，2016;Mondal 等 人 ， 2017; Assarzadegan和 Rasti-Barzoki ， 2016; Liu等人，2015; Gawali和Shinde，2018）。然而，这些算法都没有考虑任务配对，这是需要减少任务的停留时间。请注意，停留时间是成对任务之间的时间间隔。因此，本文的动机是需要开发一个任务调度算法，以有 效 地 处 理 客 户 的 任 务 ， 这 反 过 来 又 将 最 大 限 度 地 减 少 总 的exacrification- tion时间。请注意，最小化的停留时间导致最小化的总执行时间。当没有歧义时，我们可以互换使用停留时间和执行时间我们首先制定一个任务调度问题如下。给定一组l个任务，|G|组和一组m个云，该过程是将所有给定的任务分配给云，使得停留时间最小化。值得一提的是，传统问题和当前问题之间存在重大差异（即，云问题），其陈述如下。 (1)在传统问题中，没有资源的异质性。然而，在目前的问题，资源被认为是异构的。(2)传统问题中的任务大小是单一的，而当前场景中的任务大小是小型和中型的（Sadashiv和Kumar，2011）。(3)在当前的问题中，计算服务被认为是按需的，他们是可扩展的，与传统的问题。作为一个优化问题，我们计划使用匈牙利算法来解决这个问题。因此，我们在这里提出了一种算法，称为基于配对的任务调度（PTS）对上述任务调度问题的解决方案，这是基于匈牙利算法（弗兰克，2005年;库恩，2009年）。然而，匈牙利和所提出的算法之间有一些显着的差异。现将其详细说明如下。(1)该算法考虑了匈牙利算法没有考虑的租赁时间与逆租赁时间之间的最小时间差。(2)所提出的算法考虑了任务的开始和结束时间，而匈牙利算法考虑了任务的执行时间/成本。(3)所提出的算法提供了任务的调度到云，而匈牙利算法之间的任务映射，而不执行任务调度。该算法考虑了内部和外部云服务，以满足客户（或任务）的要求。因此，它适用于联邦云。所提出的算法的特点是，任务的数量是组的数量的倍数。该算法在MATLAB R2014a中进行了广泛的仿真，并使用各种合成数据集进行了测试。将所提出的算法的性能与先来先服务（FCFS）算法（Liu等人，2015年; Gawali和Shinde，2018年）、匈牙利租赁时间算法（HA-LT）（Frank，2005年 ; Kuhn ， 2009 年 ） 和 匈 牙 利 逆 向 租 赁 时 间 算 法 （ HA-CLT ）（Frank，2005年; Kuhn，2009年）。比较结果表明，PTS算法在停留时间方面优于FCFS、HA-LT、HA-CLT算法。本文的贡献可以概括为以下几点。我们开发了一个基于对的云计算环境中的任务调度算法，我们考虑了传输时间，使所提出的算法是现实的。此外，我们还利用租赁期与逆最短时间之间的最短时间来进行分配决策。我们用10个不同的数据集对该算法进行了仿真，并与FCFS，HA-LT，HA-CLT进行了比较，以显示该算法的有效性。本文的其余部分组织如下。在第2节中，我们描述了相关的工作，其适用性。第3节介绍了调度问题。在第4节中，我们提出了一个基于对的任务调度算法来解决第3节中描述的问题。最后给出了一个例子来说明该算法。第五节给出了该算法的仿真结果，并与现有的三种算法进行了比较。最后，在第六中，我们对本文进行了总结，并对本文的局限性进行了讨论.2. 相关工作近年来，已经提出了许多分配模型、资源分配和任务调度算法（Panda和Jana，2015; Mishra等人，2018; Mashayekhy等人，2016;Haidri等人，2017; Roy等人，2017; Panda等人， 2017;Pande等人，2016; Panda等人，2018; Penner等人，2014年a，b; Li例如，2014;Bassa，2012; Li等人，2016; Mondal等人，2017;Assarzadegan和Rasti-Barzoki，2016; Liu等人，2015年; Gawali和Shinde，2018年;Sadashiv和Kumar，2011年; Frank，2005年; Kuhn，2009年;Gil-Rumaja，1998年;Medina-Acosta和Delgado-Penin，2011年;Shah等人，2014; Chithra等人，2015; Sir等人， 2015;Roca-Riu等人，2015;Dong 等 人 ， 2016; Emery 等 人 ， 2016; Ji 等 人 ， 2016;Schedler 和Kuhn，2013; Shi等人，2013; Murthy，2007; Kumar例如，2017;Bhoi等人，2018; Panda等人，2015年）。这些算法主要集中在有效地分配到资源的任务。本节回顾了最近的算法，这些算法具体解决了任务调度问题（特别是云）和/或匈牙利算法，而与域无关。Gil-Gillja（1998）讨论了Hungarian算法的理论元素他们用图的形式而不是矩阵的形式来表示这个定理。然而，他们应用这个定理当且仅当每行和每列都有一个零。Medina-Acosta和Delgado-Penin（2011）通过应用流行的优化算法（称为匈牙利算法）实现了信道相关调度。它们通过求解第三代系统的约束条件来提供最优的资源分配Bassa和Gil-Lafuente（2012）为公司开发了一种为此，他们观察了客户的期望，个人资料，治疗等，并使用匈牙利算法解决了这个问题。Shah等人（2014）已经说明了匈牙利算法的局限性，当作业的数量比处理器的数量大1/4时，就会出现这种局限性。因此，他们提出了一种替代方法来解决这一限制，但这种方法是不可实现的。Penner等人（2014 b）已经修改了匈牙利算法，用于有效地将任务分配给设备，以便实现负载平衡、并置扩展等等。此外，他们还引入了一个新的计算平台，称为瞬态云。在这个云中，通过连接附近的设备形成ad-hoc网络，提供各种服务。重要的是要注意，瞬态云是由网络中存在的设备创建的，并且当这些设备离开网络时消失。Penner等人（2014a）展示了一个关于瞬态云的演示。此演示使用Android应用程序执行然而，上述大部分工作并不被视为任务的最后期限因此，任务的排序可能会导致他们之间的饥饿Li et al.（2014）研究了商品市场，并发布了价格模型在该模型中，资源共享是资源提供者或中介者与资源消费者之间就服务持续时间、服务成本和服务质量在这里，作者使用了匈牙利语●●1436S.K. Panda等人/沙特国王大学学报≤≤ ≤算法来优化资源分配。然而，该模型没有使用大量的资源和作业进行测试。他们只考虑了四种资源和三种工作。Chithra等人（2015）已经引入了用于附近区域的连接的设备到设备通信，并提出了使用匈牙利方法的传输模式分配算法以提高系统的吞吐量。Li等人（2016）改进了匈牙利算法并应用于串并行系统。此外，他们已经评估了所提出的算法在劳动力分配的调度系统。Mondal等人（2017）提出了一种使用匈牙利算法解决不平衡分配问题的方法。在这里，他们考虑了不相等数量的工作和机器。然而，他们在不同的阶段映射了作业和机器。Liu et al.（2015）使用FCFS方法对作业进行排序，以便将其分配给可用资源。在这里，客户可能无法按照他们的要求获得资源。Gawali和Shinde（2018）提出了一种混合启发式算法来执行资源分配和任务调度。他们采用改进的层次分析法进行任务处理，带宽感知的可分割调度和BAR优化进行资源分配。Nathani等人（2012）提出了一种分配算法，其中将租约分配给节点。他们考虑了租赁的开始时间和期限。然而，重新安排租赁是该算法的主要开销。HA-LT（Frank，2005; Kuhn，2009）考虑了任务之间的租赁时间，并应用匈牙利算法来映射任务。另一方面，HA-CLT（Frank，2005; Kuhn，2009）考虑了任务之间的逆向租赁时间，并以与HA-LT相同的方式但是，停留时间非常长。分配问题不仅限于云计算，而且还应用于其他领域，例如患者分类系统（Sir等人，2015），城市配送停车（Roca-Riu等人，2015），航空业（Dong等人 ， 2016 ） ， 渔 业 （ Emery 等 人 ， 2016 ） ， 供 应 链 调 度（Assarzadegan和Rasti-Barzoki，2016），动态交通管理（Ji等人，2016年，还有更多。上述工作大多采用匈牙利算法，但他们没有考虑到以下重要的事情。(1)任务和资源的数量被视为相等，不切实际。(2)任务没有截止日期，它取决于资源的可用性。它导致饥饿的任务。(3)有一个固定数量的云，都安排好了因此，它可能无法处理动态场景。(4)任务的执行时间是预先确定的，没有任何特定的开始和结束时间。因此，在特定时间不可能保留现有工程的比较研究列于表1。 现有的算法中存在一些差距，这些差距是阶段性的。TED如下。1）现有算法在不同阶段映射作业和(2)现有的算法大多通过考虑客户或供应商的感知来进行调度决策。(3)对解决方案进行穷举搜索是昂贵的。（4）大多数现有的工作都是用一组非常小的任务和机器来测试的，以显示算法的有效性。上述差距带来了以下机会。（1）设计有效的任务调度算法，该算法通过从客户和供应商的角度来映射任务和机器。(2)有效的任务调度算法不应该依赖于对解决方案的穷举搜索（3）算法应该用大量的任务和机器进行测试，以显示其有效性。在本文中，我们提出了一个新的任务调度算法，它最大限度地减少了总的执行时间。所提出的算法使用由（Penner等人，2014 a，b; Li等人，2014; Bassa，2012; Li等人，2016; Mondal等人，2017年;Gil-Rinja，1998年;Medina-Acosta和Delgado-Penin，2011年; Shah等人，2014; Chithra等人， 2015年）。然而，它有以下几与这些算法的显著差异。1)所提出的算法考虑了云计算环境中任务和云的不等数量，这在大多数现有算法中没有考虑（例如，（Li等人，2014年; Liu等人，2015; Gawali和Shinde，2018; Frank，2005; Kuhn，2009 ） 。虽 然 已 经 提 出 了 相 当 多 的 算 法 （ 如 Mondal et al.（2017）），但它们在不同的阶段映射了作业和机器。然而，所提出的算法在单个阶段中映射。2)所提出的算法将任务分成两个不同的组，并比较两组任务以找到配对，这是现有算法所不能完成的（Li等人，2014年; Liu等人，2015; Gawali和Shinde，2018; Frank，2005; Kuhn，2009; Nathani等人，2012年）。3)该算法考虑了传输时间的影响，使其更符合实际.然而，在现有算法中不考虑转移时间（Li等人，2014年;Liu等人，2015; Gawali和Shinde，2018;Frank，2005; Kuhn，2009;Nathani等人，2012年）。4)与现有的算法不同，我们考虑了一个新的性能指标，称为停留时间来评估建议和现有的算法。3. 问题陈述考虑一组l个任务T = {T1，T2，T3，. . ，T1}和一组作为服务的分布式基础设施（IaaS）云C = {C1，C2，C3，. . ，Cm}。 任务Ti，1我 L 是中表示形式3-元组ST，D，G>，其中ST表示开始时间，D表示持续时间，G表示组id。注意，结束时间（ET）是开始时间和持续时间之和。数学上，ET=AT+D。我们假设任务的开始时间、持续时间和结束时间是预先确定的。 任务集合T被划分为0= 0。|G|组请注意，每个组中的任务总数需要相等。然而，所有的组彼此不相交。 在任务分配之前，进行任务配对，其中配对任务属于两个不同的组。配对任务（比如，Tx和Ty）可以在云上处理如下。第一任务Tx可以在云中执行，并且下一个任务Ty只能在相同云中开始，在第一任务T x的结束时间（ET）任务Tx和任务Tx与任务Ty之间的传输时间。数学上，ET（T x）+sST（Ty）。 此网络延迟/传输时间为了计算的简单性，假设用户/任务之间的时间间隔为一小时然而，在我们的算法中没有考虑CPU和网络使用的动态性目标是以最小化总体停留时间的方式处理任务。这个问题被限制到以下约束。1)一个任务可以映射到任意数量的云，但它最终会被分配到其中一个可用的云。2)配对任务可以以任何顺序执行，但它们仅限于在同一云中执行。3)任务组的数量是偶数，并且优选地设置为两个。4)任务不能分区、迁移和抢占。在本文中，我们使用Haizea（即，基于租赁管理的开源虚拟机）架构来解决上述问题（Haizea，2018）。4. 该算法4.1. 基于对的任务调度算法基于对的任务调度（PTS）算法是基于一种组合优化算法，称为匈牙利算法（Frank，2005; Kuhn，2009），最初由Harold W.库恩在1955年。PTS是一种分配或调度算法，它以非常适合在云中处理为此，它将任务集分为两个不同的组，即G1到G2。然后分别计算G1到G2的任务之间的租用时间和G2到G1的任务之间的逆租用时间，表1对现有作品的比较研究文章方法环境/问题分配匈牙利算法目的实验平台/框架/规范缺点第50集9.4The Famous（2011）Bassa和Gil-Lafuente信道相关调度一种分类移动环境关系营销动态动态使用使用优化资源管理服务期望3GPP未指定假设信道状态信息完全已知所提出的方法考虑（2012年）满足客户期望仅从客户Penner等人（2014年）Li等人（2014年）瞬态云平台一种新的经济模式任务调度任务调度动态静态使用使用负载平衡利润最大化Android和Wi-FiC++拟议的演示形式的网络使用星型拓扑结构，这是容易发生单点故障该模型在小基于网格资源超市仅规模情况Chithra等人（2015）Li等人（2016）一种传输模式分配算法改进的匈牙利装置-到-装置通信作业调度静态静态使用使用总体系统吞吐量最少总时间MATLAB未指定只有一个继电器评价过程是时间蒙达尔等人（2017年）Liu等人（2015年）算法用匈牙利法实现非平衡矩阵的负载平衡基于整合的作业调度作业调度静态静态/使用不使用负载平衡低空闲CPU周期和CPU未指定轨迹驱动消耗作业和机器在不同的阶段客户可能无法获得Gawali和Shinde（2018）并行作业调度算法一种混合启发式算法任务调度和动态动态不使用使用估计周转时间和响应Cybershake和期望资源任务总数为Nathani等人（2012年）方法基于动态规划的调度算法资源分配资源分配动态不使用时间最大化接受的租赁和系统利用率，并最大限度地减少拒绝的租赁，需要重新部署其他租赁的表观基因组学限28人截止日期租赁总数限制为43。所提出的算法没有实现租赁和租赁延期以安排新租赁S.K. Panda等人/沙特国王大学学报14371438S.K. Panda等人/沙特国王大学学报以整数的形式表示。请注意，任务之间存在传输时间，这是将结果从一个任务发送到另一个任务所必需的。这里，传输时间假设为一小时，这是在同一云中完成一个任务并启动另一个任务所需的最小时间间隔。然后计算租赁时间与逆租赁时间之间的最短时间。接下来，该算法计算行机会矩阵，然后是列机会矩阵。如果两个矩阵相同，则总机会矩阵与列机会矩阵相同。或者，如果覆盖列机会矩阵中所有零的水平线和垂直线的最小数量是任务总数的一半，则总机会矩阵与列机会矩阵相同。否则，该算法在矩阵中找到最小的未覆盖元素，并将其从所有未覆盖元素中减去，并将其添加到被覆盖两次的元素中。此外，重复该过程，直到覆盖所有零的水平线和垂直线的最小数量是任务总数的一半。对于所提出的算法PTS（图1）的伪码，我们使用表2中所示的符号。注意，所提出的算法是（Murthy，2007）中讨论的调度问题的扩展。PTS算法取l个具有ST和D的任务，并计算每个任务的ET（图1的第2行）。然后，它通过调用过程1（FIND-LTU）（第4行）计算租用时间，如图1所示。 二、过程1将任务集分为两个不同的组（过程1的第1行和第2行），并计算两个不同组的任务之间的租用时间（第3行）。如果租用时间小于传输时间，则检查ET是否大于表2符号及其定义。符号定义ET[j]任务jST[j]任务jD[j]任务j的持续时间s传输时间LT[jjLTU[jjCLT[jjCLTU[jjLTU和CLTU之间的最小时间单位ROM行机会矩阵COM列机会矩阵TOM机会总矩阵ST或不。如果是，则从24 h中减去租赁时间（第4否则，它将租赁时间添加为24小时（第7行和第8行）。例如，让我们假设T1的ET是09：45，T6的ST是09：00。T1和T6之间的租赁时间是00：45。由于租用时间小于传送时间（即，01：00），T1的ET大于T6的ST，用24h减去租赁时间，得23：15。让我们考虑另一个例子，其中T2的ET是12：30，T7的ST是13：00。任务之间的租用时间为00：30。这里，租用时间小于传输时间，并且T7的ST大于T2的ET。因此，它将租赁时间与24 h相加，结果为24：30。接下来，通过将小时视为4个单位，将租赁时间转换为整数（第11- 16行）。为此，我们首先将租赁时间的小时和分钟缩放到0到100的范围内（第11例如，30 min相当于30× 1.66 = 50（近似值）1小时等于100。注意Fig. 1. PTS的伪码S.K. Panda等人/沙特国王大学学报1439图二. 查找租用时间的伪代码。图3.第三章。用于查找LTU和CLTU之间的最短时间的伪代码为了计算的简单性，执行小时和分钟的缩放。然后，它通过将小时和分钟的缩放值相加来计算总单位（第14行）。接下来，我们将总单位除以25，将其转换为整数（第15行）。在这里，1小时相当于4个单位。从主算法的第5行调用过程2（即， 图1）。由于该程序与程序1相似，因此此处未明确显示。接下来，它调用过程3（图3）来找到租约时间和逆租约时间之间的最短时间（主算法的第6行）。最少时间背后的合理性是，1440S.K. Panda等人/沙特国王大学学报×相应的列（第8-10行）。注意，结果矩阵被称为列机会矩阵。接下来，它使用最小数量的水平和垂直线覆盖COM矩阵的所有零元素（第9行）。如果线的数量是任务总数的一半，则最终的分配矩阵，称为总机会矩阵，与COM矩阵（线10和线11）相同。否则，所提出的算法找到最小的未覆盖元素，并从所有未覆盖元素中减去该元素，并将该元素添加到被覆盖两次的元素中（第12注意，上述过程（即，第12定理1：PTS算法的时间复杂度为O（kpl ~2）.见图4。 查找行机会矩阵的伪代码。图五. 查找列机会矩阵的伪代码。所提出的算法的主要目标是最小化总的停留时间。过程4从主算法的第7行调用。这个过程找到了每一行的最小值（过程4的第2-7行，图2）。 4），并从相应行的所有元素中减去它（第8-10行）。注意，所得矩阵被称为行机会矩阵。接下来，从主算法的第8行调用过程5。这个过程找到每一列的最小值（过程5的第2-7行，图5）。 5）并从所有元素中减去它，证明：。步骤1到步骤 3需要O（l）时间。步骤4和步骤 5需要O（l2）时间。同样，步骤6到步骤 9需要O（l2）时间。 步骤10和步骤 12需要恒定的时间。步骤13和步骤 15需要O（l）时间。步骤16调用步骤9到步骤 15，比如p次。上述过程针对不同的任务集合进行迭代，比如k次。因此，PTS需要O（kpl2）时间。4.2. 图示让我们考虑存在两组任务，即组1（即，G1）和组2（即，G2），每组由五个不同的任务组成[即，在G1中任务1（T1）到任务5（T5）以及在G2中的T6到T10]。每个任务有三个参数，即ST、D和ET，如表3所示。最初，所提出的算法计算两个不同组的任务之间的租赁时间（即，G1到G2）。例如，T1和T6之间的租赁时间被计算为T1的ET和T6的ST之间的差，其为23：15（即，09：45-09：00）。在这里，我们认为60分钟为100。因此，15分钟相当于25分钟。因此，23：15可以改写为23：25。G1和G2的任务之间的租用时间如表4所示（a）反之亦然（即，我们将其称为表5（a）中的逆租赁时间）逆租赁时间被计算为T6的ET和T1的ST之间的差，其为22：30（即，上午10：00-08：30）。请注意，22：30相当于22：50，将60分钟视为100分钟。我们还通过将一小时转换为4个单位来以整数的形式表示租赁时间和逆租赁时间，分别如表4（b）和5例如，23：25可以重写为93（即，23 4 + 1）。接下来，所提出的算法计算租赁时间和逆租赁时间之间的最短时间（整数），如表6所示。请注意，粗体表示最短时间与相反的租用时间相同。接下来，所提出的算法通过减去最少时间矩阵的每一行中的最小元素来生成行机会矩阵（表7），随后通过减去行机会矩阵的每一列中的最小元素来生成列机会矩阵（表8这里，行机会矩阵与列机会矩阵相同。值得注意的是，每个元素中的最小元素表3(a) 组1中的一组任务（b）组2中的一组任务G1StDETG2StDETT1八点半01时15分九点四十五分T6九点整凌晨一点十点整T2十一点整01时30分十二点半T713点整01时15分14点15分T315点整01时15分十六点十五分T817点整01时15分十八点十五分T418点整01时30分19点半的t9十九点四十五分01时30分二十一点十五分T522点整01时30分二十三点半T1021点半02：15二十三点四十五分S.K. Panda等人/沙特国王大学学报1441表4(a) 租赁时间（b）租赁时间（整数）。T6T7T8的t9T10T6T7T8的t9T10T1二十三点二十五分三点二十五分七点二十五分十点整十一点七十五分T19313294047T220点50分二十四点五十分四点五十分七点二十五分九点整T28298182936T3十六点七十五分二十点七十五分二十四点七十五分三点五十分05时25分T36783991421T413点50分十七点五十分二十一点五十分二十四点二十五分凌晨两点T45470869708T5九点五十分13点50分十七点五十分二十点二十五分22点整T53854708188表5(a)转换租赁时间（b）转换租赁时间（整数）。T6T7T8的t9T10T6T7T8的t9T10T1二十二点五十分十八点二十五分十四点二十五分十一点二十五分八点七十五分T19073574535T2凌晨一点二十点七十五分十六点七十五分十三点七十五分十一点二十五分T20483675545T3五点整二十四点七十五分二十点七十五分十七点七十五分十五点二十五分T32099837161T4八点整三点七十五分二十三点七十五分二十点七十五分十八点二十五分T43215958373T512点整七点七十五分三点七十五分二十四点七十五分二十二点二十五分T54831159989表6最少的时间。表10PTS中的任务分配T6T7T8的t9T10任务订单组时间T19013294035T 1？ T 7G1三点二十五分T20483182936T6？ T 2G2凌晨一点T32083831421T 3？的t9G1三点五十分T43215868308T 4？ T 10G1凌晨两点T53831158188T8？ T 5G2三点七十五分表7行机会矩阵。T6T7T8T9T10T177 00 16 27 22表11PTS中的任务调度序列ST08：30-09：00T6T2表8列机会矩阵。T6T7T8T9T 1015：0016：15-17：0017：00-18：0018：0018：15T5表9总机会矩阵。T6T7T8的t9T10T17700162722T20079142532T30669690007T42407787500T52316006673列机会矩阵的列为零。因此，该矩阵被视为总机会矩阵。或者，如果行机会矩阵的每一列中的最小元素为零，则该矩阵直接被认为是全机会矩阵。总机会矩阵如表9所示，其中任务分配以粗体显示T2007914253209：00-09：45T1T30669690007上午9：45-10：00T42407787500上午10：00-11：00T5231600667311：00-12：3012：30-13：0013：00-14：1514：15-15：00T7T1770016272219：30-19：45T2007914253219：45-21：15的t9T3066969000721：15-21：30T4240778750021：30-22：00T5231600667322：00-23：3023：30-23：45T101442S.K. Panda等人/沙特国王大学学报≈≈表12将任务映射到PTS中的云。云1T1T7T3T9T8T5云2T6T2T4T10任务分配见表10，调度顺序见表11。 总的中途停留时间是03：25+ 01：00 + 03：50 + 02：00 + 03：75 = 13：5013小时30 Min.The任务到云的映射如表12所示。FCFS和HA-LT的任务分配如表13所示，调度顺序如表14所示。两种算法的总停留时间为03：25 + 04：50 + 03：50 + 02：00+ 12：00 = 25：25 25小时15分钟。任务到云的映射如表15所示。S.K. Panda等人/沙特国王大学学报1443≈表13FCFS和HA-LT中的任务分配。表18将任务映射到HA-CLT中的云。任务订单组时间云1T1T7T3T4的t9T10T1 ？T7T2？T8T3？ 的t9G1G1G1三点二十五分四点五十分三点五十分云2T6T2T8T5––T 4？ T 10T6？ T 5G1G2凌晨两点12点整HA-CLT的任务分配如表16所示，调度顺序如表17所示。 总停留时间表14FCFS和HA-LT中的任务调度序列的HA-CLT是10：00 + 01：00 + 05：25 + 03：75 + 03：75 = 23：75 23小时数45分钟显示了任务到云的映射在表18中。从图中可以清楚地看出，所提出的算法在总停留时间方面优于现有的算法FCFS、HA-LT和HA-CLT。5. 仿真结果表15将任务映射到FCFS和HA-LT中的云。云1T1T2T7T8T4T10云2T6T3的t9T5––表16HA-CLT中的任务分配任务订单组时间T 1？的t9G1十点整T6？ T 2G2凌晨一点T 3？ T 10G105时25分T7？ T 4G2三点七十五分T8？ T 5G2三点七十五分表17HA-CLT中的任务调度序列我们使用MATLAB R2014a对所提出的算法进行了评估，该算法运行在以下系统配置上：1）Inteli3处理器，2）4 GB RAM，3）64位操作系统和4）Microsoft Windows 7平台。在这个模拟过程中，我们使用MATLAB生成了22个不同的数据集。我们将这些数据集分别称为数据集1至数据集22。请注意，这些数据集是使用Monte Carlo方法生成的。第一个数据集包含六个任务，第二个和第三个数据集包含八个任务。第四和第五个数据集包含10个不同的数据集，在每个数据集中，我们考虑两个不同的组，即G1和G2，其中G1包含前50%的任务，G2包含后50%的任务。前五个数据集显示在表19空间限制。我们将所提出的算法与三种现有算法FCFS（Liu et al.，2015年;Gawali和Shinde，2018年），HA-LT（Frank，2005年; Kuhn，2009年）和HA-CLT（Frank，2005年; Kuhn，2009年），使用22个不同的数据集进行停留时间。请注意，停留时间是所有配对任务之间的空闲时间之和，应该最小化。值得一提的是，由于现有算法中不存在成对映射，因此该算法不能直接与现有算法进行比较。表19数据集1有6个任务。G1StDETG2StDETT1十一点整01时30分十二点半T4九点整凌晨一点十点整T215点整01时15分十六点十五分T513点整01时15分14点15分T322点整01时30分二十三点半T6十九点四十五分01时30分二十一点十五分表20数据集2有8个任务。G1StDETG2StDETT1九点整凌晨一点十点整T5十点整凌晨一点十一点整T2十点整凌晨一点十一点整T6十一点整凌晨一点12点整T315点整凌晨一点16点整T714点整凌晨一点15点整T420点整凌晨一点21点整T822点整凌晨一点23点整表21数据集3有8个任务。G1ST D ET G2 ST D ETT1八点半01时15分九点四十五分T513点整01时15分14点15分T2十一点整01时30分十二点半T617点整01时15分十八点十ST附表08：30-09：0009：00-09：45上午9：45-10：00T1T6上午10：00-11：0011：00-12：3012：30-13：00T213：00-14：1514：15-15：00T715：00-16：1516：15-17：00T317：00-18：0018：00-18：1518：15-19：30T8T419：30-19：4519：45-21：1521：15-21：30的t921：30-22：0022：00-23：30T10T5ST附表08：30-09：0009：00-09：45上午9：45-10：00T1T6上午10：00-11：0011：00-12：3012：30-13：00T213：00-14：1514：15-15：00T715：00-16：1516：15-17：00T317：00-18：0018：00-18：1518：15-19：30T4T819：30-19：4519：45-21：1521：15-21：30的t921：30-22：0022：00-23：30T10T51444S.K. Panda等人/沙特国王大学学报五分T315点整凌晨一点16点整T7九点整凌晨一点十点整T420点整凌晨一点21点整T8十一点整凌晨一点12点整S.K. Panda等人/沙特国王大学学报1445表22数据集4有10个任务。表23数据集5有10个任务。文学。因此，我们与FCFS，HA-LT和HA-CLT算法进行了比较值得一提的是，每个数据集的云数量没有显式显示，因为它与停留时间相关。该算法具有根据任务配对增加云资源的灵活性。针对5个和22个不同的数据集计算了所提出的算法PTS的任务分配和停留时间，并分别与FCFS、HA-LT和HA-CLT进行了比较，如表24和25所示由于空间限制，最后17个数据集的任务分配没有显示出来.比较结果清楚地表明，所提出的算法PTS给出了更好的停留时间比现有的算法。这背后的合理性是，所提出的算法在做出调度决策之前对任务进行配对。为了便于可视化，所提出的算法和现有算法的图形比较也显示在图6（前十个数据集）和图。 7（最后12个数据集）。表24比较FCFS、HA-L