Scenarios / Cloud scheduling

AI for Real-Time Distributed Cloud Job Scheduling

Real-time job dispatch on heterogeneous servers

Shared objective

Keep job queues short and run work on efficient servers

Each dispatcher observes

Server utilization and queues, and the arriving jobs

Each dispatcher decides

Which server group its job goes to, every step

How the cluster responds to changing demand

Distributed heuristic

Power of two choices

Each server: utilization and queued jobs

With AI control

Adaptive

Each server: utilization and queued jobs

Utilization (lower part, 0 to 100 %) Queued jobs (upper part, 0 to 20)

Energy per unit of work: energy relative to running the same work on servers of efficiency 1.

How to train such an AI efficiently?

Why conventional multi-agent training struggles at scale

One agent's share of the shared reward

Illustration with equal contributions: the blue slice is what agent i's own action causes.

Noise in each agent's learning signal

With conventional multi-agent reinforcement learning, every agent learns from the same reward, in which its own effect shrinks as the system grows.

How our algorithm trains the dispatchers, step by step

With global information about the whole system, queueing theory identifies an ideal load, in which every server group carries work in proportion to its effective capacity, keeping queues short and work on efficient servers. Although this ideal state cannot be reached, could such knowledge be internalized into how the agents are trained?

Referenceoffline, centralized

{\tilde{x}}_{c}^{k} (t) = \frac{μ_{c}^{k}}{\sum_{j} μ_{j}^{k}} \sum_{j} W_{j}^{k} (t), k \in {CPU, memory}

Balanced load: every server group c carries work in proportion to its effective capacity μ (capacity × efficiency); W is the remaining work.

Guidanceper dispatcher

g_{i} (t) = \sum_{k} (\frac{W_{c}^{k} (t)}{μ_{c}^{k}} - \frac{\sum_{j} W_{j}^{k} (t)}{\sum_{j} μ_{j}^{k}}) d_{i}^{k} τ_{i}

How far the group chosen for job i is above the balanced load, weighted by the job's demand d and duration τ; negative when the job goes to an under-loaded group.

Learning signalper dispatcher

{\hat{A}}_{i} (t) = (1 - α) A (t) - α {\hat{g}}_{i} (t)

Shared advantage A of the reward r = −(jobs waiting / N + energy term), combined with the normalized guidance with weight α = 0.9 in every episode shown here.

Policy updateinternalizes the reference

\nabla_{θ} J \approx \sum_{t} \sum_{i} {\hat{A}}_{i} (t) \nabla_{θ} \log π_{θ} (a_{i} (t) | o_{i} (t))

Each dispatcher acts on its own observation o_i; the reference and the guidance are not needed at run time.

At its core, our algorithm uses prior knowledge of the system, in the form of a reference state, to guide the training of decentralized policies and give every agent a clear optimization signal. Through training, each agent will internalize in its policy where to send its job based on what it observes.

The charts below show A(t) and −ĝ_i(t) during one training run.

One dispatcher during training

Step

All active dispatchers at the selected step

One training run after 5 episodes. Separate vertical scales. Click a bar to select a dispatcher.

Learning progress

Jobs queued at servers on the replayed scenario

Episode