Stochastic Scheduling¶

import java.util.Random;

import localsolver.*;

public class StochasticScheduling {
    // Number of tasks
    private int nbTasks;

    // Number of machines
    private int nbMachines;

    // Number of scenarios
    private int nbScenarios;

    // For each scenario, the processing time of each task
    private int[][] scenarioTaskDurations;

    // LocalSolver
    private final LocalSolver localsolver;

    // Decision variable for the assignment of tasks
    private LSExpression[] machineTasks;

    // 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
        int[] tasksMin = new int[nbTasks];
        int[] tasksMax = new int[nbTasks];
        for (int i = 0; i < nbTasks; ++i) {
            tasksMin[i] = 10 + rng.nextInt(91);
            tasksMax[i] = tasksMin[i] + rng.nextInt(51);
        }

        // Sample the distributions to generate the scenarios
        scenarioTaskDurations = new int[nbScenarios][nbTasks];
        for (int i = 0; i < nbScenarios; ++i) {
            for (int j = 0; j < nbTasks; ++j) {
                scenarioTaskDurations[i][j] = tasksMin[j] + rng.nextInt(tasksMax[i] - tasksMin[i] + 1);
            }
        }
    }

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

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

        machineTasks = new LSExpression[nbMachines];
        scenarioMakespan = new LSExpression[nbScenarios];

        // Set decisions: machineTasks[k] represents the tasks processed my machine k
        for (int k = 0; k < nbMachines; ++k) {
            machineTasks[k] = model.setVar(nbTasks);
        }

        // Each task must be processed by exactly one machine
        model.constraint(model.partition(machineTasks));

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

            for (int k = 0; k < nbMachines; ++k) {
                machinesMakespan[k] = model.sum(machineTasks[k], taskLambda);
            }
            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();
        System.out.println("Scenario task durations:");
        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 + ": { ");
            LSCollection tasks = machineTasks[m].getCollectionValue();
            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 nbTasks = 10;
            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);
        }
    }
};