Wednesday, June 12, 2019

Machine Scheduling

Here [1] is a problem with multiple machines:
  • 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



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

2 comments:

  1. 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!

    ReplyDelete