Assigning jobs to machines without overlap

 Here we consider the following problem from [1]:

• We have jobs with a given start time and completion time
• Jobs can be repeated on given days (e.g. job 1 needs to run on Monday, Wednesday, and Friday)
• We want to assign jobs to machines in such a way that there is no overlap
• The objective is to minimize the number of machines needed to execute all jobs

The planning horizon is a week, and the problems has 50 jobs.

The tables in this post are a bit long. That is because I wanted to work with 50 jobs (which can be repeated several days). This makes the problem a little bit large but also more realistic in size. 

We don't have data for this problem, so the first thing to do is to see if we can invent some. I generated randomly:

----     49 PARAMETER start  start time (minutes since midnight)

job1   206,    job2  1012,    job3   661,    job4   361,    job5   350,    job6   269,    job7   420,    job8  1028,    job9    80
job10  600,    job11 1198,    job12  695,    job13 1190,    job14  915,    job15  156,    job16  768,    job17  191,    job18  300
job19  803,    job20  522,    job21  432,    job22  422,    job23  157,    job24  180,    job25  707,    job26  997,    job27  277
job28  799,    job29  931,    job30  364,    job31  132,    job32  603,    job33  192,    job34 1047,    job35  318,    job36  343
job37  713,    job38  867,    job39  754,    job40  557,    job41  496,    job42  141,    job43  377,    job44   55,    job45  406
job46  218,    job47  775,    job48  673,    job49  924,    job50  357


----     49 PARAMETER end  finish time (minutes since midnight)

job1   842,    job2  1722,    job3  1271,    job4   702,    job5   537,    job6   469,    job7  1040,    job8  1573,    job9   224
job10 1338,    job11 1374,    job12  952,    job13 1720,    job14 1620,    job15  415,    job16  914,    job17  767,    job18  905
job19 1227,    job20  922,    job21  741,    job22  734,    job23  378,    job24 1029,    job25 1123,    job26 1728,    job27  631
job28 1017,    job29 1635,    job30  538,    job31  409,    job32  726,    job33  522,    job34 1557,    job35  556,    job36  599
job37 1091,    job38 1234,    job39 1125,    job40 1429,    job41 1392,    job42  549,    job43  788,    job44  777,    job45  835
job46 1051,    job47  988,    job48 1367,    job49 1087,    job50  927


----     49 PARAMETER length  length of job (minutes)

job1  636,    job2  710,    job3  610,    job4  341,    job5  187,    job6  200,    job7  620,    job8  545,    job9  144
job10 738,    job11 176,    job12 257,    job13 530,    job14 705,    job15 259,    job16 146,    job17 576,    job18 605
job19 424,    job20 400,    job21 309,    job22 312,    job23 221,    job24 849,    job25 416,    job26 731,    job27 354
job28 218,    job29 704,    job30 174,    job31 277,    job32 123,    job33 330,    job34 510,    job35 238,    job36 256
job37 378,    job38 367,    job39 371,    job40 872,    job41 896,    job42 408,    job43 411,    job44 722,    job45 429
job46 833,    job47 213,    job48 694,    job49 163,    job50 570


----     49 SET jd  jobs need to run on certain days

             day1        day2        day3        day4        day5        day6        day7

job1          YES         YES                                             YES         YES
job2                      YES                     YES         YES
job3                      YES         YES                     YES                     YES
job4                                  YES         YES                                 YES
job5                                  YES
job6                      YES                                 YES                     YES
job7          YES                                 YES                     YES         YES
job8                                  YES         YES                     YES
job9                      YES         YES
job10         YES         YES         YES                     YES                     YES
job11                                             YES         YES
job12                     YES         YES         YES         YES         YES         YES
job13                                 YES         YES
job14                     YES         YES
job15                                             YES         YES
job16                                             YES                                 YES
job17         YES                                             YES
job18                     YES         YES
job19         YES                                                                     YES
job20                                 YES
job21                     YES         YES                     YES                     YES
job22         YES                                 YES                     YES
job23                                 YES         YES                     YES
job24                     YES         YES                                 YES
job25                                 YES                     YES
job26         YES                     YES                     YES
job27         YES                                 YES         YES
job28         YES                                             YES
job29                                             YES
job30         YES                                             YES         YES
job31         YES                     YES
job32                     YES                                 YES         YES
job33         YES                     YES                                 YES         YES
job34         YES         YES                                             YES         YES
job35                     YES                     YES                     YES
job36                     YES         YES                                             YES
job37         YES                                 YES         YES
job38         YES                     YES                     YES
job39                                             YES         YES                     YES
job40         YES         YES                                                         YES
job41                                                                     YES
job42         YES                                 YES                     YES
job43                                                         YES
job44         YES                     YES
job45                                 YES                     YES
job46                     YES                                                         YES
job47                                                                                 YES
job48                                             YES         YES
job49                                 YES                     YES                     YES
job50                                             YES


----     49 PARAMETER counts  jobs and individual subjob counts

jobs     50,    subjobs 131

The times are in minutes since the start of the day (0:00). The number of jobs is 50, but as jobs repeat on several days, the total number of subjobs is 131. 

Instead of dealing with jobs and days, it may be easier to just use the 131 subjobs. This makes indexing easier (one index: subjob number instead of two: job id and day). This kind of mapping between two representations is quite helpful. We see this quite often in models as it can simplify things tremendously. We just need to translate back to the original space at the end, so the user of the model can interpret the results. For this, we set up a mapping set:

----     68 SET map  mapping between jobs/days and subjobs

job1 .day1.subjob1  ,    job1 .day2.subjob2  ,    job1 .day6.subjob3  ,    job1 .day7.subjob4  ,    job2 .day2.subjob5  
job2 .day4.subjob6  ,    job2 .day5.subjob7  ,    job3 .day2.subjob8  ,    job3 .day3.subjob9  ,    job3 .day5.subjob10 
job3 .day7.subjob11 ,    job4 .day3.subjob12 ,    job4 .day4.subjob13 ,    job4 .day7.subjob14 ,    job5 .day3.subjob15 
job6 .day2.subjob16 ,    job6 .day5.subjob17 ,    job6 .day7.subjob18 ,    job7 .day1.subjob19 ,    job7 .day4.subjob20 
job7 .day6.subjob21 ,    job7 .day7.subjob22 ,    job8 .day3.subjob23 ,    job8 .day4.subjob24 ,    job8 .day6.subjob25 
job9 .day2.subjob26 ,    job9 .day3.subjob27 ,    job10.day1.subjob28 ,    job10.day2.subjob29 ,    job10.day3.subjob30 
job10.day5.subjob31 ,    job10.day7.subjob32 ,    job11.day4.subjob33 ,    job11.day5.subjob34 ,    job12.day2.subjob35 
job12.day3.subjob36 ,    job12.day4.subjob37 ,    job12.day5.subjob38 ,    job12.day6.subjob39 ,    job12.day7.subjob40 
job13.day3.subjob41 ,    job13.day4.subjob42 ,    job14.day2.subjob43 ,    job14.day3.subjob44 ,    job15.day4.subjob45 
job15.day5.subjob46 ,    job16.day4.subjob47 ,    job16.day7.subjob48 ,    job17.day1.subjob49 ,    job17.day5.subjob50 
job18.day2.subjob51 ,    job18.day3.subjob52 ,    job19.day1.subjob53 ,    job19.day7.subjob54 ,    job20.day3.subjob55 
job21.day2.subjob56 ,    job21.day3.subjob57 ,    job21.day5.subjob58 ,    job21.day7.subjob59 ,    job22.day1.subjob60 
job22.day4.subjob61 ,    job22.day6.subjob62 ,    job23.day3.subjob63 ,    job23.day4.subjob64 ,    job23.day6.subjob65 
job24.day2.subjob66 ,    job24.day3.subjob67 ,    job24.day6.subjob68 ,    job25.day3.subjob69 ,    job25.day5.subjob70 
job26.day1.subjob71 ,    job26.day3.subjob72 ,    job26.day5.subjob73 ,    job27.day1.subjob74 ,    job27.day4.subjob75 
job27.day5.subjob76 ,    job28.day1.subjob77 ,    job28.day5.subjob78 ,    job29.day4.subjob79 ,    job30.day1.subjob80 
job30.day5.subjob81 ,    job30.day6.subjob82 ,    job31.day1.subjob83 ,    job31.day3.subjob84 ,    job32.day2.subjob85 
job32.day5.subjob86 ,    job32.day6.subjob87 ,    job33.day1.subjob88 ,    job33.day3.subjob89 ,    job33.day6.subjob90 
job33.day7.subjob91 ,    job34.day1.subjob92 ,    job34.day2.subjob93 ,    job34.day6.subjob94 ,    job34.day7.subjob95 
job35.day2.subjob96 ,    job35.day4.subjob97 ,    job35.day6.subjob98 ,    job36.day2.subjob99 ,    job36.day3.subjob100
job36.day7.subjob101,    job37.day1.subjob102,    job37.day4.subjob103,    job37.day5.subjob104,    job38.day1.subjob105
job38.day3.subjob106,    job38.day5.subjob107,    job39.day4.subjob108,    job39.day5.subjob109,    job39.day7.subjob110
job40.day1.subjob111,    job40.day2.subjob112,    job40.day7.subjob113,    job41.day6.subjob114,    job42.day1.subjob115
job42.day4.subjob116,    job42.day6.subjob117,    job43.day5.subjob118,    job44.day1.subjob119,    job44.day3.subjob120
job45.day3.subjob121,    job45.day5.subjob122,    job46.day2.subjob123,    job46.day7.subjob124,    job47.day7.subjob125
job48.day4.subjob126,    job48.day5.subjob127,    job49.day3.subjob128,    job49.day5.subjob129,    job49.day7.subjob130
job50.day4.subjob131

This mapping set allows us to map back and forth between jobs/days and subjobs. Here we see that job 1 executes on days 1, 2, 6, and 7. It is mapped to subjobs 1,2,3,4. As we lose the day index, we calculate the start and end time of subjobs in minutes since the start of the week:

 

----     88 PARAMETER start2  start time of subjob (minutes since start of week)

subjob1    206,    subjob2   1646,    subjob3   7406,    subjob4   8846,    subjob5   2452,    subjob6   5332,    subjob7   6772
subjob8   2101,    subjob9   3541,    subjob10  6421,    subjob11  9301,    subjob12  3241,    subjob13  4681,    subjob14  9001
subjob15  3230,    subjob16  1709,    subjob17  6029,    subjob18  8909,    subjob19   420,    subjob20  4740,    subjob21  7620
subjob22  9060,    subjob23  3908,    subjob24  5348,    subjob25  8228,    subjob26  1520,    subjob27  2960,    subjob28   600
subjob29  2040,    subjob30  3480,    subjob31  6360,    subjob32  9240,    subjob33  5518,    subjob34  6958,    subjob35  2135
subjob36  3575,    subjob37  5015,    subjob38  6455,    subjob39  7895,    subjob40  9335,    subjob41  4070,    subjob42  5510
subjob43  2355,    subjob44  3795,    subjob45  4476,    subjob46  5916,    subjob47  5088,    subjob48  9408,    subjob49   191
subjob50  5951,    subjob51  1740,    subjob52  3180,    subjob53   803,    subjob54  9443,    subjob55  3402,    subjob56  1872
subjob57  3312,    subjob58  6192,    subjob59  9072,    subjob60   422,    subjob61  4742,    subjob62  7622,    subjob63  3037
subjob64  4477,    subjob65  7357,    subjob66  1620,    subjob67  3060,    subjob68  7380,    subjob69  3587,    subjob70  6467
subjob71   997,    subjob72  3877,    subjob73  6757,    subjob74   277,    subjob75  4597,    subjob76  6037,    subjob77   799
subjob78  6559,    subjob79  5251,    subjob80   364,    subjob81  6124,    subjob82  7564,    subjob83   132,    subjob84  3012
subjob85  2043,    subjob86  6363,    subjob87  7803,    subjob88   192,    subjob89  3072,    subjob90  7392,    subjob91  8832
subjob92  1047,    subjob93  2487,    subjob94  8247,    subjob95  9687,    subjob96  1758,    subjob97  4638,    subjob98  7518
subjob99  1783,    subjob100 3223,    subjob101 8983,    subjob102  713,    subjob103 5033,    subjob104 6473,    subjob105  867
subjob106 3747,    subjob107 6627,    subjob108 5074,    subjob109 6514,    subjob110 9394,    subjob111  557,    subjob112 1997
subjob113 9197,    subjob114 7696,    subjob115  141,    subjob116 4461,    subjob117 7341,    subjob118 6137,    subjob119   55
subjob120 2935,    subjob121 3286,    subjob122 6166,    subjob123 1658,    subjob124 8858,    subjob125 9415,    subjob126 4993
subjob127 6433,    subjob128 3804,    subjob129 6684,    subjob130 9564,    subjob131 4677


----     88 PARAMETER end2  end time of subjob (minutes since start of week)

subjob1     842,    subjob2    2282,    subjob3    8042,    subjob4    9482,    subjob5    3162,    subjob6    6042
subjob7    7482,    subjob8    2711,    subjob9    4151,    subjob10   7031,    subjob11   9911,    subjob12   3582
subjob13   5022,    subjob14   9342,    subjob15   3417,    subjob16   1909,    subjob17   6229,    subjob18   9109
subjob19   1040,    subjob20   5360,    subjob21   8240,    subjob22   9680,    subjob23   4453,    subjob24   5893
subjob25   8773,    subjob26   1664,    subjob27   3104,    subjob28   1338,    subjob29   2778,    subjob30   4218
subjob31   7098,    subjob32   9978,    subjob33   5694,    subjob34   7134,    subjob35   2392,    subjob36   3832
subjob37   5272,    subjob38   6712,    subjob39   8152,    subjob40   9592,    subjob41   4600,    subjob42   6040
subjob43   3060,    subjob44   4500,    subjob45   4735,    subjob46   6175,    subjob47   5234,    subjob48   9554
subjob49    767,    subjob50   6527,    subjob51   2345,    subjob52   3785,    subjob53   1227,    subjob54   9867
subjob55   3802,    subjob56   2181,    subjob57   3621,    subjob58   6501,    subjob59   9381,    subjob60    734
subjob61   5054,    subjob62   7934,    subjob63   3258,    subjob64   4698,    subjob65   7578,    subjob66   2469
subjob67   3909,    subjob68   8229,    subjob69   4003,    subjob70   6883,    subjob71   1728,    subjob72   4608
subjob73   7488,    subjob74    631,    subjob75   4951,    subjob76   6391,    subjob77   1017,    subjob78   6777
subjob79   5955,    subjob80    538,    subjob81   6298,    subjob82   7738,    subjob83    409,    subjob84   3289
subjob85   2166,    subjob86   6486,    subjob87   7926,    subjob88    522,    subjob89   3402,    subjob90   7722
subjob91   9162,    subjob92   1557,    subjob93   2997,    subjob94   8757,    subjob95  10197,    subjob96   1996
subjob97   4876,    subjob98   7756,    subjob99   2039,    subjob100  3479,    subjob101  9239,    subjob102  1091
subjob103  5411,    subjob104  6851,    subjob105  1234,    subjob106  4114,    subjob107  6994,    subjob108  5445
subjob109  6885,    subjob110  9765,    subjob111  1429,    subjob112  2869,    subjob113 10069,    subjob114  8592
subjob115   549,    subjob116  4869,    subjob117  7749,    subjob118  6548,    subjob119   777,    subjob120  3657
subjob121  3715,    subjob122  6595,    subjob123  2491,    subjob124  9691,    subjob125  9628,    subjob126  5687
subjob127  7127,    subjob128  3967,    subjob129  6847,    subjob130  9727,    subjob131  5247

We need one more important data structure. We want to know which jobs overlap. Those overlapping jobs cannot be placed on the same machine. To get a feeling of the overlap in the data, here is a picture of the subjobs ordered by start time.

Figure 1: Subjobs ordered by start time

The set \(\color{darkblue}{\mathit{Overlap}}_{k,k'}\) will contain the overlapping pairs for \(k\lt k'\). This last condition makes sure we don't double-count. If subjobs (subjob1,subjob2) overlap, then we already know what is going on with subjobs (subjob2,subjob1). We don't need or even want both. The number of unique overlapping subjob pairs is 751. A small section of this looks like:

----    118 SET Overlap  jobs (k<kk) with overlap

subjob1  .subjob19 ,    subjob1  .subjob28 ,    subjob1  .subjob49 ,    subjob1  .subjob53 ,    subjob1  .subjob60 
subjob1  .subjob74 ,    subjob1  .subjob77 ,    subjob1  .subjob80 ,    subjob1  .subjob83 ,    subjob1  .subjob88 
subjob1  .subjob102,    subjob1  .subjob111,    subjob1  .subjob115,    subjob1  .subjob119,    subjob2  .subjob8  
subjob2  .subjob16 ,    subjob2  .subjob26 ,    subjob2  .subjob29 ,    subjob2  .subjob35 ,    subjob2  .subjob51 
subjob2  .subjob56 ,    subjob2  .subjob66 ,    subjob2  .subjob71 ,    subjob2  .subjob85 ,    subjob2  .subjob96 
subjob2  .subjob99 ,    subjob2  .subjob112,    subjob2  .subjob123,    subjob3  .subjob7  ,    subjob3  .subjob21 
subjob3  .subjob39 ,    subjob3  .subjob62 ,    subjob3  .subjob65 ,    subjob3  .subjob68 ,    subjob3  .subjob73 
. . . 

With this data preparation behind us, we are ready to work on the model itself. It looks like:

Mathematical Model

\[ \begin{align} \text{Sets} \\ & k \text{: subjobs} \\ & m \text{: machines} \\ & \hline \\ \text{Data} \\ & \color{darkblue}{\mathit{overlap}}_{k,k'} \>\text{indicates if subjobs $k$ and $k'$ overlap}\\ & \hline \\ \text{Variables} \\ & \color{darkred}{\mathit x}_{k,m} = \begin{cases}1&\text{if subjob $k$ is assigned to machine $m$}\\ 0 &\text{otherwise} \end{cases} \\ & \color{darkred}{\mathit use}_{m} = \begin{cases}1&\text{machine $m$ is used}\\ 0&\text{otherwise}\end{cases} \\ & \hline \\ \text{Model} \\ &\begin{aligned} \min& \sum_m \color{darkred}{\mathit use}_{m} \\ & \sum_m \color{darkred}{\mathit x}_{k,m} = 1&& \forall k \\ & \color{darkred}{\mathit x}_{k,m} + \color{darkred}{\mathit x}_{k',m} \le 1 && \forall \color{darkblue}{\mathit{overlap}}_{k,k'},m\\ & \color{darkred}{\mathit use}_{m} \ge \color{darkred}{\mathit x}_{k,m} && \forall k,m \\ & \color{darkred}{\mathit x}_{k,m} \in \{0,1\}\\ & \color{darkred}{\mathit use}_m \in \{0,1\} \end{aligned} \end{align}\]

The model only needs the overlap data to work. There is no concept of time in this model at all! That may be somewhat of a surprise, as we basically discussed time-related data issues until now.

The first constraint assigns each subjob to exactly one machine. The second constraint makes sure that overlapping jobs don't appear on the same machine. The third and last constraint enforces that we don't place jobs on unused machines. That's it. This has turned out to be a rather simple model.

To make the first machines used, and the last machines unused, we can add an optional ordering constraint: \[\color{darkred}{\mathit use}_{m} \le \color{darkred}{\mathit use}_{m-1}\] This also reduces symmetry in the model.

The generated model is not small:

MODEL STATISTICS

BLOCKS OF EQUATIONS           5     SINGLE EQUATIONS       26,621
BLOCKS OF VARIABLES           3     SINGLE VARIABLES        3,961
NON ZERO ELEMENTS        56,939     DISCRETE VARIABLES      3,960

The largest block of constraints is formed by the overlap constraints. As I used 30 possible machines, we have 751 subjob pairs times 30 machines, which is 22,530 constraints. The MIP model solves this very quickly. Cplex only needed 0.2 seconds. The model was solved completely during preprocessing: zero nodes were needed.

Interestingly, Cplex can reduce the size of the model enormously in the presolve:

Reduced MIP has 2020 rows, 3960 columns, and 19798 nonzeros.

One reason could be that Cplex found earlier a good solution (using some heuristic, I suspect):

Found incumbent of value 12.000000 after 0.00 sec. (1.57 ticks)  

Instead of a problem with 30 machines, it can now work with 12, or even 11 machines. That could explain part of it. I am guessing here. At least that would make the reduction a little bit less embarrassing.

The optimal solution needed 11 machines.  After mapping the solution back in terms of the original (job,day) space, we see:

----    166 PARAMETER assignments  

              machine1    machine2    machine3    machine4    machine5    machine6    machine7    machine8    machine9   machine10

job1 .day1           1
job1 .day2           1
job1 .day6           1
job1 .day7           1
job2 .day2           1
job2 .day4           1
job2 .day5                       1
job3 .day2                       1
job3 .day3           1
job3 .day5           1
job3 .day7                       1
job4 .day3                       1
job4 .day4           1
job4 .day7                                   1
job5 .day3           1
job6 .day2                       1
job6 .day5                       1
job6 .day7                       1
job7 .day1                       1
job7 .day4                       1
job7 .day6                       1
job7 .day7                                               1
job8 .day3                       1
job8 .day4                                   1
job8 .day6           1
job9 .day2                       1
job9 .day3                       1
job10.day1                                   1
job10.day2                                   1
job10.day3                                                                                                                       1
job10.day5                                   1
job10.day7                                                           1
job11.day4                       1
job11.day5                                               1
job12.day2                                               1
job12.day3                                               1
job12.day4                                   1
job12.day5                       1
job12.day6                                   1
job12.day7                                                                       1
job13.day3                                               1
job13.day4                                               1
job14.day2                                                           1
job14.day3                                                           1
job15.day4                       1
job15.day5                                   1
job16.day4           1
job16.day7                                   1
job17.day1                                               1
job17.day5                                                           1
job18.day2                                                           1
job18.day3                                                           1
job19.day1                                               1
job19.day7                                                                                   1
job20.day3                                                                       1
job21.day2                                                                       1
job21.day3                                                                                   1
job21.day5                                               1
job21.day7                                                                                   1
job22.day1                                                           1
job22.day4                                               1
job22.day6                                               1
job23.day3                                   1
job23.day4                                   1
job23.day6                                   1
job24.day2                                                                                   1
job24.day3                                                                                               1
job24.day6                                                           1
job25.day3                                                                                                           1
job25.day5                                                                       1
job26.day1                                                           1
job26.day3                                                                       1
job27.day1                                                                       1
job27.day4                                                           1
job27.day5                                                                       1
job28.day1                                                                       1
job28.day5                                               1
job29.day4                                                                       1
job30.day1                                   1
job30.day5           1
job30.day6                                                                       1
job31.day1                       1
job31.day3                                               1
job32.day2                                                                                               1
job32.day5                                                                                                           1
job32.day6                                                                       1
job33.day1                                                                                   1
job33.day3                                                                                                           1
job33.day6                                                                                               1
job33.day7                                                           1
job34.day1           1
job34.day2                                               1
job34.day6                       1
job34.day7           1
job35.day2                                   1
job35.day4                                                                       1
job35.day6                                                                                   1
job36.day2                                               1
job36.day3                                                                                                                       1
job36.day7                                                                       1
job37.day1                                                                                   1
job37.day4                                                           1
job37.day5                                                                                               1
job38.day1                                                                                               1
job38.day3                                                                                   1
job38.day5                                                           1
job39.day4                                               1
job39.day5                                                                                                           1
job39.day7                                                                                               1
job40.day1                                                                                                           1
job40.day2                                                                                                           1
job40.day7                                                                                                           1
job41.day6                                                                                                           1
job42.day1                                                                                               1
job42.day4                                                                                   1
job42.day6                                                                                                                       1
job43.day5                                                                                                                       1
job44.day1                                                                                                                       1
job45.day3                                   1
job46.day2                                                                                                                       1
job46.day7                                                                                                                       1
job48.day4                                                                                   1
job48.day5                                                                                   1
job49.day3                                   1
job49.day5                                                                                                                       1
job49.day7                                   1
job50.day4                                                                                               1

         +   machine11

job26.day5           1
job44.day3           1
job45.day5           1
job47.day7           1

It is not so easy to see if this solution makes sense. A little visualization can help.

Figure 2: an optimal solution with 11 machines.

This looks ok. The numbers in the chart are the job numbers. Obviously, the fixed start and end times lead to considerable unused capacity on the machines.

Jobs 15 and 7 on machine 2, day 4 look a bit close. But when we look at the data, the end time of job 15 is 415, while job 7 starts at 420. So that is fine. 

Solve as Graph Coloring Problem

Rob Pratt suggested that this can be viewed as a graph coloring problem [2]. The graph is:

• nodes: subjobs (we have 131 of these)
• edges: the 751 overlapping pairs we calculated

We want to color the nodes such that the edges are always connected to two nodes with different colors. The colors can be interpreted as machines.

The usual MIP formulation for the graph coloring problem is slightly different than what I presented here. The graph coloring formulation is: 

Graph Coloring Formulation
\[ \begin{align} \min& \sum_m \color{darkred}{\mathit use}_{m} \\ & \sum_m \color{darkred}{\mathit x}_{k,m} = 1&& \forall k \\ & \color{darkred}{\mathit x}_{k,m} + \color{darkred}{\mathit x}_{k',m} \le \color{darkred}{\mathit use}_{m} && \forall \color{darkblue}{\mathit{overlap}}_{k,k'},m\\ & \color{darkred}{\mathit x}_{k,m} \in \{0,1\}\\ & \color{darkred}{\mathit use}_m \in \{0,1\} \end{align}\]

That is tighter than what I suggested. For instance: \( \color{darkred}{\mathit x}_{k,m}= \color{darkred}{\mathit x}_{k',m}=\color{darkred}{\mathit use}_{m} = 0.5\)  for some overlapping \((k,k',m)\) would be infeasible in the graph coloring formulation, but is a feasible relaxation in my earlier formulation.

However, performance on this problem does not seem to improve. Of course, one observation does not really count. Besides, my formulation was already very fast. My thesis is that good solvers help normal, naturally formulated models more than the tightest possible ones. So, we can often formulate models in a more natural way, without extreme emphasis on performance, as the more advanced solvers will reformulate and preprocess them such that actual solution times are quite similar. 

Note that with the graph coloring formulation, we have one problem. Isolated subjobs \(k\) that don't overlap with any other subjobs, don't get assigned a machine. We can just assign them afterwards to any used machine with \(\color{darkred}{\mathit use}_m=1\). Or we can assign them upfront to say machine number one. This particular data set does not contain any isolated subjobs (see figure 1 to confirm this).

 

The network package networkx [3] has a greedy graph coloring heuristic. When I run this on our overlap data, I see:

Graph after populating: Graph with 131 nodes and 751 edges

Unique colors: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

This solution is very good but slightly suboptimal (12 colors/machines instead of 11). 

Another famous graph coloring application is the coloring of maps [4]. 

Conclusions

• Although there is some data preparation going on in this model, the actual MIP model is very simple. It solves very quickly. This is a good example where a simple MIP model just works very well. The presolve is doing an amazing job here.
• Switching between representations (here from (job,day) to subjob) is an operation we encounter in many models.
• Interestingly, and maybe somewhat counterintuitive, the MIP model does not deal with time at all. The only data it needs is whether two subjobs overlap or not.
• A slightly alternative view of the problem as a Graph Coloring Problem, leads to a slightly different MIP model. Running a fast greedy graph coloring heuristic gives a great, but suboptimal solution.

References

1. Schedule Optimization Question - Variant of Job Shop, https://stackoverflow.com/questions/75438804/schedule-optimization-question-variant-of-job-shop
2. Graph Coloring, https://en.wikipedia.org/wiki/Graph_coloring
3. NetworkX, Software for Complex Networks, https://networkx.org/documentation/stable/index.html
4. Coloring the US county map, https://yetanothermathprogrammingconsultant.blogspot.com/2022/01/coloring-us-county-map.html

Appendix: GAMS model

This is the MIP model for the above results. All data is random.

$ontext       Assign jobs to machines so that the schedule has no overlapping     jobs on the same machine.         Start and completion times of jobs are given.         The goal is to minimize the number of machines we need.   $offtext     *----------------------------------------------------------------- * size of the problem *-----------------------------------------------------------------   Set   d 'days' /day1*day7/   j 'jobs' /job1*job50/   m 'machines' /machine1*machine30/   jd(j,d) 'jobs need to run on certain days' ;   *----------------------------------------------------------------- * random data *-----------------------------------------------------------------   Parameters    start(j) 'start time (minutes since midnight)'    end(j)   'finish time (minutes since midnight)'    length(j) 'length of job (minutes)' ;     * times are in minutes sice start of day (0:00) * minutes per day : 1440 start(j) = uniformint(0,1200); length(j) = uniformint(2*60,15*60); end(j) = start(j) + length(j);   jd(j,d) = uniform(0,1)<0.25;   * some jobs have no days. Give them one scalar day; loop(j$(sum(jd(j,d),0) = 0),    day = uniformint(1,7);    jd(j,d)$(ord(d)=day) = yes; );     parameter counts(*) 'jobs and individual subjob counts'; * calculate number of jobs from jd (this is an extra check * we correctly generated the random data) counts('jobs') = sum(j$sum(jd(j,d),1),1); counts('subjobs') = card(jd);   abort$(counts('jobs')<>card(j)) "Job count mismatch",j,counts;     option start:0,end:0,length:0,counts:0; display start,end,length,jd,counts;   *----------------------------------------------------------------- * map to subjobs *-----------------------------------------------------------------   set    k0 'subjobs superset' /subjob1*subjob10000/    k(k0) 'subjobs in problem'    map(j,d,k0) 'mapping between jobs/days and subjobs' ; singleton set kcur(k0) /subjob1/;   abort$(card(k0)<counts('subjobs')) 'increase size of set k0';   loop(jd,    k(kcur) = yes;    map(jd,kcur) = yes;    kcur(k0) = kcur(k0-1); ); option map:0:0:8; display map;     *----------------------------------------------------------------- * timings in minutes since start of week *-----------------------------------------------------------------   parameters    start2(k0) 'start time of subjob (minutes since start of week)'    end2(k0)   'end time of subjob (minutes since start of week)' ; loop(map(j,d,k),    start2(k) = start(j)+1440*(ord(d)-1);    end2(k) = end(j)+1440*(ord(d)-1); );   option start2:0,end2:0; display start2,end2;     *----------------------------------------------------------------- * which jobs overlap * we only want to compare jobs (k,kk) with k<kk * this is to prevent double counting resulting in too many * constraints in the model *-----------------------------------------------------------------   alias(k,kk);   * we can't do ord on a dynamic set, so we create ordk(k) parameter ordk(k0) 'subjob number'; ordk(k0) = ord(k0);   sets  noOverlap(k0,k0)  'jobs (k<kk) without overlap'  Overlap(k0,k0)    'jobs (k<kk) with overlap' ; noOverlap(k,kk)$(ordk(k)<ordk(kk)) = start2(k) > end2(kk) or start2(kk) > end2(k); overlap(k,kk)$(ordk(k)<ordk(kk)) = not noOverlap(k,kk);   option overlap:0:0:8; display overlap;   scalar numOverlap 'number of overlapping subjobs'; numOverlap = card(Overlap); option NumOverlap:0; display numOverlap;   *----------------------------------------------------------------- * Model *-----------------------------------------------------------------   binary variables     x(k0,m) 'assign job to machine'     used(m) 'machine is used' ;   variable num 'number of machines needed';   Equations    mustRun(k0)           'job has to be assigned to exactly one machine'    dontOverlap(k0,k0,m)  'forbid overlapping jobs on the same machine'          usage(k0,m)           'use=0 => x=0'    numMachines           'objective: minimize number of used machines'    order(m)              'optional: ordering constraint' ;    mustRun(k)..  sum(m,x(k,m)) =e= 1; dontOverlap(k,kk,m)$overlap(k,kk).. x(k,m)+x(kk,m) =l= 1; usage(k,m)..  used(m) =g= x(k,m); numMachines.. num =e= sum(m,used(m)); order(m-1)..  used(m) =l= used(m-1);   model assign1 /mustrun,dontoverlap,usage,nummachines,order/;     *----------------------------------------------------------------- * Alternative graph coloring formulation *-----------------------------------------------------------------     Equation    coloring(k0,k0,m)            'graph coloring constraint' ;   coloring(k,kk,m)$overlap(k,kk).. x(k,m)+x(kk,m) =l= used(m);   model assign2 /mustRun,coloring,numMachines,order/;   *----------------------------------------------------------------- * fix isolated subjobs to run on machine 1 * * needed for the graph coloring model * (not needed for the first model, but is does not hurt) * * this is ok even when not using the ordering constraint *-----------------------------------------------------------------   set isolated(k0) 'jobs that have no overlap with other jobs'; isolated(k) = yes; isolated(k)$sum(overlap(k,kk),1) = no; isolated(kk)$sum(overlap(k,kk),1) = no; display isolated;   x.fx(isolated,m)$(ord(m)=1) = 1;   *----------------------------------------------------------------- * Solve *-----------------------------------------------------------------   option threads = 0; solve assign1 minimizing num using mip; option x:0,used:0,num:0; display x.l,used.l,num.l;   *----------------------------------------------------------------- * report solution in original space *-----------------------------------------------------------------   parameter assignments(j,d,m); assignments(jd,m) = sum(map(jd,k),x.l(k,m)); option assignments:0; display assignments;   *----------------------------------------------------------------- * prepare data for plotting *-----------------------------------------------------------------   parameter plotdata(j,d,k0,m,*);   plotdata(map(j,d,k),m,'start')$(x.l(k,m)>0.5) = start2(k); plotdata(map(j,d,k),m,'end')$(x.l(k,m)>0.5) = end2(k); plotdata(map(j,d,k),m,'machine')$(x.l(k,m)>0.5) = ord(m);   execute_unload 'plotdata',plotdata; execute 'gdxdump plotdata.gdx symb=plotdata format=csv output=plotdata.csv cdim=1';   *----------------------------------------------------------------- * prepare data for networkx *-----------------------------------------------------------------   execute_unload "networkdata" overlap; execute 'gdxdump networkdata.gdx symb=overlap format=csv output=networkdata.csv';

 

Appendix 2: Graph coloring heuristic

This uses a Graph Coloring heuristic to find a good, but suboptimal solution. The overlap data is from the above GAMS model (the set overlap). The nodes are the subjobs.

The graph is somewhat of a monstrosity.

Figure 3: plot of network.

We can see a few interesting things here. The blobs of nodes are days. We have one isolated day. From the solution plot, we can conclude that it must be day 7. No jobs from day 6 overlap with jobs on day 7 (see figure 1).