<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "https://jats.nlm.nih.gov/publishing/1.3/JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xml:lang="en">
  <front xmlns:xlink="http://www.w3.org/1999/xlink">
    <journal-meta>
      <journal-title-group>
        <journal-title>Computing, Telecommunication and Control</journal-title>
        <trans-title-group xml:lang="ru">
          <trans-title>Информатика, телекоммуникации и управление</trans-title>
        </trans-title-group>
      </journal-title-group>
      <issn pub-type="epub">2687-0517</issn>
    </journal-meta>
    <article-meta xmlns:xlink="http://www.w3.org/1999/xlink">
      <article-id pub-id-type="publisher-id">7</article-id>
      <article-id pub-id-type="doi">10.18721/JCSTCS.19107</article-id>
      <title-group>
        <article-title>A Lyapunov-based dynamic scheduling algorithm for heterogeneous computing clusters</article-title>
        <trans-title-group xml:lang="ru">
          <trans-title>Алгоритм динамического планирования на основе функции Ляпунова для гетерогенных вычислительных кластеров</trans-title>
        </trans-title-group>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <contrib-id contrib-id-type="orcid">0000-0001-8591-9080</contrib-id>
          <name>
            <surname>Wang</surname>
            <given-names>Shan</given-names>
          </name>
          <xref ref-type="aff" rid="aff1"/>
          <email>wangshan@mail.ru</email>
        </contrib>
        <contrib contrib-type="author">
          <name>
            <surname>Nikiforov</surname>
            <given-names>Igor</given-names>
          </name>
          <email>igor.nikiforov@gmail.com</email>
        </contrib>
      </contrib-group>
      <aff id="aff1">Peter the Great St. Petersburg Polytechnic University</aff>
      <pub-date publication-format="electronic" date-type="pub" iso-8601-date="2026-03-31">
        <day>31</day>
        <month>03</month>
        <year>2026</year>
      </pub-date>
      <volume>19</volume>
      <issue>1</issue>
      <fpage>65</fpage>
      <lpage>79</lpage>
      <self-uri xmlns:xlink="http://www.w3.org/1999/xlink" content-type="pdf" xlink:href="https://infocom.spbstu.ru/userfiles/files/articles/2026/1/65-79.pdf"/>
      <abstract xml:lang="en">
        <p>The paper proposes a Lyapunov-based dynamic scheduling algorithm for heteroge-neous computing clusters, targeting fine-grained resource control under bursty and latency-sensitive workloads. By constructing a quadratic Lyapunov function and applying a drift-plus-penalty framework, the scheduling problem is formulated as a two-criteria optimization problem balancing queue stability and scheduling delay. A dynamic control parameter V is introduced to quantitatively regulate the trade-off between backlog stability and delay minimization. Sensitivity analysis demonstrates an O(1/V) backlog and O(V) delay trade-off. Experiments conducted on the Alibaba GPU cluster trace dataset show that under burst-dominant workloads, the proposed method reduces average scheduling delay to 0.2663 seconds, while achieving a 0.5459 resource utilization and a 0.6489 fairness index. The method is particularly suitable for latency-sensitive and dynamically fluctuating environments.</p>
      </abstract>
      <kwd-group xml:lang="en">
        <kwd>Lyapunov optimization</kwd>
        <kwd>drift-plus-penalty</kwd>
        <kwd>resource scheduling</kwd>
        <kwd>cloud computing</kwd>
        <kwd>two-criteria optimization</kwd>
      </kwd-group>
    </article-meta>
  </front>
  <back>
    <ref-list>
      <title>References</title>
      <ref id="ref1">
        <mixed-citation publication-type="journal">Ismail A.A., Khalifa N.E., El-Khoribi R.A. A survey on resource scheduling approaches in multi-access edge computing environment: a deep reinforcement learning study. Cluster Computing, 2025, Vol. 28, Art. no. 184. DOI: 10.1007/s10586-024-04893-7</mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation publication-type="journal">Polo J., Castillo C., Carrera D., Becerra Y., Whalley I., Steinder M., Torres J., Ayguadé E. Resource-aware adaptive scheduling for MapReduce clusters. In: Middleware 2011: Lecture Notes in Computer Science (eds. F. Kon, A.M. Kermarrec), 2011, Vol. 7049, Pp. 187–207. DOI: 10.1007/978-3-642-25821-3_10</mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation publication-type="journal">Chen Y., Griffith R., Liu J., Katz R.H., Joseph A.D. Understanding TCP incast throughput collapse in datacenter networks. Proceedings of the 1st ACM Workshop on Research on Enterprise Networking, 2009, Pp. 73–82. DOI: 10.1145/1592681.1592693</mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation publication-type="journal">Hindman B., Konwinski A., Zaharia M., Ghodsi A., Joseph A.D., Katz R., Shenker S., Stoica I. Mesos: A platform for fine-grained resource sharing in the data center. Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, 2011, Pp. 295–308.</mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation publication-type="journal">Neely M.J. Stochastic Network Optimization with Application to Communication and Queueing Systems. Cham: Springer, 2010. DOI: 10.1007/978-3-031-79995-2</mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation publication-type="journal">Shi Y., Yang K., Jiang T., Zhang J., Letaief K.B. Communication-efficient edge AI: Algorithms and systems. arXiv:2002.09668, 2020. DOI: 10.48550/arXiv.2002.09668</mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation publication-type="journal">Shahrad M., Fonseca R., Goiri Í., Chaudhry G., Batum P., Cooke J., Laureano E., Tresness C., Russinovich M., Bianchini R. Serverless in the wild: characterizing and optimizing the serverless workload at a large cloud provider. Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, 2020, Pp. 205–218.</mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation publication-type="journal">Zhang J., Zhai Y., Liu Z., Wang Y. A Lyapunov-based resource allocation method for edge-assisted industrial internet of things. IEEE Internet of Things Journal, 2024, Vol. 11, No. 24, Pp. 39464–39472. DOI: 10.1109/JIOT.2024.3446722</mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation publication-type="journal">Gao Y., Liu L., Zheng X., Zhang C., Ma H. Federated sensing: Edge-cloud elastic collaborative learning for intelligent sensing. IEEE Internet of Things Journal, 2021, Vol. 8, No. 14, Pp. 11100–11111. DOI: 10.1109/JIOT.2021.3053055</mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation publication-type="journal">Tang S., He B.-S., Zhang S., Niu Z. Elastic multi-resource fairness: balancing fairness and efficiency in coupled CPU-GPU architectures. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2016, Pp. 875–886. DOI: 10.1109/SC.2016.74</mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation publication-type="journal">Verma A., Pedrosa L., Korupolu M., Oppenheimer D., Tune E., Wilkes J. Large-scale cluster management at Google with Borg. Proceedings of the 10th European Conference on Computer Systems, 2015, Art. no. 18. DOI: 10.1145/2741948.2741964</mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation publication-type="journal">Reiss C., Wilkes J. Google cluster-usage traces: format + schema. Google Inc. Technical Report, 2011.</mixed-citation>
      </ref>
      <ref id="ref13">
        <mixed-citation publication-type="journal">Burns B., Grant B., Oppenheimer D., Brewer E., Wilkes J. Borg, Omega, and Kubernetes. Communications of the ACM, 2016, Vol. 59, No. 5, Pp. 50–57. DOI: 10.1145/2890784</mixed-citation>
      </ref>
      <ref id="ref14">
        <mixed-citation publication-type="journal">Ghodsi A., Zaharia M., Hindman B., Konwinski A., Shenker S., Stoica I. Dominant resource fairness: fair allocation of multiple resource types. Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, 2011, Pp. 323–336.</mixed-citation>
      </ref>
      <ref id="ref15">
        <mixed-citation publication-type="journal">Xiao W., Bhardwaj R., Ramjee R. et al. Gandiva: introspective cluster scheduling for deep learning workloads. Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation, 2018, Pp. 595–610.</mixed-citation>
      </ref>
      <ref id="ref16">
        <mixed-citation publication-type="journal">Zhao X., Yao J., Gao P., Guan H. Efficient sharing and fine-grained scheduling of virtualized GPU resources. 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), 2018, Pp. 742–752. DOI: 10.1109/ICDCS.2018.00077</mixed-citation>
      </ref>
      <ref id="ref17">
        <mixed-citation publication-type="journal">Sukhoroslov O. Building web-based services for practical exercises in parallel and distributed computing. Journal of Parallel and Distributed Computing, 2018, Vol. 118 (1), Pp. 177–188. DOI: 10.1016/j.jpdc.2018.02.024</mixed-citation>
      </ref>
      <ref id="ref18">
        <mixed-citation publication-type="journal">Mao Y., You C., Zhang J., Huang K., Letaief K.B. A survey on mobile edge computing: The communication perspective. IEEE Communications Surveys &amp; Tutorials, 2017, Vol. 19, No. 4, Pp. 2322–2358. DOI: 10.1109/COMST.2017.2745201</mixed-citation>
      </ref>
      <ref id="ref19">
        <mixed-citation publication-type="journal">Beloglazov A., Buyya R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers. Concurrency and Computation: Practice and Experience, 2012, Vol. 24, No. 13, Pp. 1397–1420. DOI: 10.1002/cpe.1867</mixed-citation>
      </ref>
      <ref id="ref20">
        <mixed-citation publication-type="journal">Smorodnikov G., Zolotarev R., Rykova A., Sabutkevich A., Samochadin A. Elastic cloud resource allocation using short-term long short-term memory-based workload prediction. Proceedings of the 4th International Conference on Optics, Computer Applications, and Materials Science (CMSD-IV 2024), 2025, Vol. 13651, Art. no. 136510J. DOI: 10.1117/12.3060861</mixed-citation>
      </ref>
      <ref id="ref21">
        <mixed-citation publication-type="journal">Sukhoroslov O., Nazarenko A., Aleksandrov R. An experimental study of scheduling algorithms for many-task applications. The Journal of Supercomputing, 2019, Vol. 75, Pp. 7857–7871. DOI: 10.1007/s11227-018-2553-9</mixed-citation>
      </ref>
      <ref id="ref22">
        <mixed-citation publication-type="journal">Sukhoroslov O. Supporting efficient execution of workflows on Everest platform. Supercomputing (RuSCDays), 2019, Pp. 713–724. DOI: 10.1007/978-3-030-36592-9_58</mixed-citation>
      </ref>
      <ref id="ref23">
        <mixed-citation publication-type="journal">Peng Y., Bao Y., Chen Y., Wu C., Guo C. Optimus: an efficient dynamic resource scheduler for deep learning clusters. Proceedings of the 13th EuroSys Conference, 2018, Art. no. 3. DOI: 10.1145/3190508.3190517</mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>
