sysid blog

Task Scheduling with limited Resources

May 24, 2020 ☕️ 4 min read

We already looked at a simple scheduling problem: Task Scheduling.

Here we are looking at a more elaborated scheduling example with limited resources for tasks with various durations. We want to get insights by re-engineering the solution of 1 with Pyomo.

Problem

  • We have NN tasks and MM facilities to execute the tasks.
  • Every task has a due date.
  • Tasks require certain resources for execution, e.g. water, electricity, …
  • Every facility provides a set of resources
  • Only one task per resource can be executed at a given time.

Assign the tasks to the facilities so that the task get all required resources for execution. We want to minimize the total time to complete all tasks. This time is called makespan.

One challenge is the no-overlap constraint for tasks. We will make use of our meanwhile well-known datastructure. It encodes business logic for formulating the non-overlap constraint. If you need a primer on this important concept, please refer to 2.

For experimentation I am using sample data from 1 in order to have a result benchmark. We have 30 tasks:

'resource_usage': {
    1: [0, 0, 0, 0, 0],
        ...
    9: [0, 1, 0, 1, 0],
    29: [0, 0, 0, 0, 0],
        ...
    30: [0, 0, 0, 0, 0],
}

There are 5 facilities and 5 different resource types. Note that some tasks don’t need special resources (e.g. task1).

'resource_availability': {
    1: [0, 1, 1, 1, 1],
    2: [0, 0, 1, 1, 0],
    3: [0, 0, 0, 1, 1],
    4: [1, 1, 1, 0, 1],
    5: [1, 0, 1, 1, 1],
}

Note that some tasks don’t need special resources (e.g. task1). They can execute in any facility. Some jobs require resources that allow only one facility. For instance, task9 needs resources 2 and 4. Only facility 1 provides this combination.

Model

We focus on the better performing approach from 1. For comparison of performance of two solution approaches please check there.

Variables

xij={1,  task i is assigned to room j 0,  else MakespanR+finishR+x_{ij} = \begin{cases} 1, \ \text{ task i is assigned to room j }\\ 0, \ \text{ else }\\ \end{cases}\\ \mathit{Makespan} \in R^+\\ \mathit{finish} \in R^+\\

Parameters

DueDatei  task du date lengthi,  task duration okij={1,  task i is allowed in room j 0,  else \mathit{DueDate}_i \ \text{ task du date }\\ length_i, \ \text{ task duration }\\ ok_{ij} = \begin{cases} 1, \ \text{ task i is allowed in room j }\\ 0, \ \text{ else }\\ \end{cases}\\

Objective

minMakespan\min \mathit{Makespan}\\

Constraints

The finish time for task ii placed in facility jj can be calculated as the sum of the processing time of all previous jobs assignted to jj. We allocate jobs to a facility back-to-back (no holes):

iiiok(i,j)lengthixi,j\sum_{i'|i'\le i \land ok(i',j)} length_{i'} x_{i', j}\\finishiiiiok(i,j) lengthixi,jM(1xi,j), i,jok(i,j)finish_i \ge \sum_{i'|i'\le i \land ok(i',j)} \ length_{i'} x_{i', j} - M(1-x_{i,j}), \ \forall{i,j|ok(i,j)}\\finishiDueDateifinish_i \le \mathit{DueDate}_i\\finishi0finish_i \ge 0\\jok(i,j)xi,j=1, i\sum_{j|ok(i,j)} x_{i,j} = 1, \ \forall i\\Makespanfinishi\mathit{Makespan} \ge finish_i\\

MM has been set to 100.

Implementation

By using the bespoke index oki,jok_{i,j} the Pyomo formulation of the constraints are compact:

def all_jobs_assigned_c(model, i):
    return sum(model.x[ii, jj] for (ii, jj) in model.ok if ii == i) == 1
model.all_jobs_assigned_c = Constraint(model.I, rule=all_jobs_assigned_c)

def finish1_c(model, i, j):
    return sum(
        model.length[ii] * model.x[ii, jj] for (ii, jj) in model.ok if jj == j and ii <= i
    ) - M * (1 - model.x[i, j]) <= model.finish[i]
model.finish1_c = Constraint(model.I, model.J, rule=finish1_c)

The rest of the model is straightforward. Some effort is only needed for visualization of the result.

Results

Solving the model with the given parameters is easy:

  • Optimal solution: 19.432

  • Number of constraints : 240

  • Number of variables : 181

  • Duration: 00:02:31

          1: [1, 9, 11, 20, 23, 30],
          2: [6, 10, 15, 24, 29],
          3: [2, 8, 18, 22, 27, 28],
          4: [3, 4, 13, 17, 21, 25],
          5: [5, 7, 12, 14, 16, 19, 26]
           

Visualization

schedule

Summary

We have seen (again) that using bespoke index sets which encode business rules help, expressing constraints and make models easier to formulate and to solve.

Calculating these binary datastructures comes down to applying sound software engineering practice, so they can be tested and debugged with known tools of the trade. This is easier and less error-prone than trying to find errors in constraint equations.


always be building, by sysid.

© 2022