# Stochastic SchedulingÂ¶

## Principles learnedÂ¶

• Use list decision variables

• Use a lambda expression to sum over a set

• Use the sort operator

## ProblemÂ¶

The Stochastic Scheduling Problem is defined as a set of tasks that has to be processed by machines. Any machine can independently process all tasks, but tasks have random processing times. Here, the randomness is represented by scenarios, where a scenario defines the processing times of all the tasks. Given a processing schedule, each scenario yields a makespan: the time when all tasks have been processed.

Now, which objective is most appropriate to minimize the stochastic makespan?

Minimizing the average makespan can hide risky scenarios while minimizing the worst-case might be too pessimistic. A usual compromise to build a robust scenario is to optimize on a given percentile. It is what is done, minimizing the 90 th percentile of makespans. Thanks to the sort operator, such a nonlinear criterion is straightforward to model using LocalSolver.

## DataÂ¶

For this example, we generate instances at runtime: first a uniform distribution is picked for each task, then for each scenario, the processing time of each task is independently sampled from the corresponding uniform distribution.

## ProgramÂ¶

We use a set decision variable to represent the set of tasks processed by each machine. Those sets are constrained to form a partition as each task must be processed by exactly one machine.

We then compute and store in the `scenarioMakespan` array the makespan corresponding to each scenario. To do so, we first need to compute the total processing time of each machine as a sum over a set and therefore need to define a lambda expression.

We can then sort the array of makespans and access our objective function: its 9 th decile.

Execution:
localsolver stochastic_scheduling.lsp [lsTimeLimit=n] [solFileName=solution.txt]
```use random;

/* Generate instance data */
function input() {
nbMachines = 2;
nbScenarios = 3;
rngSeed = 42;

// Pick random parameters for each task distribution
rng = random.create(rngSeed);

// Sample the distributions to generate the scenarios
}

/* Declare the optimization model */
function model() {

// Each task must be processed by exactly one machine

// Compute makespan of each scenario
scenarioMakespan[m in 0...nbScenarios] <- max[k in 0...nbMachines](

// Compute the 90th percentile of scenario makespans
stochasticMakespan <- sort(scenarioMakespan)[ceil(0.9 * (nbScenarios - 1))];

minimize stochasticMakespan;
}

// Parametrize the solver
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 2;
}

/* Write the solution */
function output() {
println();
for [i in 0...nbScenarios] {
print(i + ": [");
print(scenarioTaskDurations[i][j] + (j == nbTasks - 1 ? "" : ", "));
println("]");
}

println();
println("Machines:");
for [k in 0...nbMachines]
println(k + ": " + machineTasks[k].value);
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python stochastic_scheduling.py
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python stochastic_scheduling.py
```from __future__ import print_function
import random
import math
import localsolver

random.seed(rng_seed)

# Pick random parameters for each task distribution

# Sample the distributions to generate the scenarios
for _ in range(nb_scenarios)]

def main(nb_tasks, nb_machines, nb_scenarios, seed, time_limit):
# Generate instance data

with localsolver.LocalSolver() as ls:
#
# Declare the optimization model
#
model = ls.model

# Each task must be processed by exactly one machine

# Compute makespan of each scenario
scenarios_makespan = model.array(
model.max(
model.sum(machine,
model.lambda_function(
lambda i:
for machine in machine_tasks) for k in range(nb_scenarios))

# Compute the 90th percentile of scenario makespans
stochastic_makespan = \
model.sort(scenarios_makespan)[int(math.ceil(0.9 * (nb_scenarios - 1)))]

model.minimize(stochastic_makespan)
model.close()

# Parameterize the solver
ls.param.time_limit = time_limit

ls.solve()

#
# Write the solution
#
print()
print(i, ': ', scenario, sep='')

print()
print("Machines:")
print(k, ': ', machine.value, sep='')

if __name__ == '__main__':
nb_machines = 2
nb_scenarios = 3
rng_seed = 42
time_limit = 2

main(
nb_machines,
nb_scenarios,
rng_seed,
time_limit
)
```
Compilation / Execution (Windows)
cl /EHsc stochastic_scheduling.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
stochastic_scheduling
Compilation / Execution (Linux)
g++ stochastic_scheduling.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o stochastic_scheduling
stochastic_scheduling
```#include "localsolver.h"
#include <cmath>
#include <iostream>
#include <random>
#include <vector>

using namespace localsolver;

class StochasticScheduling {
private:
// Number of machines
int nbMachines;
// Number of scenarios
int nbScenarios;
// For each scenario, the processing time of each task

// LocalSolver
LocalSolver localsolver;
// Decision variable for the assignment of tasks
// For each scenario, the corresponding makespan
std::vector<LSExpression> scenarioMakespan;
// Objective = minimize the 9th decile of all possible makespans
LSExpression stochasticMakespan;

void generateScenarios(unsigned int rngSeed) {
std::mt19937 rng(rngSeed);
std::uniform_int_distribution<int> distMin(10, 100);
std::uniform_int_distribution<int> distDelta(0, 50);

// Pick random parameters for each task distribution
for (int i = 0; i < nbTasks; ++i) {
int min = distMin(rng);
int max = min + distDelta(rng);
}

// Sample the distributions to generate the scenarios
for (int i = 0; i < nbScenarios; ++i) {
for (int j = 0; j < nbTasks; ++j) {
}
}
}

public:
StochasticScheduling(int nbTasks, int nbMachines, int nbScenarios, unsigned int seed)
generateScenarios(seed);
}

void solve(int timeLimit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

scenarioMakespan.resize(nbScenarios);

for (int k = 0; k < nbMachines; ++k) {
}

// Each task must be processed by exactly one machine

// Compute makespan of each scenario
for (int m = 0; m < nbScenarios; ++m) {
LSExpression taskLambda = model.createLambdaFunction([&](LSExpression i) { return scenario[i]; });
std::vector<LSExpression> machinesMakespan(nbMachines);

for (int k = 0; k < nbMachines; ++k) {
}
scenarioMakespan[m] = model.max(machinesMakespan.begin(), machinesMakespan.end());
}

// Compute the 90th percentile of scenario makespans
LSExpression scenarioMakespanArray = model.array(scenarioMakespan.begin(), scenarioMakespan.end());
LSExpression sortedScenarioMakespan = model.sort(scenarioMakespanArray);
stochasticMakespan = sortedScenarioMakespan[(int)std::ceil(0.9 * (nbScenarios - 1))];

model.minimize(stochasticMakespan);
model.close();

// Parametrize the solver
localsolver.getParam().setTimeLimit(timeLimit);

localsolver.solve();
}

/* Write the solution */
void writeSolution(std::ostream& os) const {
for (int i = 0; i < nbScenarios; ++i) {
os << i << ": [";
for (int j = 0; j < scenarioTaskDurations[i].size(); ++j) {
os << scenarioTaskDurations[i][j] << (j == scenarioTaskDurations[i].size() - 1 ? "" : ", ");
}
os << "]\n";
}

os << "\nMachines:\n";
for (int m = 0; m < nbMachines; ++m) {
os << m << ": { ";
for (int i = 0; i < tasks.count(); ++i) {
os << tasks[i] << (i == tasks.count() - 1 ? " " : ", ");
}
os << "}\n";
}
}
};

int main(int argc, char** argv) {
int nbMachines = 2;
int nbScenarios = 3;
int rngSeed = 42;
int timeLimit = 2;

try {
model.solve(timeLimit);
model.writeSolution(std::cout);
return 0;
} catch (const std::exception& e) {
std::cerr << "An error occurred: " << e.what() << std::endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc StochasticScheduling.cs /reference:localsolvernet.dll
StochasticScheduling
```using System;

using localsolver;

public class StochasticScheduling : IDisposable
{

// Number of machines
int nbMachines;

// Number of scenarios
int nbScenarios;

// For each scenario, the processing time of each task

// LocalSolver
LocalSolver localsolver;

// Decision variable for the assignment of tasks

// For each scenario, the corresponding makespan
LSExpression[] scenarioMakespan;

// Objective = minimize the 9th decile of all possible makespans
LSExpression stochasticMakespan;

private void generateScenarios(int rngSeed)
{
Random rng = new Random(rngSeed);

// Pick random parameters for each task distribution
for (int i = 0; i < nbTasks; ++i)
{
}

// Sample the distributions to generate the scenarios
for (int i = 0; i < nbScenarios; ++i)
{
for (int j = 0; j < nbTasks; ++j)
}
}

public StochasticScheduling(int nbTasks, int nbMachines, int nbScenarios, int rngSeed)
{
localsolver = new LocalSolver();
this.nbMachines = nbMachines;
this.nbScenarios = nbScenarios;
generateScenarios(rngSeed);
}

public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}

void Solve(int limit)
{
// Declare the optimization model
LSModel model = localsolver.GetModel();

scenarioMakespan = new LSExpression[nbScenarios];

for (int k = 0; k < nbMachines; ++k)

// Each task must be processed by exactly one machine

// Compute makespan of each scenario
for (int m = 0; m < nbScenarios; ++m)
{
LSExpression taskLambda = model.LambdaFunction(i => scenario[i]);
LSExpression[] machinesMakespan = new LSExpression[nbMachines];

for (int k = 0; k < nbMachines; ++k)
scenarioMakespan[m] = model.Max(machinesMakespan);
}

// Compute the 90th percentile of scenario makespans
LSExpression scenarioMakespanArray = model.Array(scenarioMakespan);
LSExpression sortedScenarioMakespan = model.Sort(scenarioMakespanArray);
stochasticMakespan = sortedScenarioMakespan[(int)Math.Ceiling(0.9 * (nbScenarios - 1))];

model.Minimize(stochasticMakespan);
model.Close();

// Parametrize the solver
localsolver.GetParam().SetTimeLimit(limit);

localsolver.Solve();
}

/* Write the solution */
private void WriteSolution()
{
Console.WriteLine();
for (int i = 0; i < nbScenarios; ++i)
{
Console.Write(i + ": [");
for (int j = 0; j < nbTasks; ++j)
Console.Write(scenarioTaskDurations[i][j] + (j == nbTasks - 1 ? "" : ", "));
Console.WriteLine("]");
}

Console.WriteLine();
Console.WriteLine("Machines:");

for (int m = 0; m < nbMachines; ++m)
{
Console.Write(m + ": { ");
for (int i = 0; i < tasks.Count(); ++i)
Console.Write(tasks.Get(i) + (i == tasks.Count() - 1 ? " " : ", "));
Console.WriteLine("}");
}
}

public static void Main(string[] args)
{
int nbMachines = 2;
int nbScenarios = 3;
int rngSeed = 43;
int timeLimit = 2;

using (
StochasticScheduling model = new StochasticScheduling(
nbMachines,
nbScenarios,
rngSeed
)
)
{
model.Solve(timeLimit);
model.WriteSolution();
}
}
}
```
Compilation / Execution (Windows)
javac StochasticScheduling.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. StochasticScheduling
Compilation/Execution (Linux)
javac StochasticScheduling.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. StochasticScheduling
```import java.util.Random;

import localsolver.*;

public class StochasticScheduling {

// Number of machines
private int nbMachines;

// Number of scenarios
private int nbScenarios;

// For each scenario, the processing time of each task

// LocalSolver
private final LocalSolver localsolver;

// Decision variable for the assignment of tasks

// For each scenario, the corresponding makespan
private LSExpression[] scenarioMakespan;

// Objective = minimize the 9th decile of all possible makespans
private LSExpression stochasticMakespan;

private void generateScenarios(int rngSeed) {
Random rng = new Random(rngSeed);

// Pick random parameters for each task distribution
for (int i = 0; i < nbTasks; ++i) {
}

// Sample the distributions to generate the scenarios
for (int i = 0; i < nbScenarios; ++i) {
for (int j = 0; j < nbTasks; ++j) {
}
}
}

private StochasticScheduling(LocalSolver localsolver, int nbTasks, int nbMachines, int nbScenarios, int rngSeed) {
this.localsolver = localsolver;
this.nbMachines = nbMachines;
this.nbScenarios = nbScenarios;
generateScenarios(rngSeed);
}

private void solve(int limit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

scenarioMakespan = new LSExpression[nbScenarios];

for (int k = 0; k < nbMachines; ++k) {
}

// Each task must be processed by exactly one machine

// Compute makespan of each scenario
for (int m = 0; m < nbScenarios; ++m) {
LSExpression taskLambda = model.lambdaFunction(i -> model.at(scenario, i));
LSExpression[] machinesMakespan = new LSExpression[nbMachines];

for (int k = 0; k < nbMachines; ++k) {
}
scenarioMakespan[m] = model.max(machinesMakespan);
}

// Compute the 90th percentile of scenario makespans
LSExpression scenarioMakespanArray = model.array(scenarioMakespan);
LSExpression sortedScenarioMakespan = model.sort(scenarioMakespanArray);
stochasticMakespan = model.at(sortedScenarioMakespan, (int) Math.ceil(0.9 * (nbScenarios - 1)));

model.minimize(stochasticMakespan);
model.close();

// Parametrize the solver
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

/* Write the solution */
private void writeSolution() {
System.out.println();
for (int i = 0; i < nbScenarios; ++i) {
System.out.print("" + i + ": [");
for (int j = 0; j < nbTasks; ++j) {
System.out.print("" + scenarioTaskDurations[i][j] + (j == nbTasks - 1 ? "" : ", "));
}
System.out.println("]");
}

System.out.println();
System.out.println("Machines:");

for (int m = 0; m < nbMachines; ++m) {
System.out.print("" + m + ": { ");
for (int i = 0; i < tasks.count(); ++i) {
System.out.print("" + tasks.get(i) + (i == tasks.count() - 1 ? " " : ", "));
}
System.out.println("}");
}
}

public static void main(String[] args) {
try (LocalSolver localsolver = new LocalSolver()) {
int nbMachines = 2;
int nbScenarios = 3;
int rngSeed = 42;
int timeLimit = 2;

StochasticScheduling model = new StochasticScheduling(localsolver, nbTasks, nbMachines, nbScenarios,
rngSeed);

model.solve(timeLimit);
model.writeSolution();
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
};
```