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
 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
 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
. . .
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}\] 
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
Reduced MIP has 2020 rows, 3960 columns, and 19798 nonzeros.
Found incumbent of value 12.000000 after 0.00 sec. (1.57 ticks)
 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
Solve as Graph Coloring Problem
 nodes: subjobs (we have 131 of these)
 edges: the 751 overlapping pairs we calculated
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}\] 
Graph after populating: Graph with 131 nodes and 751 edgesUnique colors: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
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
 Schedule Optimization Question  Variant of Job Shop, https://stackoverflow.com/questions/75438804/scheduleoptimizationquestionvariantofjobshop
 Graph Coloring, https://en.wikipedia.org/wiki/Graph_coloring
 NetworkX, Software for Complex Networks, https://networkx.org/documentation/stable/index.html
 Coloring the US county map, https://yetanothermathprogrammingconsultant.blogspot.com/2022/01/coloringuscountymap.html
Appendix: GAMS model
$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(k01); ); 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(m1).. used(m) =l= used(m1);
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
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).
networkx has a coloring heuristic. I need to try this out!
ReplyDeleteI had the same idea as Rob Pratt: this is a graph theory problem. Interesting that the MIP solved so quickly despite the symmetry in the use[m] variables.
ReplyDeleteAmazing work Erwin! Question, how would the graph output a table of what subjobs each machine would run?
ReplyDeleteThe GANTT chart would be largely the same (different numbers and even more colors). The CSV file already contains the subjob ids (column k).
DeleteIn fact, because the graph is an interval graph (https://en.wikipedia.org/wiki/Interval_graph), you can solve the node coloring problem via minimumcost network flow on a directed network, without explicitly using integer variables. For this instance, the network has 264 nodes and 8158 arcs. The objective is to minimize the flow from the source node to the job nodes. See my answer here: https://math.stackexchange.com/questions/4653921/schedulingjobswithfixedstartandendtimeonlimitedmachines/4654550#4654550
ReplyDeleteI need to try that!
DeleteIt worked well for me, and I look forward to seeing your update. By the way, my original comment somehow got deleted.
DeleteSorry, I see your old comment is marked as spam and hidden (don't know why; must be AI).
Delete