• Docs »
  • Tutorials »
  • Modeling Scheduling Problems with Interval Decisions

Modeling Scheduling Problems with Interval Decisions

Interval decision variables are very useful to model the time span of tasks in scheduling problems. When modeling disjunctive scheduling problems, interval decisions are often paired with list decision variables. Indeed, list decisions are a very powerful modeling feature for various problems where collections of items have to be ordered in an optimized fashion. When considering a disjunctive scheduling problem, it is often useful to know the order in which the tasks are processed on the resources, to access the task in position i, or the neighboring tasks of a given task. Other typical use cases for list decisions include routing, production planning, or even assignment problems. Indeed, list-based models for such problems are very compact and straightforward. Not only are they easier to write than classic MILP models, they also allow Hexaly to scale well and achieve state-of-the-art results even on very large instances. For more information, check out our scheduling benchmarks page.

Starting with the Job Shop Scheduling Problem, this page illustrates the good modeling practices for scheduling problems through guided step-by-step examples.

The Job Shop Scheduling Problem (JSSP)

In the Job Shop Scheduling Problem (JSSP), a set of jobs has to be processed on every machine in the shop. The jobs consist in ordered sequences of tasks (called activities). An activity represents the processing of the job on one of the machines and has a given processing time. Each job has one activity per machine, and each activity can only start when the previous one has ended. Each machine can only process one activity at a time. The goal is to find a sequence of jobs that minimizes the makespan: the time when all jobs have been processed.

While it is possible to write a linear program for the Job Shop Scheduling Problem (JSSP), classic MILP models for this problem tend to be large and intricate. A common formulation represents the tasks’ start times with integer variables, but requires a quadratic number of additional binary decisions to model the non-overlap constraints. Alternatively, time-indexed formulations use binary variables to indicate whether a task starts at each possible time step; while conceptually simple, these formulations can require a very large number of binary variables as the planning horizon grows. In both cases, the size of the models makes it harder for solvers to efficiently solve large instances.

On the contrary, by using interval and list decisions, combined with lambda functions, the Hexaly model for the Job Shop Scheduling Problem (JSSP) only has a linear number of decision variables and constraints, helping the solver scale to much larger instances.

The Hexaly model for the Job Shop Scheduling Problem (JSSP) starts with the definition of the interval decision variables. We use one interval decision for each activity, representing its time span: tasks[j][m] represents the time span of the activity of job j that is processed on machine m:

tasks[j in 0...nbJobs][m in 0...nbMachines] <- interval(0, maxEnd);

tasks = [[model.interval(0, max_end) for m in range(nb_machines)] for j in range(nb_jobs)]

for (unsigned int j = 0; j < nbJobs; ++j) {
    for (unsigned int m = 0; m < nbMachines; ++m) {
        tasks[j][m] = model.intervalVar(0, maxEnd);
    }
}

tasks = new HxExpression[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; ++j)
{
    for (int m = 0; m < nbMachines; ++m)
        tasks[j, m] = model.Interval(0, maxEnd);
}

tasks = new HxExpression[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; ++j) {
    for (int m = 0; m < nbMachines; ++m) {
        tasks[j][m] = model.intervalVar(0, maxEnd);
    }
}

For each activity, we use the length operator (returning the difference between the interval’s start and end times) to ensure that the corresponding interval has the right duration:

constraint length(tasks[j][m]) == processingTime[j][m];

model.constraint(model.length(tasks[j][m]) == processing_time[j][m])

model.constraint(model.length(tasks[j][m]) == processingTime[j][m]);

model.Constraint(model.Length(tasks[j, m]) == processingTime[j, m]);

model.constraint(model.eq(model.length(tasks[j][m]), processingTime[j][m]));

Then, we write the precedence constraints between the activities of each job: for each j and k, the activity in position k for job j needs to be scheduled before the activity in position k+1 for job j. The constant expression machineOrder[j][k], given as input data, corresponds to the index of the machine processing the activity in position k for job j. We use the < (lt) shortcut to ensure that the start time of the activity in position k+1 for job j is greater or equal to the end time of the activity in position k for job j:

constraint tasks[j][machineOrder[j][k]] < tasks[j][machineOrder[j][k + 1]];

model.constraint(tasks[j][machine_order[j][k]] < tasks[j][machine_order[j][k + 1]])

model.constraint(tasks[j][machineOrder[j][k]] < tasks[j][machineOrder[j][k + 1]]);

model.Constraint(tasks[j, machineOrder[j, k]] < tasks[j, machineOrder[j, k + 1]]);

model.constraint(model.lt(tasks[j][machineOrder[j][k]], tasks[j][machineOrder[j][k + 1]]));

In addition to the interval decisions representing the activities, we also use list decision variables, representing the ordering of activities on a machine. Indeed, a list decision of domain size n represents a subpermutation of {0, ..., n-1}, which makes it a very natural and intuitive way to represent an order.

Each machine processes one activity for each job. For each machine m, jobsOrder[m] represents the order of activities on machine m, meaning that jobsOrder[m][i] represents the index of the job corresponding to the activity in position i in machine m’s schedule:

jobsOrder[m in 0...nbMachines] <- list(nbJobs);

jobs_order = [model.list(nb_jobs) for m in range(nb_machines)]

for (int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbJobs);
}

jobsOrder = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m)
    jobsOrder[m] = model.List(nbJobs);

jobsOrder = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbJobs);
}

Then, we use the count operator to ensure that the index of every job is present in each list. Since the list decision represents a permutation, every element inside jobsOrder[m] is unique: ensuring that it contains n elements ensures that every job is scheduled exactly once on each machine:

constraint count(jobsOrder[m]) == nbJobs;

sequence = jobs_order[m]
model.constraint(model.eq(model.count(sequence), nb_jobs))

HxExpression sequence = jobsOrder[m];
model.constraint(model.eq(model.count(sequence), nbJobs));

HxExpression sequence = jobsOrder[m];
model.Constraint(model.Count(sequence) == nbJobs);

HxExpression sequence = jobsOrder[m];
model.constraint(model.eq(model.count(sequence), nbJobs));

The disjunctive resource constraints (each machine can only process one activity at a time) can be formulated as follows: for all i, the activity processed in position i+1 must start after the end of the activity processed in position i. To model these constraints, we pair up the interval decisions (the time ranges) with the list decisions (the job orderings): if jobsOrder[m][i] represents the index of the job in position i on machine m’s schedule, and tasks[j][m] represents the activity of job j that is processed by machine m, then tasks[jobsOrder[m][i]][m] represents the activity scheduled in position i in machine m’s schedule.

To enforce the non-overlap constraints, we write a lambda function expressing the relationship between two consecutive activities. This function is used within a variadic and operator over all activities processed by each machine, which can be seen as a “for all” expression. The constraint reads: “for all i between 0 and the number of jobs minus two, the activity scheduled in position i+1 on machine m starts after the end of the activity scheduled in position i on machine m”:

constraint and(0...nbJobs-1,
        i => tasks[jobsOrder[m][i]][m] < tasks[jobsOrder[m][i + 1]][m]);

sequence_lambda = model.lambda_function(
    lambda i: model.lt(model.at(task_array, sequence[i], m),
                       model.at(task_array, sequence[i + 1], m)))
model.constraint(model.and_(model.range(0, nb_jobs - 1), sequence_lambda))

HxExpression sequenceLambda = model.createLambdaFunction([&](HxExpression i) {
    return model.at(taskArray, sequence[i], m) < model.at(taskArray, sequence[i + 1], m);
});
model.constraint(model.and_(model.range(0, nbJobs - 1), sequenceLambda));

HxExpression sequenceLambda = model.LambdaFunction(
    i => taskArray[sequence[i], m] < taskArray[sequence[i + 1], m]
);
model.Constraint(model.And(model.Range(0, nbJobs - 1), sequenceLambda));

HxExpression mExpr = model.createConstant(m);
HxExpression sequenceLambda = model
        .lambdaFunction(i -> model.lt(model.at(taskArray, model.at(sequence, i), mExpr),
                model.at(taskArray, model.at(sequence, model.sum(i, 1)), mExpr)));
model.constraint(model.and(model.range(0, nbJobs - 1), sequenceLambda));

By using a list decision, we can make the formulation of the non-overlap constraints very compact: only O(n) for each machine (as opposed to O(n²) for pairwise disjunctive constraints).

The final step consists in defining the objective function. We define the makespan as the end time of the last activity to finish. Using the end operator, we can compute the makespan as the maximum end time among every job’s last activities. In the following code, makespan is not a decision variable but an intermediate expression: its value is directly computed from the values of the interval decisions and the input data. Then, we indicate that this expression is an objective function to minimize:

makespan <- max[j in 0...nbJobs] (end(tasks[j][machineOrder[j][nbMachines - 1]]));
minimize makespan;

makespan = model.max([model.end(tasks[j][machine_order[j][nb_machines - 1]])
                    for j in range(nb_jobs)])
model.minimize(makespan)

makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
    makespan.addOperand(model.end(tasks[j][machineOrder[j][nbMachines - 1]]));
}
model.minimize(makespan);

makespan = model.Max();
for (int j = 0; j < nbJobs; ++j)
    makespan.AddOperand(model.End(tasks[j, machineOrder[j, nbMachines - 1]]));
model.Minimize(makespan);

makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
    makespan.addOperand(model.end(tasks[j][machineOrder[j][nbMachines - 1]]));
}
model.minimize(makespan);

The complete Hexaly model for the Job Shop Scheduling Problem (JSSP) is then:

tasks[j in 0...nbJobs][m in 0...nbMachines] <- interval(0, maxEnd);

for [j in 0...nbJobs][m in 0...nbMachines]
    constraint length(tasks[j][m]) == processingTime[j][m];

for [j in 0...nbJobs][k in 0...nbMachines-1]
    constraint tasks[j][machineOrder[j][k]] < tasks[j][machineOrder[j][k + 1]];

jobsOrder[m in 0...nbMachines] <- list(nbJobs);

for [m in 0...nbMachines] {
    constraint count(jobsOrder[m]) == nbJobs;

    constraint and(0...nbJobs-1,
            i => tasks[jobsOrder[m][i]][m] < tasks[jobsOrder[m][i + 1]][m]);
}

makespan <- max[j in 0...nbJobs] (end(tasks[j][machineOrder[j][nbMachines - 1]]));
minimize makespan;

tasks = [[model.interval(0, max_end) for m in range(nb_machines)]
        for j in range(nb_jobs)]

for j in range(nb_jobs):
    for m in range(0, nb_machines):
        model.constraint(model.length(tasks[j][m]) == processing_time[j][m])

task_array = model.array(tasks)

for j in range(nb_jobs):
    for k in range(nb_machines - 1):
        model.constraint(
            tasks[j][machine_order[j][k]] < tasks[j][machine_order[j][k + 1]])

jobs_order = [model.list(nb_jobs) for m in range(nb_machines)]

for m in range(nb_machines):
    sequence = jobs_order[m]
    model.constraint(model.eq(model.count(sequence), nb_jobs))

    sequence_lambda = model.lambda_function(
        lambda i: model.lt(model.at(task_array, sequence[i], m),
                        model.at(task_array, sequence[i + 1], m)))
    model.constraint(model.and_(model.range(0, nb_jobs - 1), sequence_lambda))

makespan = model.max([model.end(tasks[j][machine_order[j][nb_machines - 1]])
                    for j in range(nb_jobs)])
model.minimize(makespan)

tasks.resize(nbJobs);
for (unsigned int j = 0; j < nbJobs; ++j) {
    tasks[j].resize(nbMachines);
    for (unsigned int m = 0; m < nbMachines; ++m) {
        tasks[j][m] = model.intervalVar(0, maxEnd);

        model.constraint(model.length(tasks[j][m]) == processingTime[j][m]);
    }
}

HxExpression taskArray = model.array();
for (int j = 0; j < nbJobs; ++j) {
    taskArray.addOperand(model.array(tasks[j].begin(), tasks[j].end()));
}

for (int j = 0; j < nbJobs; ++j) {
    for (int k = 0; k < nbMachines - 1; ++k) {
        model.constraint(tasks[j][machineOrder[j][k]] < tasks[j][machineOrder[j][k + 1]]);
    }
}

jobsOrder.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbJobs);
}

for (int m = 0; m < nbMachines; ++m) {
    HxExpression sequence = jobsOrder[m];
    model.constraint(model.eq(model.count(sequence), nbJobs));

    HxExpression sequenceLambda = model.createLambdaFunction([&](HxExpression i) {
        return model.at(taskArray, sequence[i], m) < model.at(taskArray, sequence[i + 1], m);
    });
    model.constraint(model.and_(model.range(0, nbJobs - 1), sequenceLambda));
}

makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
    makespan.addOperand(model.end(tasks[j][machineOrder[j][nbMachines - 1]]));
}
model.minimize(makespan);

tasks = new HxExpression[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; ++j)
{
    for (int m = 0; m < nbMachines; ++m)
    {
        tasks[j, m] = model.Interval(0, maxEnd);

        model.Constraint(model.Length(tasks[j, m]) == processingTime[j, m]);
    }
}

HxExpression taskArray = model.Array(tasks);

for (int j = 0; j < nbJobs; ++j)
{
    for (int k = 0; k < nbMachines - 1; ++k)
    {
        model.Constraint(tasks[j, machineOrder[j, k]] < tasks[j, machineOrder[j, k + 1]]);
    }
}

jobsOrder = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m)
    jobsOrder[m] = model.List(nbJobs);

for (int m = 0; m < nbMachines; ++m)
{
    HxExpression sequence = jobsOrder[m];
    model.Constraint(model.Count(sequence) == nbJobs);

    HxExpression sequenceLambda = model.LambdaFunction(
        i => taskArray[sequence[i], m] < taskArray[sequence[i + 1], m]
    );
    model.Constraint(model.And(model.Range(0, nbJobs - 1), sequenceLambda));
}

makespan = model.Max();
for (int j = 0; j < nbJobs; ++j)
    makespan.AddOperand(model.End(tasks[j, machineOrder[j, nbMachines - 1]]));
model.Minimize(makespan);

tasks = new HxExpression[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; ++j) {
    for (int m = 0; m < nbMachines; ++m) {
        tasks[j][m] = model.intervalVar(0, maxEnd);

        // Task duration constraints
        model.constraint(model.eq(model.length(tasks[j][m]), processingTime[j][m]));
    }
}

HxExpression taskArray = model.array(tasks);

for (int j = 0; j < nbJobs; ++j) {
    for (int k = 0; k < nbMachines - 1; ++k) {
        model.constraint(model.lt(tasks[j][machineOrder[j][k]], tasks[j][machineOrder[j][k + 1]]));
    }
}

jobsOrder = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbJobs);
}

for (int m = 0; m < nbMachines; ++m) {
    HxExpression sequence = jobsOrder[m];
    model.constraint(model.eq(model.count(sequence), nbJobs));

    HxExpression mExpr = model.createConstant(m);
    HxExpression sequenceLambda = model
            .lambdaFunction(i -> model.lt(model.at(taskArray, model.at(sequence, i), mExpr),
                    model.at(taskArray, model.at(sequence, model.sum(i, 1)), mExpr)));
    model.constraint(model.and(model.range(0, nbJobs - 1), sequenceLambda));
}

makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
    makespan.addOperand(model.end(tasks[j][machineOrder[j][nbMachines - 1]]));
}
model.minimize(makespan);

The whole code for solving the Job Shop Scheduling Problem (JSSP) with Hexaly, along with a few instances, is available as a code template, with an associated JSSP benchmark.

The Flexible Job Shop Problem (FJSP)

The Flexible Job Shop Problem (FJSP) is an extension of the Job Shop Scheduling Problem (JSSP) in which the assignment of activities to machines is flexible and not fixed in advance. Each activity has a set of compatible machines, and must be processed by one of them. The processing time of an activity depends on the machine processing it.

Like in the previous section, the Hexaly model for the Flexible Job Shop Problem (FJSP) uses interval decision variables to model the time span of the activities:

tasks[i in 0...nbTasks] <- interval(0, maxEnd);

tasks = [model.interval(0, max_end) for _ in range(nb_tasks)]

for (int i = 0; i < nbTasks; ++i)
    tasks[i] = model.intervalVar(0, maxEnd);

for (int i = 0; i < nbTasks; ++i)
    tasks[i] = model.Interval(0, maxEnd);

for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, maxEnd);
}

and list decision variables to model the order of activities on each machine:

jobsOrder[m in 0...nbMachines] <- list(nbTasks);

jobs_order = [model.list(nb_tasks) for _ in range(nb_machines)]
machines = model.array(jobs_order)

HxExpression machines = model.array();
for (unsigned int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbTasks);
    machines.addOperand(jobsOrder[m]);
}

jobsOrder = new HxExpression[nbMachines];
HxExpression machines = model.Array();
for (int m = 0; m < nbMachines; ++m)
{
    jobsOrder[m] = model.List(nbTasks);
    machines.AddOperand(jobsOrder[m]);
}

jobsOrder = new HxExpression[nbMachines];
HxExpression machines = model.array();
for (int m = 0; m < nbMachines; ++m) {
    jobsOrder[m] = model.listVar(nbTasks);
    machines.addOperand(jobsOrder[m]);
}

For each machine m, jobsOrder[m] is a list decision variable of domain size nbTasks (the total number of activities among all jobs) representing the activities scheduled on machine m: jobsOrder[m][i] is the index of the activity scheduled in position i on machine m.

All activities need to be assigned to exactly one machine. We use the partition operator to enforce this constraint:

constraint partition[m in 0...nbMachines](jobsOrder[m]);

model.constraint(model.partition(machines))

model.constraint(model.partition(machines));

model.Constraint(model.Partition(machines));

model.constraint(model.partition(machines));

The partition operator, when applied to a series of lists of domain size n, returns 1 if every element between 0 and n-1 is present in exactly one of the lists. Therefore, this constraint ensures that the index of each activity is present in exactly one of the lists, meaning that each activity is assigned to exactly one of the machines.

Not every activity can be assigned to every machine, and incompatibilities are identified via very large processing times. To enforce the incompatibility constraints, we use the contains operator to ensure that the index of an activity does not appear in the lists corresponding to incompatible machines:

for [i in 0...nbTasks][m in 0...nbMachines : taskProcessingTime[i][m] == INFINITE]
    constraint !contains(jobsOrder[m], i);

for i in range(nb_tasks):
    for m in range(nb_machines):
        if task_processing_time_data[i][m] == INFINITE:
            model.constraint(model.not_(model.contains(jobs_order[m], i)))

for (int i = 0; i < nbTasks; ++i) {
    for (unsigned int m = 0; m < nbMachines; ++m) {
        if (taskProcessingTimeData[i][m] == INFINITE) {
            model.constraint(!model.contains(jobsOrder[m], i));
        }
    }
}

for (int i = 0; i < nbTasks; ++i)
{
    for (int m = 0; m < nbMachines; ++m)
    {
        if (taskProcessingTimeData[i][m] == INFINITE)
            model.Constraint(!model.Contains(jobsOrder[m], i));
    }
}

for (int i = 0; i < nbTasks; ++i) {
    for (int m = 0; m < nbMachines; ++m) {
        if (taskProcessingTimeData[i][m] == INFINITE) {
            model.constraint(model.not(model.contains(jobsOrder[m], i)));
        }
    }
}

The processing time of an activity depends on the machine processing it. To enforce the duration constraints, we first need to retrieve the index of the machine processing each activity. For that, we use the find operator, which returns the position of the first list containing element i:

taskMachine[i in 0...nbTasks] <- find(jobsOrder, i);

task_machine = [model.find(machines, i) for i in range(nb_tasks)]

taskMachine[i] = model.find(machines, i);

taskMachine[i] = model.Find(machines, i);

taskMachine[i] = model.find(machines, i);

We can then write the duration constraints:

duration[i in 0...nbTasks] <- taskProcessingTime[i][taskMachine[i]];
for [i in 0...nbTasks]
    constraint length(tasks[i]) == duration[i];

duration = [model.at(task_processing_time, i, task_machine[i]) for i in range(nb_tasks)]
for i in range(nb_tasks):
    model.constraint(model.length(tasks[i]) == duration[i])

duration[i] = model.at(taskProcessingTime, i, taskMachine[i]);
model.constraint(model.length(tasks[i]) == duration[i]);

HxExpression iExpr = model.CreateConstant(i);
duration[i] = model.At(taskProcessingTime, iExpr, taskMachine[i]);
model.Constraint(model.Length(tasks[i]) == duration[i]);

HxExpression iExpr = model.createConstant(i);
duration[i] = model.at(taskProcessingTime, iExpr, taskMachine[i]);
model.constraint(model.eq(model.length(tasks[i]), duration[i]));

The non-overlap constraints are written in the same way as for the Job Shop Scheduling Problem (JSSP):

for [m in 0...nbMachines] {
    local sequence <- jobsOrder[m];
    constraint and(0...count(sequence)-1,
            i => tasks[sequence[i]] < tasks[sequence[i + 1]]);
}

sequence = jobs_order[m]
sequence_lambda = model.lambda_function(
    lambda i: task_array[sequence[i]] < task_array[sequence[i + 1]])
model.constraint(model.and_(model.range(0, model.count(sequence) - 1), sequence_lambda))

HxExpression sequence = jobsOrder[m];
HxExpression sequenceLambda = model.createLambdaFunction(
    [&](HxExpression i) { return taskArray[sequence[i]] < taskArray[sequence[i + 1]]; });
model.constraint(model.and_(model.range(0, model.count(sequence) - 1), sequenceLambda));

HxExpression sequence = jobsOrder[m];
HxExpression sequenceLambda = model.LambdaFunction(
    i => taskArray[sequence[i]] < taskArray[sequence[i + 1]]
);
model.Constraint(model.And(model.Range(0, model.Count(sequence) - 1), sequenceLambda));

HxExpression sequence = jobsOrder[m];
HxExpression sequenceLambda = model.lambdaFunction(i -> model
        .lt(model.at(taskArray, model.at(sequence, i)),
                model.at(taskArray, model.at(sequence, model.sum(i, 1)))));
model.constraint(model.and(model.range(0, model.sub(model.count(sequence), 1)), sequenceLambda));

The only difference is that the number of terms in the variadic and expressions varies during the search along with the size of the lists (number of activities assigned to each machine). This feature of Hexaly Optimizer’s modeling formalism is particularly powerful, since being able to apply n-ary operators to a variable number of terms can make the models much more compact, and lead to better performance overall on large instances.

The complete Hexaly model for the Flexible Job Shop Problem (FJSP), along with a few instances, is available as a code template, with an associated FJSP benchmark.

A very common extension of this problem consists in adding sequence-dependent setup times between each pair of consecutive tasks on each machine. In this case, we cannot use the < (lt) shortcut in the expression of the non-overlap constraints anymore, but the logic remains the same. The constraint reads: “for all i, the start time of the activity in position i+1 on machine m is greater or equal to the end time of the activity in position i plus the setup time between the activities in position i and i+1”:

for [m in 0...nbMachines] {
    local sequence <- jobsOrder[m];
    constraint and(0...count(sequence)-1, i =>
    start(tasks[sequence[i + 1]]) >= end(tasks[sequence[i]])
            + taskSetupTime[m][sequence[i]][sequence[i + 1]]);
}

sequence = jobs_order[m]
sequence_lambda = model.lambda_function(
    lambda i: model.start(task_array[sequence[i + 1]]) >= model.end(task_array[sequence[i]])
    + model.at(task_setup_time, m, sequence[i], sequence[i + 1]))
model.constraint(model.and_(model.range(0, model.count(sequence) - 1), sequence_lambda))

HxExpression sequence = jobsOrder[m];
HxExpression sequenceLambda = model.createLambdaFunction([&](HxExpression i) {
    return model.start(taskArray[sequence[i + 1]]) >=
           model.end(taskArray[sequence[i]]) + model.at(taskSetupTime, m, sequence[i], sequence[i + 1]);
});
model.constraint(model.and_(model.range(0, model.count(sequence) - 1), sequenceLambda));

HxExpression sequence = jobsOrder[m];
HxExpression mexpr = model.CreateConstant(m);
HxExpression sequenceLambda = model.LambdaFunction(
    i =>
        model.Start(taskArray[sequence[i + 1]])
        >= (model.End(taskArray[sequence[i]])
            + model.At(taskSetupTime, mexpr, sequence[i], sequence[i + 1])));
model.Constraint(model.And(model.Range(0, model.Count(sequence) - 1), sequenceLambda));

HxExpression sequence = jobsOrder[m];
HxExpression mExpr = model.createConstant(m);
HxExpression sequenceLambda = model
        .lambdaFunction(
                i -> model.geq(model.start(model.at(taskArray, model.at(sequence, model.sum(i, 1)))),
                        model.sum(model.end(model.at(taskArray, model.at(sequence, i))),
                                model.at(taskSetupTime, mExpr,
                                        model.at(sequence, i), model.at(sequence, model.sum(i, 1))))));
model.constraint(model.and(model.range(0, model.sub(model.count(sequence), 1)), sequenceLambda));

The complete Hexaly model for the Flexible Job Shop Problem with Sequence-Dependent Setup Times (FJSP-SDST), along with a few instances, is available as a code template.

The Resource-Constrained Project Scheduling Problem (RCPSP)

In the Resource-Constrained Project Scheduling Problem (RCPSP), a project consists of a set of tasks to schedule. Each task has a given duration and cannot be interrupted. There are precedence constraints between the tasks: each task must end before any of its successors can start. There is a set of renewable resources. Each task has a given resource requirement or weight (possibly zero) on each resource, representing the amount of resource it consumes while it is active. Each resource has a given maximum capacity: it can process several tasks at once, but the sum of the processed tasks’ weights can never exceed this maximum capacity. The goal is to find a schedule that minimizes the makespan: the time when all tasks have been processed.

Like in the previous sections, the Hexaly model for the Resource-Constrained Project Scheduling Problem (RCPSP) uses interval decision variables to model the tasks:

tasks[i in 0...nbTasks] <- interval(0, horizon);

tasks = [model.interval(0, horizon) for i in range(nb_tasks)]

for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}

tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i)
    tasks[i] = model.Interval(0, horizon);

tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i)
    tasks[i] = model.intervalVar(0, horizon);

The cumulative resource constraints can be rephrased as follows: “at any time, the sum of the weights of the tasks running on the resource must be less than the capacity of the resource”. We will now build the Hexaly expression corresponding to this constraint formulation step by step.

The first step is to check, for a given task i and time step t, whether task i is running at time t. For that, we use the contains operator to check whether t is contained within the interval’s bounds corresponding to task i:

contains(tasks[i], t)

model.contains(tasks[i], t)

model.contains(tasks[i], t)

model.Contains(tasks[i], t)

model.contains(tasks[i], t)

Then, we can loop over all the tasks to sum the weights of the tasks running at time t:

sum[i in 0...nbTasks](weight[i][r] * contains(tasks[i], t))

model.sum(weight[i][r] * model.contains(tasks[i], t) for i in range(nb_tasks))

HxExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    HxExpression taskWeight = weight[i][r] * model.contains(tasks[i], t);
    totalWeight.addOperand(taskWeight);
}

HxExpression totalWeight = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
    totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i], t));
}

HxExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    totalWeight.addOperand(model.prod(
            weight[i][r],
            model.contains(tasks[i], t)));
}

We can then compare this sum to the resource’s capacity:

sum[i in 0...nbTasks](weight[i][r] * contains(tasks[i], t)) <= capacity[r]

model.sum(weight[i][r] * model.contains(tasks[i], t) for i in range(nb_tasks)) <= capacity[r]

HxExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    HxExpression taskWeight = weight[i][r] * model.contains(tasks[i], t);
    totalWeight.addOperand(taskWeight);
}
HxExpression capacityRespected = model.leq(totalWeight, capacity[r]);

HxExpression totalWeight = model.Sum();
for (int i = 0; i < nbTasks; ++i)
{
    totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i], t));
}
HxExpression capacityRespected = totalWeight <= capacity[r];

HxExpression totalWeight = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    totalWeight.addOperand(model.prod(
            weight[i][r],
            model.contains(tasks[i], t)));
}
HxExpression capacityRespected = model.leq(totalWeight, capacity[r]);

Finally, we define a lambda function returning the above expression for any time t. Thanks to a variadic and operator looping over the time horizon, we can ensure that the resource capacity is respected at any time:

constraint and(0...makespan,
        t => sum[i in 0...nbTasks](weight[i][r] * contains(tasks[i], t)) <= capacity[r]);

capacity_respected = model.lambda_function(
    lambda t: model.sum(weight[i][r] * model.contains(tasks[i], t)
                        for i in range(nb_tasks))
    <= capacity[r])
model.constraint(model.and_(model.range(makespan), capacity_respected))

HxExpression capacityRespected = model.createLambdaFunction([&](HxExpression t) {
    HxExpression totalWeight = model.sum();
    for (int i = 0; i < nbTasks; ++i) {
        HxExpression taskWeight = weight[i][r] * model.contains(tasks[i], t);
        totalWeight.addOperand(taskWeight);
    }
    return model.leq(totalWeight, capacity[r]);
});
model.constraint(model.and_(model.range(0, makespan), capacityRespected));

HxExpression capacityRespected = model.LambdaFunction(t =>
    {
        HxExpression totalWeight = model.Sum();
        for (int i = 0; i < nbTasks; ++i)
        {
            totalWeight.AddOperand(weight[i, r] * model.Contains(tasks[i], t));
        }
        return totalWeight <= capacity[r];
    }
);
model.Constraint(model.And(model.Range(0, makespan), capacityRespected));

HxExpression capacityRespected = model.lambdaFunction(t -> {
    HxExpression totalWeight = model.sum();
    for (int i = 0; i < nbTasks; ++i) {
        totalWeight.addOperand(model.prod(
                weight[i][r],
                model.contains(tasks[i], t)));
    }
    return model.leq(totalWeight, capacity[r]);
});
model.constraint(model.and(model.range(0, makespan), capacityRespected));

Thanks to the variadic and operator, this formulation is very compact. Indeed, Hexaly does not “unroll” the constraint to split it into as many constraints as there are time steps in the time horizon. On the contrary, the compact formulation is used internally throughout the whole solving process, which helps the solver achieve very good performance on large instances of cumulative scheduling problems.

The complete Hexaly model for the Resource-Constrained Project Scheduling Problem (RCPSP), along with a few instances, is available as a code template, with an associated RCPSP benchmark.

Further reading: discover our code templates on scheduling problems

Calendar constraints

When considering calendar constraints, the intensity with which machines process tasks varies over time. In particular, an intensity of 0 means that the machine is off. At each time step, each ongoing activity’s progress increases by the current intensity of its machine. An activity starting at time t is considered completed once the sum of its machine’s intensity since time t reaches its processing time. In other words, a task is paused when the machine is turned off, and resumes when the machine is turned on again. Typical use cases include machines that must undergo maintenance at certain predefined times, or employee schedules with working hours and time off.

The complete Hexaly model for the Job Shop Scheduling Problem with Intensity, along with a few instances, is available as a code template.

Batch scheduling

In a batch scheduling problem, a set of tasks must be processed in batches on a set of available resources. Tasks within the same batch are processed together. Consequently, they must share a certain number of characteristics: same duration, same type, same resource type, …

The complete Hexaly model for the Batch Scheduling Problem, along with a few instances, is available as a code template.

Multiple modes

In a multi-mode scheduling problem, tasks can be performed according to several modes. Different modes for a task may result in different processing times, resource consumption, machine compatibility, etc. We must choose exactly one mode for each task. A typical use case is construction scheduling, where a task can be performed by a small crew over several days or by a larger crew in less time.

The complete Hexaly model for the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP), along with a few instances, is available as a code template.

Production and consumption of resources

Scheduling problems with production and consumption of resources involve inventory resources, which are consumed and/or produced by the tasks. The tasks consume a certain amount of each inventory resource when they start, and produce a certain amount when they end. Each inventory resource has an initial level, which then decreases whenever a task starts and consumes resources, and increases when a task ends and produces resources. The levels must stay between a given minimum level and a given maximum level.

The complete Hexaly model for the Project Scheduling Problem with Production and Consumption of Resources, along with a few instances, is available as a code template.

Other variants

Many other variants of scheduling problems (preemption, states, multiple machine groups, machine-dependent travel times, parallel machines, workforce scheduling, …) are available in our scheduling code templates.