## Friday, May 8, 2020

### A scheduling problem

#### Problem Statement

The problem we are trying to solve here is a simple scheduling model [1]. But as we shall see, it has some interesting performance issues.

There are $$N$$ tasks (jobs) and $$M$$ rooms. We need to assign jobs to rooms where they are executed. We assume we execute one job at the time in each room (but jobs in different rooms can execute concurrently). Jobs require some resources (for example water tap, gas piping). Rooms provide certain resources. We need to make sure tasks are assigned to rooms that contain the resources that are needed. Finally, all jobs have a due date.

#### Data

Let's generate some data.

----     33 SET use  resource usage

resource1   resource2   resource3   resource4   resource5

----     33 SET avail  resource availability

resource1   resource2   resource3   resource4   resource5

room1                     YES         YES         YES         YES
room2                                 YES         YES
room3                                             YES         YES
room4         YES         YES         YES                     YES
room5         YES                     YES         YES         YES

----     33 PARAMETER length  job length

----     33 PARAMETER due  job due dates

We have 30 tasks, 5 rooms, and 5 resources. Note that some tasks don't need special resources (e.g. task1). They can execute in any room. Some jobs require resources that allow only one room. For instance, task9 needs resources 2 and 4. Only room1 provides this combination.

In the model, we actually don't need to know about resource usage. The only thing we need to know is whether job $$i$$ can be assigned to room $$j$$. So I calculated a set Allowed:

----     37 SET allowed  task is allowed to be executed in room

room1       room2       room3       room4       room5

task1          YES         YES         YES         YES         YES
task4          YES         YES         YES         YES         YES
task6          YES         YES         YES         YES         YES
task8          YES         YES         YES         YES         YES
task10         YES         YES         YES         YES         YES
task18         YES         YES         YES         YES         YES
task19         YES         YES         YES         YES         YES
task22         YES         YES         YES         YES         YES
task27         YES         YES         YES         YES         YES
task29         YES         YES         YES         YES         YES
task30         YES         YES         YES         YES         YES

#### Model 1

My first approach is to use no-overlap constraints for jobs that are assigned to the same room.

Mixed Integer Programming Model 1
\begin{align} \min\>&\color{darkred}{\mathit{Makespan}}\\ &\sum_{j|\color{darkblue}{\mathit{Allowed}}(i,j)} \color{darkred}{\mathit{Assign}}_{i,j} = 1 && \forall i \\ &\color{darkred}{\mathit{Finish}}_{i} = \color{darkred}{\mathit{Start}}_{i} + \color{darkblue}{\mathit{Length}}_{i} && \forall i \\ &\color{darkred}{\mathit{Start}}_{i} \ge \color{darkred}{\mathit{Finish}}_{i'} - \color{darkblue}M \cdot\color{darkred}\delta_{i,i',j} - \color{darkblue}M (1-\color{darkred}{\mathit{Assign}}_{i,j}) - \color{darkblue}M (1-\color{darkred}{\mathit{Assign}}_{i',j}) && \forall i \lt i',j | \color{darkblue}{\mathit{Allowed}}(i,j) \>\mathbf{and}\>\color{darkblue}{\mathit{Allowed}}(i',j)\\ &\color{darkred}{\mathit{Start}}_{i'} \ge \color{darkred}{\mathit{Finish}}_{i} - \color{darkblue}M (1-\color{darkred}\delta_{i,i',j}) - \color{darkblue}M (1-\color{darkred}{\mathit{Assign}}_{i,j}) - \color{darkblue}M (1-\color{darkred}{\mathit{Assign}}_{i',j}) &&\forall i \lt i',j | \color{darkblue}{\mathit{Allowed}}(i,j) \>\mathbf{and}\>\color{darkblue}{\mathit{Allowed}}(i',j) \\ &\color{darkred}{\mathit{Finish}}_i \le \color{darkblue}{\mathit{DueDate}}_{i} && \forall i\\ &\color{darkred}{\mathit{Makespan}} \ge \color{darkred}{\mathit{Finish}}_{i} && \forall i \\ & \color{darkred}{\mathit{Assign}}_{i,j} \in \{0,1\} \\ & \color{darkred}{\mathit{Start}}_{i},\color{darkred}{\mathit{Finish}}_{i} \ge 0\\ & \color{darkred}\delta_{i,i',j} \in \{0,1\} \end{align}

The no-overlap constraints say, if jobs $$i$$ and $$i'$$ execute in the same room $$j$$ then either $$i$$ has to execute before $$i'$$ or $$i'$$ has to execute before $$i$$. As usual, the big-M values are used to make constraints non-binding when they are not to be obeyed. For this problem, I simply used $$M=100$$.

This model does not perform very well at all. After an hour, I still saw a gap of 27% In addition, the number of constraints is large (given the small data set): 2,352.

We can improve on this formulation by observing that we don't need all variables $$\delta_{i,i',j}$$. Instead we can use  $$\delta_{i,i'}$$. This improves the performance a bit, but it is still not very good. This version is called "Improved Model 1" in the results table further down.

#### Model 2

Let's try a different model. First, we make sure all jobs are ordered by the due date. This means that we can find the finish time for job $$i$$ placed in room $$j$$ by calculating the processing time of all previous jobs assigned to room $$j$$: $\sum_{i'|i'\le i\>\mathbf{and} \mathit{Allowed}(i',j)} {\mathit{Length}}_{i'} \cdot {\mathit{Assign}}_{i',j}$ This means: we execute jobs assigned to a room back-to-back (no holes). Using this approach we can write:

Mixed Integer Programming Model 2
\begin{align} \min\>&\color{darkred}{\mathit{Makespan}}\\ &\color{darkred}{\mathit{Finish}}_{i} \ge \sum_{i'|i'\le i\> \mathbf{and}\>\color{darkblue}{\mathit{Allowed}}(i',j)} \color{darkblue}{\mathit{Length}}_{i'} \cdot \color{darkred}{\mathit{Assign}}_{i',j} - \color{darkblue}M (1-\color{darkred}{\mathit{Assign}}_{i,j})&& \forall i,j|\color{darkblue}{\mathit{Allowed}}(i,j)\\ &\color{darkred}{\mathit{Finish}}_i \le \color{darkblue}{\mathit{DueDate}}_{i} && \forall i\\ &\sum_{j|\color{darkblue}{\mathit{Allowed}}(i,j)} \color{darkred}{\mathit{Assign}}_{i,j} = 1 && \forall i \\ &\color{darkred}{\mathit{Makespan}} \ge \color{darkred}{\mathit{Finish}}_{i} && \forall i \\ & \color{darkred}{\mathit{Assign}}_{i,j} \in \{0,1\} \\ & \color{darkred}{\mathit{Finish}}_{i} \ge 0\\ \end{align}

Again we rely heavily on the set Allowed.

Note that in the finish constraint we repeat large parts of the summation in subsequent constraints. For large models, we may want to look into this (e.g. by adding extra variables and constraints to reduce the number of nonzero elements). In this case, I just left the constraint as specified in the mathematical model.

This model 2 turns out to be much faster:

Model 1Improved Model 1Model 2
Rows2,3522,352286
Columns1,283585137
Binary Columns1,222524106
Time>3,600>3,60024
StatusTime LimitTime LimitOptimal
Objective19.514219.435919.4322
Gap27%22%0%

The difference between models 1 and 2 is rather dramatic.

#### Solution

The solution values for the variables $$\mathit{Finish}_i$$ are not necessarily as small as possible. The objective does not push all job completion times down, only the ones involved with the total makespan (i.e. on the critical path). When reporting it makes sense just to take the optimal assignments from the model and then execute jobs as early as possible. This is what I did here. Jobs on a single line are ordered by the due date. The recalculated solution is:

----    129 PARAMETER results

start      length      finish     duedate

The highlighted completion time corresponds to the makespan.

#### Conclusion

This is a bit more interesting model than I initially thought.

The standard no-overlap constraints for a continuous-time model do not perform very well. In addition, they are a bit complicated due to several big-M terms (the constraints should only hold in certain specific cases: two jobs run in the same room).

By using the assumption that jobs in a single room are executed in order of the due date (not a bad assumption), we can create a much simpler MIP model that also performs much, much better.

When we have an infeasible solution (i.e. we cannot meet all due dates), we may want to deliver a good schedule that minimizes the damage. This is easy is we just add a slack variable to each due date constraint, and add the slack with a cost (penalty) to the objective. This essentially minimized the sum of the due date violations. There may be a reason to also look at minimizing the number of tardy jobs. It is noted that because we fixed the order of jobs in a single room, we may not get the best if we want to minimize the number of tardy jobs.

#### References

1. Allocating and scheduling tasks into rooms with conditions - optimization algorithm, https://stackoverflow.com/questions/61656492/allocating-and-scheduling-tasks-into-rooms-with-conditions-optimization-algori