advent_or_day22.mzn

include "globals.mzn";

int: N;
int: M;

set of int: JOBS = 1..N;
set of int: MACHINES = 1..M;

array[JOBS, MACHINES] of int: durations;
array[JOBS, MACHINES] of int: steps;

int: min_duration = 
    max(j in JOBS)(sum(row(durations, j)));

int: max_duration = sum(durations);

%% Start times (job i starts at start[i] on machine j)
array[JOBS, MACHINES] of var 0..max_duration: start;


constraint forall(j in JOBS, m in 1..M-1)(
  start[j, m] + durations[j, m] <= start[j, m +1]
);


constraint forall(m1, m2 in MACHINES)(
  forall(j1 in 1..N-1, j2 in  (j1+1)..N)(
    (steps[j1, m1]  =  steps[j2, m2])  ->

  (
    start[j1, m1] + durations[j1, m1] <= start[j2, m2]
    \/
    start[j2, m2] + durations[j2, m2] <= start[j1, m1]

  ) 
  )
);


var min_duration..max_duration : makespan;

constraint makespan = max(j in 1..N)(start[j, M] + durations[j, M]) - 1;

annotation relax_and_reconstruct(array[int] of var int,int);
annotation restart_luby(int);

solve 
  :: int_search(start, dom_w_deg, indomain_random, complete)
  minimize makespan;

% abz5 instance
%
% Solution: HIGHS (optimal solution)

job 1: [267, 363, 441, 554, 653, 774, 863, 940, 1039, 1125]
job 2: [0, 119, 242, 355, 430, 815, 903, 995, 1077, 1171]
job 3: [0, 83, 144, 227, 311, 469, 821, 899, 984, 1039]
job 4: [50, 144, 457, 527, 626, 686, 761, 827, 940, 1003]
job 5: [0, 98, 186, 268, 425, 524, 591, 686, 754, 821]
job 6: [0, 186, 267, 375, 524, 604, 684, 790, 852, 1146]
job 7: [0, 99, 430, 527, 623, 718, 863, 929, 1028, 1100]
job 8: [0, 98, 171, 253, 304, 375, 469, 554, 616, 711]
job 9: [50, 171, 253, 334, 518, 684, 774, 850, 908, 1003]
job 10: [69, 227, 375, 457, 554, 610, 761, 984, 1065, 1124]

makespan: 1234
% time elapsed: 4m 5s

==========