Task scheduling

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 2009.02186 §1 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 2009.02186 eq. 1 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.).

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 2009.02186 §3.2 2009.02186 eq. 3 2009.02186 eq. 4. Card: Dynamic Scheduling with A3C and R2N2 (Tuli et al.).

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 2009.02186 §4.1 2009.02186 fig. 7. The 100 by 100 output fixes the capacity at 100 tasks and 100 hosts 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 2009.02186 §4.3 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%) 2009.02186 §5.4.4 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 2009.02186 §5.3. Their numbers appear only in figures and are not stated in the text 2009.02186 fig. 16. Two learned baselines, DDQN and REINFORCE, are described as adapted to the same setting 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.

Use the weights from the paper only with care. The reported weights sum to 1.059, not the 1 that the loss definition requires 2009.02186 eq. 14 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.

# 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

# 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 2009.02186 §5.1.2, and in another section says all 100 active hosts act as agents 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 2009.02186 eq. 14 2009.02186 eq. 10.
• Scalability numbers. A speedup of 34.3 on 100 agents is reported with efficiency 0.37 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 2009.02186 §4.1 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.). Do not treat the code as an implementation of the paper.

Papers

• Dynamic Scheduling with A3C and R2N2 (Tuli et al.): 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.