Online Scheduling for Dynamic and Unpredictable Workloads

This direction is split into other directions: dynamic task arrival (dynamic job arrival). Its last version stays readable and citable here.

Version 1 of 1266 papers284 conceptsfrozen 2026-10-04

Most classical scheduling theory operates under a "God’s eye view" assumption: the scheduler knows every task’s release date, deadline, and resource requirement before the first clock cycle ticks. In this offline world, researchers like Amirhossein Esmaili, Mahdi Nazemi, and Massoud Pedram can use Mixed Integer Linear Programming (MILP) to find mathematically perfect balances between energy consumption and performance.

However, the papers in this research direction argue that this "offline" luxury is increasingly rare. Whether it is a cloud server receiving a burst of SQL queries, an autonomous vehicle encountering a sudden obstacle, or an electric vehicle (EV) plugging into a charging station, the real world is a continuous, unpredictable stream. The core challenge of this field is transitioning from static, batch-oriented optimization to online scheduling—making high-quality decisions in real-time without knowing what the next millisecond will bring.

The Failure of the Static Snapshot

The fundamental problem with offline scheduling is its fragility. A schedule optimized for a fixed "snapshot" of tasks becomes suboptimal or even useless the moment a new task arrives or an existing task takes longer than expected.

In the context of autonomous applications, Mingcong Han and Haibo Chen 0001 point out that a 100ms delay in computation can be the difference between safety and a collision. If a scheduler relies on static execution profiles, it cannot adapt to the input variability inherent in real-world environments. Similarly, in cloud environments, Xiaohong Hao and Juan Cao observe that treating tasks as static batches ignores the "bursty" nature of real-world traffic, leading to poor load balancing and wasted revenue.

Bridging the Gap with Online Algorithms

To move beyond static snapshots, researchers are developing algorithms that can handle "streaming" workloads. The goal is to achieve a competitive ratio—a guarantee that the online algorithm's performance will stay within a constant factor of the theoretical offline optimum.

For example, Jiao Ying Huang and Bo Yang tackle geo-distributed data analytics by introducing "switching costs." Their algorithms, OSR and MFHC, make placement decisions on-the-fly, balancing the cost of moving data against the benefit of faster execution. In the realm of data structures, Christopher Chung and Bertrand Simon have developed $O(1)$-approximation algorithms for Root-to-Leaf Scheduling in Write-Optimized Trees, allowing systems to flush messages efficiently even as new ones arrive continuously.

Learning to Schedule in Real Time

As systems become more complex—involving heterogeneous processors (XPUs), GPUs, and multi-tenant environments—traditional combinatorial math often becomes too slow for real-time use. This has led to a surge in learning-based schedulers that "intuitionize" the best path forward.

  • Reinforcement Learning: Chenhao Xu and Jiannan Wang 0002 introduced BQSched, which uses RL to schedule SQL queries without needing to know the internal state of the database. Similarly, Bingqian Du and Chuan Wu use Deep RL in their LAPP framework to jointly optimize pricing and task placement in the cloud.
  • Meta-Heuristics: For edge-cloud offloading, Hao Dai and Shigen Shen developed PECCO, which uses an enhanced Moth-Flame Optimization to navigate the non-differentiable trade-offs of profit and cost in real-time.

Handling Uncertainty and Heterogeneity

A major sub-theme in this research is resilience. If you don't know when a task will arrive or how long it will take, how do you guarantee a result?

Amanda Prorok addresses this in robotics by using "redundant robots." By deploying more agents than strictly necessary, the system becomes resilient to travel-time uncertainty. In hardware, Hyoukjun Kwon and Vikas Chandra propose Heterogeneous Dataflow Accelerators, which use specialized sub-accelerators to handle the diverse, unpredictable workloads of modern AI applications like AR/VR.

The Path Forward: Fluid Systems

The ultimate goal of this research direction is to move away from "stop-and-calculate" architectures. As Yujie Wang and Xupeng Miao demonstrate with their Spindle system for large model training, the future lies in "fluid" rescheduling. Instead of snapshot-based planning, these systems use fine-grained resource allocation to respond to live workload changes, ensuring that even as tasks are added or removed, the hardware remains at peak efficiency.

By treating scheduling as a continuous, online process rather than a one-time offline puzzle, this field is enabling the next generation of responsive, energy-efficient, and autonomous technology.

Papers in this version

Showing 60 of 266 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_scheduling_for_dynamic_and_unpred_60a886a4,
  title = {Online Scheduling for Dynamic and Unpredictable Workloads},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-scheduling-for-dynamic-and-unpredictable-workloads/rdr_60a886a460424657844128eb858e1c6c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_scheduling_for_dynamic_and_unpred_60a886a4_v1,
  title = {Online Scheduling for Dynamic and Unpredictable Workloads},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-scheduling-for-dynamic-and-unpredictable-workloads/rdr_60a886a460424657844128eb858e1c6c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}