Stochastic Scheduling¶

/********** stochastic_scheduling.java **********/

import java.io.*;
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;

    // Solver
    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) {
        // Declares 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 taskSelector = 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], taskSelector);
            }
            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();

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

        localsolver.solve();
    }

    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);
        }
    }
};