- There are 3 machines and 4 jobs in this example
- Not all machines can do all jobs
- We have a few precedence constraints
- Given known processing times, find a schedule that minimizes the makespan (the time the last job is finished)
Assume the following data:
---- 63 --------------- data --- ---- 63 SET j jobs job1, job2, job3, job4 ---- 63 SET m machines machine1, machine2, machine3 ---- 63 SET ok allowed job/machine combinations machine1 machine2 machine3 job1 YES YES job2 YES YES job3 YES YES job4 YES ---- 63 PARAMETER proctime processing time job1 4.000, job2 2.000, job3 10.000, job4 12.000 ---- 63 SET prec precedence constraints job2 job4 job1 YES YES
There are many ways to model this. Some approaches can be:
- Discrete time using time slots. This leads to binary variables \[x_{j,m,t} = \begin{cases} 1 & \text{if job $j$ executes on machine $m$ at time $t$}\\ 0 & \text{otherwise}\end{cases}\]
- Continuous time with a binary variable indicating if job \(j_1\) is executed before job \(j_2\) (on the same machine)
- Continuous time with a binary variable indicating if job \(j_1\) immediately precedes job \(j_2\) (on the same machine)
Let's try the second approach. First we need a planning horizon. A simplistic way to find a planning horizon \(T\) is just to schedule each job after another: \[T = \sum_j \mathit{proctime}_j \] For our small data set, this gives:
---- 63 PARAMETER T = 28.000 max time
This \(T\) is used as a big-\(M\) constant, so we would like it to be as small as possible. For very large problems, we often use some heuristic to find an initial solution, and use this to set the planning horizon \(T\). If that is not possible, we may want to use indicator constraints, so we don't need any \(T\).
Decision Variables
We have two blocks of binary variables. One dealing with assigning jobs to machines and a second one about ordering of jobs on the same machine. The latter is handled by implementing no-overlap constraints. For this we need a binary variable indicating if job \(j_1\) is before or after job \(j_2\).
| Binary variables |
|---|
| \[\color{DarkRed}{\mathit{assign}}_{j,m} = \begin{cases} 1 & \text{if job $j$ is placed on machine $m$}\\ 0 & \text{otherwise}\end{cases}\] \[\color{DarkRed}{\mathit{after}}_{j_1,j_2} = \begin{cases} 1 & \text{if job $j_1$ is executed after job $j_2$ when placed on the same machine}\\ 0 & \text{if job $j_1$ is executed before job $j_2$ when placed on the same machine}\end{cases}\] |
Note that the variable \(\mathit{after}_{j_1,j_2}\) will be used only for \(j_1 \lt j_2\). This is to avoid double checking the same pair.
We also have a few continuous variables:
| Continuous variables |
|---|
| \[\begin{align} & \color{DarkRed}{\mathit{start}}_{j} \ge 0 && \text{start time of job $j$}\\ & \color{DarkRed}{\mathit{finish}}_{j} \ge 0 && \text{finish time of job $j$}\\ & \color{DarkRed}{\mathit{makespan}} \ge 0 && \text{last finish time} \end{align}\] |
Constraints
The model can look like:
| Mixed Integer Programming Model |
|---|
| \[\begin{align} \min\> & \color{DarkRed}{\mathit{makespan}} \\ & \color{DarkRed}{\mathit{makespan}} \ge \color{DarkRed}{\mathit{finish}}_j && \forall j \\ & \color{DarkRed}{\mathit{finish}}_j = \color{DarkRed}{\mathit{start}}_j + \color{DarkBlue}{\mathit{proctime}}_j && \forall j\\ & \sum_m \color{DarkRed}{\mathit{assign}}_{j,m} = 1 && \forall j\\ & \color{DarkRed}{\mathit{start}}_{j_1} \ge \color{DarkRed}{\mathit{finish}}_{j_2} - \color{DarkBlue}T (1-\color{DarkRed}{\mathit{after}}_{j_1,j_2}) - \color{DarkBlue}T (1-\color{DarkRed}{\mathit{assign}}_{j_1,m})- \color{DarkBlue}T (1-\color{DarkRed}{\mathit{assign}}_{j_2,m}) && \forall m, j_1 \lt j_2 \\ & \color{DarkRed}{\mathit{start}}_{j_2} \ge \color{DarkRed}{\mathit{finish}}_{j_1} - \color{DarkBlue}T \color{DarkRed}{\mathit{after}}_{j_1,j_2} - \color{DarkBlue}T (1-\color{DarkRed}{\mathit{assign}}_{j_1,m})- \color{DarkBlue}T (1-\color{DarkRed}{\mathit{assign}}_{j_2,m}) && \forall m, j_1 \lt j_2 \\ & \color{DarkRed}{\mathit{start}}_{j_2} \ge \color{DarkRed}{\mathit{finish}}_{j_1} && \forall \color{DarkBlue}{\mathit{prec}}_{j_1,j_2} \\ & \color{DarkRed}{\mathit{assign}}_{j,m} = 0 && \forall \text{ not } \color{DarkBlue}{\mathit{ok}}_{j,m} \end{align}\] |
The no-overlap constraints are the most complicated in this model. If the problem was a single machine scheduling problem, the no-overlap constraints would look like: \[\mathit{start}_{j_1} \ge \mathit{finish}_{j_2} \text{ or } \mathit{start}_{j_2} \ge \mathit{finish}_{j_1} \>\> \forall j_1 \lt j_2\] Note that we only need to compare jobs \(j_1 \lt j_2\) (each pair needs to be checked only once). The OR condition can be implemented using a binary variable, and big-\(M\) constraints: \[\begin{align} & \mathit{start}_{j_1} \ge \mathit{finish}_{j_2} - T (1-{\mathit{after}}_{j_1,j_2}) && \forall j_1 \lt j_2 \\ & \mathit{start}_{j_2} \ge \mathit{finish}_{j_1} - T {\mathit{after}}_{j_1,j_2} && \forall j_1 \lt j_2 \end{align}\] i.e. job \(j_1\) executes before or after job \(j_2\), but not in parallel. When we have multiple machines, we only want to keep this constraint active when jobs \(j_1\) and \(j_2\) are assigned to the same machine. That is: jobs are allowed to execute in parallel when they are on different machines. In a sense, we have built some nested big-\(M\) constraints.
Results
After running this model we get as results:
--------------- solution ----- ---- 66 VARIABLE assign.L assign job to machine machine1 machine2 machine3 job1 1.000 job2 1.000 job3 1.000 job4 1.000 ---- 66 VARIABLE start.L job start time job2 4.000, job4 4.000 ---- 66 VARIABLE finish.L job finish time job1 4.000, job2 6.000, job3 10.000, job4 16.000 ---- 66 VARIABLE makespan.L = 16.000 time last job is finished ---- 66 VARIABLE after.L j1 is scheduled after j2 on machine m job3 job1 1.000
How should we interpret the variable \(\mathit{after}\)? Only jobs 1 and 2 are on the same machine and for this combination we have \(\mathit{after}_{1,2}=0\). This means job1 is not after job2, and thus: job2 must be after job1. This is indeed what is happening. The values for \(\mathit{after}\) for jobs not on the same machine are basically just random: they are not used in active constraints. This means: the printed value \(\mathit{after}_{1,3}=1\) is not relevant as jobs 1 and 3 are on different machines.
Graphically this looks like:
We see that this solution obeys the precedence constraints (jobs 2 and 4 after job 1). Furthermore, it only assigns jobs to allowed machines (e.g. job 4 can only run on machine 3).
Larger data set
The above data set is very small. Such a data set is great during development. A beginners mistake I often see is using a large data set during model development. It is much more convenient and efficient using a very small data set when things are in flux, and you do many runs just to get the model right.
Now, it is important to see how the model behaves with a large data set. I used random data with 8 machines and 50 jobs. For this problem we only needed a few seconds to solve to guaranteed optimality. The model had about 20k constraints, 1,700 variables (of which 1,400 binary variables).
 |
| solution of 8 machine, 50 job problem with random data |
The performance seems to be quite reasonable. The main problem is that for large models the number of constraints becomes big, and the big-\(M\) constraints may not be as tight as we want. But for a first formulation, not so bad.
References
- Multiprocessor scheduling with job exclusions and precedence constraints, https://stackoverflow.com/questions/56546290/multiprocessor-scheduling-with-job-exclusions-and-precedence-constraints
Appendix: large data set
---- 64 --------------- data --- ---- 64 SET j jobs job1 , job2 , job3 , job4 , job5 , job6 , job7 , job8 , job9 , job10, job11, job12 job13, job14, job15, job16, job17, job18, job19, job20, job21, job22, job23, job24 job25, job26, job27, job28, job29, job30, job31, job32, job33, job34, job35, job36 job37, job38, job39, job40, job41, job42, job43, job44, job45, job46, job47, job48 job49, job50 ---- 64 SET m machines machine1, machine2, machine3, machine4, machine5, machine6, machine7, machine8 ---- 64 SET ok allowed job/machine combinations machine1 machine2 machine3 machine4 machine5 machine6 machine7 machine8 job1 YES YES YES YES YES job2 YES YES job3 YES YES YES YES YES YES job4 YES YES YES job5 YES YES YES job6 YES YES YES YES YES job7 YES YES YES YES job8 YES YES YES job9 YES YES YES YES YES YES job10 YES YES YES YES YES job11 YES YES YES YES YES YES YES job12 YES YES YES YES job13 YES YES YES YES job14 YES YES YES YES YES job15 YES YES YES YES YES YES job16 YES YES YES YES YES YES job17 YES job18 YES YES YES job19 YES YES YES YES YES job20 YES YES YES YES job21 YES YES YES YES job22 YES YES job23 YES YES YES YES YES YES job24 YES YES YES YES job25 YES YES YES job26 YES YES YES job27 YES YES YES job28 YES YES YES job29 YES YES job30 YES job31 YES YES YES YES job32 YES YES job33 YES YES YES YES YES job34 YES YES YES job35 YES YES YES YES job36 YES YES YES job37 YES YES YES job38 YES YES job39 YES YES YES YES job40 YES YES job41 YES YES YES job42 YES YES YES job43 YES YES YES YES YES job44 YES YES YES job45 YES YES YES YES YES job46 YES YES YES YES job47 YES YES YES YES YES job48 YES YES job49 YES YES YES YES job50 YES ---- 64 PARAMETER proctime job1 7.000, job2 6.000, job3 3.000, job4 3.000, job5 6.000, job6 3.000, job7 10.000 job8 1.000, job9 7.000, job10 3.000, job11 7.000, job12 9.000, job13 2.000, job14 3.000 job15 9.000, job16 10.000, job17 2.000, job18 4.000, job19 4.000, job20 8.000, job21 10.000 job22 6.000, job23 5.000, job24 7.000, job25 1.000, job26 6.000, job27 10.000, job28 7.000 job29 7.000, job30 5.000, job31 6.000, job32 10.000, job33 9.000, job34 5.000, job35 6.000 job36 7.000, job37 4.000, job38 9.000, job39 2.000, job40 5.000, job41 7.000, job42 7.000 job43 7.000, job44 6.000, job45 4.000, job46 4.000, job47 3.000, job48 9.000, job49 9.000 job50 5.000 ---- 64 SET prec precedence constraints job5 job7 job12 job15 job17 job18 job19 job20 job21 job1 YES job2 YES YES job4 YES job6 YES job9 YES YES job10 YES job11 YES YES job12 YES job14 YES job15 YES job16 YES + job22 job23 job24 job25 job26 job27 job28 job29 job30 job2 YES YES job4 YES YES job6 YES job8 YES job10 YES YES YES job14 YES job16 YES job17 YES YES job18 YES job21 YES YES job23 YES job24 YES YES YES job26 YES job27 YES job29 YES + job31 job32 job33 job34 job35 job36 job37 job38 job39 job2 YES YES job3 YES job4 YES job5 YES job6 YES YES YES job7 YES job8 YES job9 YES job12 YES YES job14 YES YES job15 YES YES job17 YES YES YES job18 YES YES YES job19 YES YES YES job20 YES job21 YES job22 YES YES YES job23 YES job25 YES job26 YES YES job27 YES job30 YES job31 YES YES job32 YES + job40 job41 job42 job43 job44 job45 job46 job47 job48 job1 YES YES job2 YES job3 YES YES YES job4 YES YES job5 YES YES job6 YES job7 YES YES job8 YES job9 YES job10 YES job11 YES YES job12 YES job13 YES job14 YES YES job15 YES job17 YES job20 YES job21 YES job22 YES job23 YES job24 YES YES job26 YES YES job27 YES job28 YES job30 YES job32 YES YES job33 YES job34 YES YES job35 YES job37 YES job38 YES YES job41 YES job42 YES YES job47 YES + job49 job50 job3 YES job4 YES job6 YES job13 YES job14 YES job19 YES job23 YES job27 YES job31 YES job35 YES job42 YES job45 YES ---- 64 PARAMETER T = 295.000 max time --------------- solution ----- ---- 64 VARIABLE assign.L assign job to machine machine1 machine2 machine3 machine4 machine5 machine6 machine7 machine8 job1 1.000 job2 1.000 job3 1.000 job4 1.000 job5 1.000 job6 1.000 job7 1.000 job8 1.000 job9 1.000 job10 1.000 job11 1.000 job12 1.000 job13 1.000 job14 1.000 job15 1.000 job16 1.000 job17 1.000 job18 1.000 job19 1.000 job20 1.000 job21 1.000 job22 1.000 job23 1.000 job24 1.000 job25 1.000 job26 1.000 job27 1.000 job28 1.000 job29 1.000 job30 1.000 job31 1.000 job32 1.000 job33 1.000 job34 1.000 job35 1.000 job36 1.000 job37 1.000 job38 1.000 job39 1.000 job40 1.000 job41 1.000 job42 1.000 job43 1.000 job44 1.000 job45 1.000 job46 1.000 job47 1.000 job48 1.000 job49 1.000 job50 1.000 ---- 64 VARIABLE start.L job start time job5 7.000, job7 22.000, job8 3.000, job9 7.000, job10 14.000, job12 7.000, job13 3.000 job14 3.000, job15 7.000, job16 6.000, job17 7.000, job18 16.000, job19 17.000, job20 16.000 job21 16.000, job22 32.000, job23 29.000, job24 17.000, job25 21.000, job26 24.000, job27 26.000 job28 41.000, job29 24.000, job30 31.000, job31 16.000, job32 22.000, job33 32.000, job34 24.000 job35 36.000, job36 38.000, job37 48.000, job38 38.000, job39 38.000, job40 47.000, job41 42.000 job42 26.000, job43 47.000, job44 52.000, job45 36.000, job46 54.000, job47 38.000, job48 49.000 job49 40.000, job50 49.000 ---- 64 VARIABLE finish.L job finish time job1 7.000, job2 6.000, job3 3.000, job4 3.000, job5 13.000, job6 3.000, job7 32.000 job8 4.000, job9 14.000, job10 17.000, job11 7.000, job12 16.000, job13 5.000, job14 6.000 job15 16.000, job16 16.000, job17 9.000, job18 20.000, job19 21.000, job20 24.000, job21 26.000 job22 38.000, job23 34.000, job24 24.000, job25 22.000, job26 30.000, job27 36.000, job28 48.000 job29 31.000, job30 36.000, job31 22.000, job32 32.000, job33 41.000, job34 29.000, job35 42.000 job36 45.000, job37 52.000, job38 47.000, job39 40.000, job40 52.000, job41 49.000, job42 33.000 job43 54.000, job44 58.000, job45 40.000, job46 58.000, job47 41.000, job48 58.000, job49 49.000 job50 54.000 ---- 64 VARIABLE makespan.L = 58.000 time last job is finished ---- 64 VARIABLE after.L j1 is scheduled after j2 on machine m job3 job9 job10 job11 job12 job13 job14 job15 job16 job1 1.000 job3 1.000 1.000 1.000 job5 1.000 1.000 1.000 job7 1.000 1.000 job9 1.000 1.000 job10 1.000 job12 1.000 1.000 job15 1.000 + job24 job25 job26 job29 job30 job31 job33 job34 job35 job7 1.000 job20 1.000 job22 1.000 1.000 1.000 1.000 job23 1.000 1.000 1.000 job24 1.000 job27 1.000 1.000 job28 1.000 1.000 1.000 1.000 1.000 + job41 job42 job45 job46 job47 job48 job49 job50 job22 1.000 job28 1.000 1.000 1.000 job33 1.000 1.000 job35 1.000 1.000 job37 1.000 job39 1.000 job40 1.000 1.000 job41 1.000 1.000 job43 1.000 1.000 1.000 1.000 job44 1.000 job46 1.000 1.000
Hallo Erwin, would it be possible to get the larger data set you have used here? I implemented the model in Pyomo/CBC and would like to check results against yours. I appreciate the quality of your articles, indeed! Thanks!
ReplyDeleteAdded the large data set.
Delete