---
kind: concept
slug: task-scheduling
title: Task scheduling
summary: >-
  Deciding which machine runs each task and when tasks move. One learned variant is on the wiki so far: an A3C agent with a recurrent network that ranks hosts for each task in an edge-cloud system, judged in a simulator against heuristics and REINFORCE. Its gains are author-reported and simulator-only. Only one paper is covered, so treat this page as a starting point.
tags: [scheduling, edge-cloud, resource-allocation, reinforcement-learning]
papers: ["2009.02186"]
related: [actor-critic, policy-gradient, recurrent-neural-network, carbon-aware-scheduling]
status: draft
updated_at: 2026-11-08
---

## Overview

Task scheduling decides, at each time step, where each task runs, and whether a
running task should move to another host. The hosts differ in speed, memory,
cost and network distance, and the workload changes over time, so the choice
has to be revisited [arxiv:2009.02186 §1] [arxiv:2009.02186 §2.1].

The paper formalises a scheduler as a function from the system state to an
action. The quantity it minimises is a per-interval loss built from energy,
response time, migration time, cost and SLA violations [arxiv:2009.02186 eq. 1]
[arxiv:2009.02186 §3.3]. The variant on this page is a learned policy trained
with reinforcement learning, not a fixed rule [Dynamic Scheduling with A3C and R2N2 (Tuli et al.)](/papers/2009.02186).

The invariant all variants share is that the scheduler must output a feasible
placement for every task in each interval. The variants differ in how they
rank hosts and how they enforce feasibility.

## Variants

### Ranked-host policy with a constraint module (A3C, R2N2)

Instead of picking one host per task, the policy outputs an ordered list of
all hosts for each task, most preferred first. A constraint module then walks
each task's list and assigns the first host that is allowed. A carried-over task
that cannot migrate keeps its host. The penalty for skipped preferences is added
to the training loss [arxiv:2009.02186 §3.2] [arxiv:2009.02186 eq. 3]
[arxiv:2009.02186 eq. 4]. Card: [Dynamic Scheduling with A3C and R2N2 (Tuli et al.)](/papers/2009.02186).

The network is a residual recurrent model. Two dense layers feed three recurrent
layers with skip links, followed by an actor head that outputs a 100 by 100
row-softmax matrix and a critic head that predicts future loss [arxiv:2009.02186 §4.1]
[arxiv:2009.02186 fig. 7]. The 100 by 100 output fixes the capacity at 100
tasks and 100 hosts [arxiv:2009.02186 §4.1].

Training uses asynchronous actor-critic learning over several agents. Gradients
accumulate over an episode of 12 intervals, one hour of simulated time, before
the global network is updated [arxiv:2009.02186 §4.3] [arxiv:2009.02186 alg. 1].
Reported gains over REINFORCE in simulation are a lower total energy (14.4%), a
lower average response time (7.74%), fewer SLA violations (31.9%) and a lower
total cost (4.64%) [arxiv:2009.02186 §5.4.4] [arxiv:2009.02186 fig. 16]. All
of these are author-reported, from CloudSim and iFogSim, on one test day.

### Baselines in the same paper

The paper also reports heuristic schedulers as comparison points: LR-MMT and
MAD-MC [arxiv:2009.02186 §5.3]. Their numbers appear only in figures and are not
stated in the text [arxiv:2009.02186 fig. 16]. Two learned baselines, DDQN and
REINFORCE, are described as adapted to the same setting [arxiv:2009.02186 §5.3].
These are the reference points for the claims above. No card on the wiki covers
the heuristics or DDQN in their own right.

## When to use which

The wiki has one card for this concept, so the table compares the paper's
design with the simpler options it was measured against. It does not show that
the learned policy beats them in general.

| Situation | Use | Why |
|---|---|---|
| You need a simulator-checked comparison first | The ranked-host design as a research baseline | The paper evaluates it in CloudSim and iFogSim against heuristics and REINFORCE [arxiv:2009.02186 §5.3] [arxiv:2009.02186 §5.4.4] |
| Hosts or tasks exceed 100 each | Not this design as specified | The output matrix is 100 by 100 [arxiv:2009.02186 §4.1] |
| No recorded workload trace to normalise against | Not this design as specified | Feature ranges come from a sample run of two heuristics, and the size of that sample is not stated [arxiv:2009.02186 §4.2] |
| You must meet a strict per-task latency or fixed rule | Heuristic baselines, if their numbers suit you | The paper's heuristic results appear only in figures [arxiv:2009.02186 fig. 16] |
| Training time or GPU memory is tight | Smaller recurrent stack | The authors limited the stack to three recurrent layers because four did not fit their GPU [arxiv:2009.02186 §5.4.2] |
| Real edge deployment | Validate in your own system first | All results are simulated. Real edge deployment is listed as future work [arxiv:2009.02186 §7] |

Use the weights from the paper only with care. The reported weights sum to
1.059, not the 1 that the loss definition requires [arxiv:2009.02186 eq. 14]
[arxiv:2009.02186 eq. 10]. Normalise them, or keep them and say so in your
results.

## Implementation sketch

The core loop is the same for any ranked-host policy. The step that varies is
the constraint module. Shapes follow the paper's 100 by 100 output.

```pseudocode
# Per-interval loop of the ranked-host policy  [arxiv:2009.02186 alg. 1]
# Each interval: observe, rank hosts per task, apply feasible actions

def schedule_interval(state, network, constraints):
    # Scale features into [0, 1] using a normalisation fixed in advance  [§4.2]
    x = normalise(state)
    # Actor returns one row of host probabilities per task  [§4.1]
    prob_map = network.actor(x)
    # Sort hosts per task, take the best feasible one  [§3.2] [eq. 3]
    action, penalty = constraints.apply(prob_map)
    # The penalty joins the interval loss at training time  [eq. 11]
    return action, penalty
```

```pseudocode
# Training: update every episode of 12 intervals  [§4.3]
# Actor-critic advantage with a squared critic term  [eq. 13]

def update(buffer, network):
    # Use the gradient of log-probability times the loss plus the critic  [eq. 13]
    policy_term = log_prob(buffer.state) * buffer.loss
    critic_term = (buffer.loss_next - network.critic(buffer.state)) ** 2
    # Accumulate, then apply one step to the global network  [§4.3]
    network.apply_gradient(policy_term + critic_term)
```

Where variants differ: the network type (recurrent, dense or convolutional),
the loss weights, the learning-rate schedule and whether the update is
synchronous or asynchronous. Several of these are not stated in the paper
(see Contradictions), so take the values from the paper's card and test them.

## Contradictions

- **Actor agents, within the paper.** The paper says 10 actor agents are used
  [arxiv:2009.02186 §5.1.2], and in another section says all 100 active hosts act
  as agents [arxiv:2009.02186 §5.4.3]. The card does not resolve this.
- **Loss weights.** The reported optimal weights sum to 1.059, while the loss
  definition requires a convex combination summing to 1
  [arxiv:2009.02186 eq. 14] [arxiv:2009.02186 eq. 10].
- **Scalability numbers.** A speedup of 34.3 on 100 agents is reported with
  efficiency 0.37 [arxiv:2009.02186 §5.4.3]. Dividing the speedup by the agent
  count gives 0.343. This is a conflict inside the paper.
- **Paper and released code.** The paper describes a recurrent residual network
  with a critic and a weighted five-metric loss [arxiv:2009.02186 §4.1]
  [arxiv:2009.02186 eq. 10]. The released Python differs on architecture,
  learning rate, loss and update rule. The card lists each difference
  [Dynamic Scheduling with A3C and R2N2 (Tuli et al.)](/papers/2009.02186).
  Do not treat the code as an implementation of the paper.

## Papers

- [Dynamic Scheduling with A3C and R2N2 (Tuli et al.)](/papers/2009.02186): an
  A3C policy-gradient scheduler for edge and cloud hosts, with a recurrent
  residual network and a constraint module. Simulator results are against
  REINFORCE and heuristics.