/* 

  Scheduling with assignments of workers in Picat.

  (This is a port of my MiniZinc model scheduling_with_assignments.mzn)

  The reason I wrote this model was that most (if not all) 
  examples of scheduling (e.g. using cumulative) don't show the 
  assignments of the individual workers. It's just a list
  of start_times and end_times.

    start_time = [0,0,30,45]
    end_time = [30,10,45,60]

  But who was assigned to what job?
  
  This model features the following:

    - the order of jobs is calculated using cumulative.

    - it shows the assignments of workers to the job in several ways:
      * assignment matrices for both jobs to workers and workers to jobs
      * timelines for jobs as well as for workers (Gantt like)
      (Note: the timeline for the jobs is hard to get aligned in a pretty
       way.)

    - can handle precedences between jobs (when do_precedence = true).
      There are some examples of this (via the link below).

    - can enforce that idleness is not allowed (with allow_idle=false), 
      i.e. that a worker cannot be idle until his/her last task.
      This is for testing the Rule 1 from Ron L. Graham's paper 
       "Combinatorial Scheduling Theory". See below for more comments.
      This is tested in the models 
         scheduling_with_assignments10*.dzn

      Note: Enforcing non-idleness can make the solving time much 
      longer, and can lead to some unexpected results (which is discussed
      in Graham's paper.)

    - can enforce that the workers assigned to a tasks must be "near" i.e.
      as a collected block. This is set by collect_workers = true.

      This might lead to nicer (Gantt-like) output and solve some more 
      type of problems, e.g. perfect square placement problems.
      It can also make the result sub-optimal compared with a version

      For perfect square placement problems, I also added Sat = true
      which mean that a sat solution is asked for (not minimization).

      It should be considered experimental.
      


  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import sat.
% import cp.

main => go.


go =>
  nolog,
  Problem =  2,
  run_problem(Problem),

  nl.

/*
  Timing for SAT (no timeout)

                      SAT
                 seconds    obj     
   ---------------------------------------------------------------------------------------
   1                 0.235  60
   2                 0.166  22
   3                 0.263  10
   4                 1.327  22
   5                30.673 130
   6                 0.309  90
   7               193.164  70         
   8                50.66   60
   '8b'             4.058  270 
   9                0.222   13
   10               0.057   32
   '10b'            0.131   33
   '10c'            0.158   33  
   '10d'            0.253   34
   11               0.16    14 
   12               4.914  230
   13               2.802   55
   14               0.1     14    
   '14b'          928.528  112
   '14c'            0.068    8
   15               0.065   12    
   16               2.164    7 
   '16b'            2.164    7
   '16c'         2580.32     6
   '16d'           28.155    7 
   17               0.344   19
   18               2.955   66
   19               0.287   12
   20               0.151   15
   21               0.245    8
   22               8.026    4
   23             283.041  285    
   -------------------------------------------------------------------------
   Total        4502.258

   Run time  1h14min30.31s


*/

go2 =>
  nolog,
  Problems = [1,2,3,4,5,6,7,8,'8b',9,10,'10b','10c','10d',11,12,13,14,'14b','14c',15,16,'16b','16c','16d',17,18,19,20,21,22,23],
  println(problems=Problems),
  member(P,Problems),
  println(problem=P),
  flush(stdout),  
  time(run_problem(P)),
  nl,
  flush(stdout),
  fail,
  nl.


% All optimal solutions
go3 =>
  nolog,
  Problem = 20,
  printf("Problem %w\n", Problem),
  data(Problem,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat),
  schedule(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,
           Precedences,DoPrecedences,Sat, _StartTime,_EndTime,EarliestEndTime,
           _Assignments,_NumAssignments,_FirstWorkerAssigned,WorkersTime),
  printf("Optimal time: %d\n",EarliestEndTime),
  println("\nAll optimal solutions:"),

  schedule(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,
           Precedences,DoPrecedences,Sat, StartTime,EndTime,EarliestEndTime,Assignments,
           NumAssignments,FirstWorkerAssigned,WorkersTime),

  print_solution(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat,
                 StartTime,EndTime,EarliestEndTime,Assignments,NumAssignments,FirstWorkerAssigned,WorkersTime),
  fail,
  nl.


%
% Run a problem and print solution
%
run_problem(Problem) =>
  data(Problem,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat),
  println([Problem,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat]),
  schedule(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,
           Precedences,DoPrecedences,Sat, StartTime,EndTime,EarliestEndTime,Assignments,
           NumAssignments,FirstWorkerAssigned,WorkersTime),

  print_solution(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat,
                 StartTime,EndTime,EarliestEndTime,Assignments,NumAssignments,FirstWorkerAssigned,WorkersTime),
  nl.


%
% Print the solution.
%
print_solution(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat,
               StartTime,EndTime,EarliestEndTime,Assignments,NumAssignments,FirstWorkerAssigned,WorkersTime) =>

  println(num_jobs=NumJobs),
  println(num_workers=NumWorkers),
  println(max_time=MaxTime),
  println(allow_idle=AllowIdle),
  println(collect_workers=CollectWorkers),
  println(do_precedences=DoPrecedences),
  println(sat=Sat),
  if DoPrecedences, Precedences.len > 0 then
     println("Precedences:"),
     foreach(P in Precedences)
       printf("Job %d before Job %d\n", P[1],P[2])
     end
  end,
  nl,
  println('start_time'=StartTime),
  println('duration  '=Duration),  
  println('end_time  '=EndTime),
  println('resource  '=Resource),  
  println(earliest_end_time=EarliestEndTime),
  nl,
  % println(assignments=Assignments),
  println('first_worker_assigned'=FirstWorkerAssigned),
  println(num_assignments=NumAssignments),
  nl,
  println("Assignments Jobs / workers:"),
  foreach(J in 1..NumJobs)
    printf("Job %3d: %w\n", J, [Assignments[J,W] : W in 1..NumWorkers])
  end,
  nl,
  println("Assignments Workers / Jobs:"),
  foreach(W in 1..NumWorkers)
    printf("Worker %3d: %w\n", W,[Assignments[J,W] : J in 1..NumJobs])
  end,
  nl,
  println("Time range for the jobs and the assigned worker(s):"),
  foreach(J in 1..NumJobs)
    printf("Job %3d (%3d..%3d): %w\n", J, StartTime[J], EndTime[J], [W : W in 1..NumWorkers, Assignments[J,W] == 1])
  end,
  nl,
  println("Schedule: jobs (workers):"),
  foreach(Time in 0..EarliestEndTime-1)
    printf("Time %3d: ", Time),
    foreach(Job in 1..NumJobs)
      if Time >= StartTime[Job], Time < EndTime[Job] then
        Workers = [W : W in 1..NumWorkers, Assignments[Job,W] == 1],
        printf("(J%d, Ws:%w) ", Job,[W.to_string : W in Workers].join(" ")),
        print(" ")
      else
        printf("     --    ")
      end
    end,
    nl
  end,
  nl,

  % Create the Gantt graph
  println("Schedule: worker(job):"),
  printf("Workers:  %w\n", [to_fstring("%3d", W) : W in 1..NumWorkers].join(" ")),
  Gantt = new_array(EarliestEndTime,NumWorkers),
  foreach(Time in 0..EarliestEndTime-1)
    % check which job (if any) the worker is assigned to at this time
    foreach(W in 1..NumWorkers)
      Jobs = [J : J in 1..NumJobs, Assignments[J,W] == 1, Time >= StartTime[J], Time < EndTime[J]],
      % Sanity check.
      if Jobs.len > 1 then
        printf("Error: Worker %d is assigned at more than one job at time %d!\n",W,Time),
        halt
      end,
      if Jobs != [] then
        Gantt[Time+1,W] := to_fstring("%3d ",Jobs.first)
      else
        Gantt[Time+1,W] := "  - "
      end
    end
  end,
  foreach(Time in 0..EarliestEndTime-1)
    printf("Time %3d: %w\n", Time, Gantt[Time+1].to_list.join(''))
  end,
  nl,
  % Transpose of above.
  printf("Schedule: worker(job), timeline: (earliest_end_time: %d)\n", EarliestEndTime),
  foreach(W in 1..NumWorkers)
    printf("Worker %3d: %w\n",W, [Gantt[Time+1,W] : Time in 0..EarliestEndTime-1].join(''))
  end,
  nl,
  % The Timeline
  printf("Timeline:   %w\n",[to_fstring("%3d ", TT) : T in 0..EarliestEndTime-1, TT = cond(T mod 10 == 0, T, T mod 10)].join('')),

  nl,
  println("Workers time (is a worker assigned at time t?):"),
  foreach(W in 1..NumWorkers)
    printf("Worker %2w: %w\n", W, [to_fstring("%d",WorkersTime[W,T+1]) : T in 0..EarliestEndTime-1].join(''))
  end,
  nl,
  printf("EarliestEndTime: %d\n", EarliestEndTime),
  nl.

%
% Solve the scheduling problem.
%
schedule(NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat,
         StartTime,EndTime,EarliestEndTime,Assignments,NumAssignments,FirstWorkerAssigned,WorkersTime) => 

  % decision variables
  % Start/End times for the jobs
  StartTime = new_list(NumJobs),
  StartTime :: 0..MaxTime,

  EndTime = new_list(NumJobs),
  EndTime :: 0..MaxTime,

  % Assignments of workers for the jobs (0/1 matrix)
  Assignments = new_array(NumJobs,NumWorkers),
  Assignments :: 0..1,

  % Is a workers assigned to any job at time Time?
  % Note: The time stated is Time+1.
  % This is used in AllowIdle = false and to ensure that the worker
  % is assigned to atmost a single job per time slot.
  WorkersTime = new_array(NumWorkers,MaxTime),
  WorkersTime :: 0..1,

  % Number of assignments per worker
  NumAssignments = new_list(NumWorkers),
  NumAssignments :: 0..NumJobs,

  % The first worker assigned to a job
  % (for symmetry breaking with value_precede_chain/2)
  FirstWorkerAssigned = new_list(NumJobs),
  FirstWorkerAssigned :: 1..NumWorkers,


  % Calculate the EndTime for each job
  foreach(Job in 1..NumJobs)
    EndTime[Job] #= StartTime[Job] + Duration[Job]
  end,

  % Timespan (to minimize)
  EarliestEndTime #= max(EndTime),

  % get the job order
  cumulative(StartTime, Duration, Resource, NumWorkers),

  % assignmenst
  foreach(W in 1..NumWorkers)
    NumAssignments[W] #= sum([Assignments[J,W] : J in 1..NumJobs])
  end,

  % Workers time
  foreach(W in 1..NumWorkers)
    foreach(Time in 0..MaxTime-1)
      WorkersTime[W,Time+1] #= sum([Assignments[J,W] #= 1 #/\ Time #>= StartTime[J] #/\ Time #< EndTime[J] : J in 1..NumJobs])
    end
  end,

  foreach(Job in 1..NumJobs)
     % Check number of workers working with the job
     % This is important. Without it, we can cheat and put more people on the job.
     Resource[Job] #= sum([Assignments[Job,W] : W in 1..NumWorkers ]),

     /*
     2022-06-26: Skipped these two no_overlap constraints for SAT solver.
                 The CP solver is faster (but not fast) with them.
     */
     if member(cp,loaded_modules()) then
       % If a person is assigned to two jobs, then these jobs cannot overlap.
       foreach(J2 in 1..NumJobs, Job < J2)
         sum([Assignments[Job,W] + Assignments[J2,W] #= 2 : W in 1..NumWorkers]) #= 2
         #=> 
         (StartTime[Job] + Duration[Job] #<= StartTime[J2]
          #\/
          StartTime[J2] + Duration[J2] #<= StartTime[Job]) 
       end,
   
       % If the resources of two jobs > total number of workers
       % they cannot overlap. 
       foreach(J2 in 1..NumJobs, Job < J2)
         if Resource[Job] + Resource[J2] > NumWorkers then
              no_overlap(StartTime[Job], Duration[Job],
                         StartTime[J2], Duration[J2])
          end
       end
     end
     
  end,


  %
  % Set the lower bound of makespan x num_workers
  %
  EarliestEndTime*NumWorkers #>= sum([Duration[J]*Resource[J] : J in 1..NumJobs]),

  %
  % Collect workers.
  %
  % Enforce that all jobs are done by "near" workers, i.e.
  % seeing the workers as a "block".
  %
  % This is done with a (decomposition) of the global 
  % constraint contiguity.
  %
  if CollectWorkers then
     println(collect_workers),
     foreach(J in 1..NumJobs) 
       if Resource[J] > 1 then
          global_contiguity_regular([Assignments[J,W] : W in 1..NumWorkers])
        end
     end
  end,

  %
  % Handle precedences
  %
  if DoPrecedences, Precedences.len > 0 then    
    foreach(P in 1..Precedences.len)
       prec(Precedences[P,1], Precedences[P,2], StartTime, Duration)
    end
  end,

  

  %
  % Handle idleness
  % 
  % If allow_idle = false then there can be no idle time 
  % for any worker until after his/her final task.
  %
  % We implement this simply as the checking that
  % the total work time must be the same as the end_time for
  % the last task.
  %
  if AllowIdle == false then
    println(allow_idle),
      % % This works in MiniZinc but not in Picat:
      % foreach(W in 1..NumWorkers)
      %   max([EndTime[J]*Assignments[J, W] #= 1 : J in 1..NumJobs])
      %   #=
      %   sum([Duration[J]*Assignments[J, W] : J in 1..NumJobs])
      % end,

    % OK, here's another way of stating this:
    % If time T is schedules for a worker, then T-1 must be as well
    foreach(W in 1..NumWorkers)
      foreach(Time in 2..MaxTime)
        WorkersTime[W,Time] #> 0 #=> WorkersTime[W,Time-1] #> 0
      end
    end
  end,


  %
  % Symmetry breaking (experiments)
  %

  % Symmetry breaking: Assign worker 1 before worker 2 etc
  foreach(J in 1..NumJobs)
    min_except_0_assignment(1..NumWorkers,[Assignments[J,W]: W in 1..NumWorkers], FirstWorkerAssigned[J])
  end,
  % This should not be activated when CollectWorkers == true, e.g. problem 14
  if not CollectWorkers  then
    value_precede_chain(1..NumWorkers,FirstWorkerAssigned)
  end,

  % lex2/1 does not work well with the other symmetry breaking constraints
  % - decreasing(NumAssignments)
  % - value_precede_chain(1..NumWorkers,FirstWorkerAssigned)
  % lex2(Assignments), 

  % Symmetry breaking
  % decreasing(NumAssignments), % This does not work with lex2/1!

  %
  % Solve
  %

  
  if member(cp,loaded_modules()) then
    % cp solver
    Vars = StartTime ++ EndTime ++ Assignments.vars ++ WorkersTime.vars ++ FirstWorkerAssigned ++ NumAssignments
  else
    % sat solver
    Vars = Assignments.vars ++ WorkersTime.vars ++ StartTime ++ EndTime ++ FirstWorkerAssigned ++ NumAssignments
  end,
  if var(EarliestEndTime), not Sat then
    solve($[constr,min(EarliestEndTime),report(printf("EarliestEndTime: %d\n",EarliestEndTime))],Vars)
  else
    solve($[split],Vars)  
  end.


%
% Ensure that there are no overlaps between two jobs.
%
no_overlap(S1, D1, S2, D2) =>
   (S1 + D1 #<= S2) #\/ (S2 + D2 #<= S1).

%
% Precedences: start[job1] must be done before start[job2]
%
prec(Job1, Job2, Start, Dur) =>
   Start[Job1] + Dur[Job1] #<= Start[Job2].

%
% Global contiguity via regular
% (Cf http://www.hakank.org/minizinc/contiguity_regular.mzn )
%
global_contiguity_regular(X) =>

   N = X.length,

   % Transition function (MiniZinc style)  
   % This use the regular expression "0*1*0*" to 
   % require that all 1's (if any) in an array appear contiguously.
   % 
   Transition = [
                 [1,2], % state 1 (start) input 0 -> state 1, input 1 -> state 2 i.e. 0*
                 [3,2], % state 2: 1*
                 [3,0]  % state 3: 0*
                ],
   NStates = 3,
   InputMax = 2,
   InitialState = 1,
   AcceptingStates = [1,2,3],

   RegInput = new_list(N),
   RegInput :: 1..InputMax,  % 1..2

   % Translate X's 0..1 to RegInput's 1..2
   foreach(I in 1..N) 
      RegInput[I] #= X[I]+1  
   end,

   regular(RegInput,NStates,InputMax,Transition,InitialState, AcceptingStates).


lex2(X) =>
   Len1 = X.len,
   Len2 = X[1].length,
   foreach(I in 2..Len1) 
      lex_le([X[I-1, J] : J in 1..Len2], [X[I, J] : J in 1..Len2])
   end,
   foreach(J in 2..Len2)
      lex_le([X[I ,J-1] : I in 1..Len1], [X[I, J] : I in 1..Len1])      
   end.

%
% min_except_0(Values,Assignments,MinVal)
% Ensure that the minumum value (> 0) in Assignmments[J] #= 1 is MinVal.
%
min_except_0_assignment(V,A,MinVal) =>
  % println($min_except_0(V,A,MinVal)),
  MinVal :: V,
  % element(_I,V,MinVal), % min val must be a value in X
  foreach(J in 1..V.len)
    A[J] #= 1 #=> MinVal #<= V[J],
    A[J] #= 0 #=> MinVal #!= V[J]
  end.


value_precede_chain(C, X) =>
  foreach(I in 2..C.length)
    value_precede(C[I-1], C[I], X)
  end.

% This definition is inspired by 
% MiniZinc definition value_precede_int.mzn
value_precede(S,T,X) =>
   XLen = X.length,
   B = new_list(XLen+1),
   B :: 0..1,
   foreach(I in 1..XLen)
     % Xis :: 0..1,
     Xis #= (X[I] #= S),
     (Xis #=> (B[I+1] #= 1))
     #/\ ((#~ Xis #= 1) #=> (B[I] #= B[I+1]))
     #/\ ((#~ B[I] #= 1) #=> (X[I] #!= T))
   end,
   B[1] #= 0.




%
% Data ported from the problems instances
% http://hakank.org/minizinc/#scheduling_with_assignments
% The problem number is the same as the MiniZinc instances
% http://www.hakank.org/minizinc/scheduling_with_assignments<problem_id>.dzn
%
% hakank: Added Sat = true for perfect square problems...
%
%
% This problem is from Marriott & Stuckey: 
%   "Programming with constraints", page  112f)
% Cf: furniture_moving.pi
%
data(1,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 4,
  NumWorkers = 4,
  Duration = [30,10,15,15],
  Resource = [3,1,3,2],
  MaxTime = 70, % optimal: 60
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.

% Problem from Ivan Bratko 
% "Prolog - Programming for Artificial Intelligence", 3rd edition,
% page 329ff.
% Ported from http://www.hakank.org/minizinc/scheduling_with_assignments2.dzn
data(2,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 5,
  NumWorkers = 3,
  Duration = [5,7,10,2,9],
  Resource = [1,1, 1,1,1],
  MaxTime = 33, % optimal: 22 (12 without precedences)
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,  
  Precedences = [[1,2],
                 [1,4],
                 [2,3],
                 [4,5]],
  Sat = false.


%
% Problem from Global constraints catalog
%    http://www.emn.fr/x-info/sdemasse/gccat/Ccumulative.html
%
data(3,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 5,
  NumWorkers = 7,
  Duration = [3,9,10,6,2],
  Resource = [1,2, 1,1,3],
  MaxTime = 30, % optimal: 10
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Problem from SICStus documentation
%    http://www.sics.se/sicstus/docs/4.0.1/html/sicstus/Cumulative-Scheduling.html
% (Also , Nicolas Beldiceanu & Evelyne Contejean: 
%  "Introducing Global Constraints in CHIP", page 3f)
%
data(4,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 7,
  NumWorkers = 13,
  Duration = [16,6,13,7,5,18,4],
  Resource = [2,9,3,7,10,1,11],
  MaxTime = 30, % optimal: 22
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% A little harder test
%
data(5,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 9,
  NumWorkers = 5,
  %           j1 j2 j3 j4 j5 j6 j7 j8 j9
  Duration = [30,10,15,15,20,10,10,45,20],
  Resource = [ 3, 1, 3, 2, 4, 2, 2, 4, 3],
  MaxTime = 175, % optimal: 130
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% From the OPL model sched_intro.model
% (with the precedences)
% Cf http://www.hakank.org/minizinc/building_a_house.mzn
%
% Compare with the output from
%    http://www.hakank.org/minizinc/building_a_house.mzn
% where the first time is 1, not 0 as in this model:
% makespan: 91
% z: 91
% masonry: 1 - 35 --> 36
% carpentry: 36 - 15 --> 51
% plumbing: 36 - 40 --> 76
% ceiling: 36 - 15 --> 51
% roofing: 51 - 5 --> 56
% painting: 51 - 10 --> 61
% windows: 56 - 5 --> 61
% facade: 76 - 10 --> 86
% garden: 76 - 5 --> 81
% moving: 86 - 5 --> 91
%
% Note: This problem is harder _without_ the precedences:
% It takes 0.2 seconds with precedences, and about 2 seconds without.
%
data(6,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 10,
  NumWorkers = 3,
  Duration =  [35,15,40,15, 5,10, 5,10, 5, 5],
  Resource =  [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 145, % optimal: 90  (50 without the precedences)
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = [
                 [1,2],  % masonry,   carpentry, 
                 [1,3],  % masonry,   plumbing, 
                 [1,4],  % masonry,   ceiling,
                 [2,5],  % carpentry, roofing,
                 [4,6],  % ceiling,   painting,
                 [5,7],  % roofing,   windows,
                 [5,8],  % roofing,   facade,
                 [3,8],  % plumbing,  facade,
                 [5,9],  % roofing,   garden,
                 [3,9],  % plumbing,  garden,
                 [7,10], % windows,   moving,
                 [8,10], % facade,    moving,
                 [9,10], % garden,    moving,
                 [6,10]  % painting,  moving
                ],
  Sat = false.

%
% Another harder test
%
data(7,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 15,
  NumWorkers = 15,
  Duration = [30,10,15,15,20,10,10,45,20, 10,10,20,30,40,50],
  Resource = [ 3, 1, 3, 2, 4, 2, 2, 4, 3,  2, 2, 2, 3, 3, 4],
  MaxTime = 100, % optimal: 70
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% This is much harder...
%
data(8,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 20,
  NumWorkers = 20,
  Duration = [30,10,15,15,20,10,10,45,20, 10,10,20,30,40,50,30,20,10,15,25],
  Resource = [ 3, 1, 3, 2, 4, 2, 2, 4, 3,  2, 2, 2, 3, 3, 4, 1, 1, 2, 2,  2],
  MaxTime = 100, % optimal: 60 (for 20 workers)
  AllowIdle = true,
  CollectWorkers = true,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.

%
% This is a variant of the hard problem 8. With precedences it's much faster.
%
data('8b',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 20,
  NumWorkers = 6,
  % jobs       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
  Duration = [30,10,15,15,20,10,10,45,20,10,10,20,30,40,50,30,20,10,15,25],
  Resource = [ 3, 1, 3, 2, 4, 2, 2, 4, 3, 2, 2, 2, 3, 3, 4, 1, 1, 2, 2, 2],
  MaxTime = 400, % optimal: 270
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = [ 
                 [1,2],
                 [1,3],
                 [1,4],
                 [2,3],
                 [2,4],
                 [3,4],
                 [4,5],
                 [5,6],
                 [5,7],
                 [5,8],
                 [5,10],
                 [6,10],
                 [6,11],
                 [11,12],
                 [12,13],
                 [12,14],
                 [14,15],
                 [15,16],
                 [15,17],
                 [15,18],
                 [16,19],
                 [17,20]],
  Sat = false.


%
% Problem from 
% Andreas Schutt, Thibaut Feydy, Peter J. Stuckey, Mark G. Wallace:
% "Explaining the cumulative propagator", page 2 (figure 1)
%
%            ------f(6)  ---------
%           /                      \
%   source-> -- d(4) ---> e(5) -----> sink
%          \                        /
%            - a(1) -> b(2) -> c(3)
%
%
data(9,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 6,
  NumWorkers = 5,
  %           1 2 3 4 5 6
  Duration = [2,6,2,2,5,6],
  Resource = [1,2,4,2,2,2],
  MaxTime = 20, % optimal: 13
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = [ 
                [1,2], % a,b
                [2,3], % b,c
                [4,5]  % d,e,
                ],
  Sat = false.



%
% Assembling bicycles
%
% Problem from R.L. Graham: "Combinatorial Scheduling Theory",
% in L. A. Steen (Ed.), Mathematics Today: "Twelve Informal Essays", 
% Springer-Verlag, New York, 1978, pp. 183-211.
%
% http://www.math.ucsd.edu/~ronspubs/78_15_combinatorial_scheduling.pdf
%
% The tasks:
% FP - Frame preparation which includes installation of the
%     front fork and fenders.
% FW - Mounting and aligning front wheel.
% BW - Mounting and aligning back wheel.
% DE - Attaching the derailleur to the frame.
% GC - Installing the gear cluster.
% CW - Attaching the chain wheel to the crank.
% CR - Attaching the crank and chain wheel to the frame.
% RP - Mounting right pedal and toe clip.
% LP - Mounting left pedal and toe clip.
% FA - Final attachments which includes mounting and adjusting
%      handlebars, seat, brakes, etc.
%
%
% Precedences:
%  Job     must be done after  job(s)
%  -----------------------------------------
%  FA                           FP,FW,BW,GC,DE
%  BW                           GC,DE
%  GC,CW                        DE
%  LP, RP                       CR,CW,GC
%  CR                           CW

%
% Also see:
% "A Quick and Gentle Guide to Constraint Logic Programming
%  via ECLiPSe", page 353ff.
%
%
% Note:
% There are 128 different optimal solutions with a makespan of 32.
% With symmetry breaking, it's 16 solutions.
%

% There are some variants of this problem instance where we experiments
% (somewhat following Graham's paper) with idleness and durations:
%  - scheduling_with_assignments10b.mzn: 
%      * setting allow_idle = false
%        (this is Graham's Rule 1)
%  - scheduling_with_assignments10c.mzn
%      * setting allow_idle = false
%      * increase num_workers to 3
%  - scheduling_with_assignments10d.mzn
%      * setting allow_idle = false
%      * decrease each tasks' duration with one.
%  Some of the improvements leads to unexpected results,
%  since allow_idle = false (Rule 1) makes the scheduling 
%  too greedy..
%
data(10,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 10,
  % Max number of workers/team that can be assigned (with some job): 6
  % (but it don't give better results than with 2 workers/team)
  NumWorkers = 2,
  %            1  2  3  4  5  6  7  8  9 10
  %           FP FW BW DE GC CW CR RP LP FA
  Duration = [ 7, 7, 7, 2, 2, 2, 2, 8, 8,18],
  Resource = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 63, % optimal: 32
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                            1,10, % FP,FA,
                            2,10, % FW,FA,
                            3,10, % BW,FA,
                            4,10, % DE,FA,
                            5,10, % GC,FA,
                            4,3,  % DE,BW,
                            5,3,  % GC,BW,
                            1,3,  % FP,BW,
                            4,5,  % DG,GC,
                            4,6,  % DG,CW,
                            5,8,  % GC,RP,
                            5,9,  % GC,LP,
                            6,8,  % CW,RP,
                            6,9,  % CW,LP,
                            7,8,  % CR,RP,
                            7,9,  % CR,LP,
                            6,7,  % CW,CR,
                            1,2   % FP,FW
                           ],2),
  Sat = false.



%
% Assembling bicycles.
% This is the same problem as in problem #10.
%
% Here we test the effect of Graham's Rule 1, i.e. that there can
% be no idleness for a worker until his/her last task.
% (allow_idle = false).
%
data('10b',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) => 
  NumJobs = 10,
  % Max number of workers/team that can be assigned (with some job): 6
  % (but it don't give better results than with 2 workers/team)
  NumWorkers = 2,
  %            1  2  3  4  5  6  7  8  9 10
  %           FP FW BW DE GC CW CR RP LP FA
  Duration = [ 7, 7, 7, 2, 2, 2, 2, 8, 8,18],
  Resource = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 63, % optimal: 33
  AllowIdle = false, % Testing of Rule 1
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                           1,10, % FP,FA,
                           2,10, % FW,FA,
                           3,10, % BW,FA,
                           4,10, % DE,FA,
                           5,10, % GC,FA,
                           4,3,  % DE,BW,
                           5,3,  % GC,BW,
                           1,3,  % FP,BW,
                           4,5,  % DG,GC,
                           4,6,  % DG,CW,
                           5,8,  % GC,RP,
                           5,9,  % GC,LP,
                           6,8,  % CW,RP,
                           6,9,  % CW,LP,
                           7,8,  % CR,RP,
                           7,9,  % CR,LP,
                           6,7,  % CW,CR,
                           1,2   % FP,FW
                           ],2),
  Sat = false.



%
% Assembling bicycles
%
% Problem from R.L. Graham: "Combinatorial Scheduling Theory",
% in L. A. Steen (Ed.), Mathematics Today: "Twelve Informal Essays", 
% Springer-Verlag, New York, 1978, pp. 183-211.
%
% http://www.math.ucsd.edu/~ronspubs/78_15_combinatorial_scheduling.pdf
%
% The tasks:
% FP - Frame preparation which includes installation of the
%     front fork and fenders.
% FW - Mounting and aligning front wheel.
% BW - Mounting and aligning back wheel.
% DE - Attaching the derailleur to the frame.
% GC - Installing the gear cluster.
% CW - Attaching the chain wheel to the crank.
% CR - Attaching the crank and chain wheel to the frame.
% RP - Mounting right pedal and toe clip.
% LP - Mounting left pedal and toe clip.
% FA - Final attachments which includes mounting and adjusting
%      handlebars, seat, brakes, etc.
%
%
% Precedences:
%  Job     must be done after  job(s)
%  -----------------------------------------
%  FA                           FP,FW,BW,GC,DE
%  BW                           GC,DE
%  GC,CW                        DE
%  LP, RP                       CR,CW,GC
%  CR                           CW

%
% Also see:
% "A Quick and Gentle Guide to Constraint Logic Programming
%  via ECLiPSe", page 353ff.
%

% Note: In this problem instance we test two things:
%  - the effect of 
%    Graham's Rule 1, i.e. that there can be no idleness 
%    for a worker until his/her last task (allow_idle = false).
%  - increasing to 3 teams (num_worker = 3)

% Comments:
% According to Graham's paper this should lead to a finishing
% time of 39. However, using this model this increases the
% makespan to 33 (and it use just 2 if the teams anyhow).
% Perhaps I have missed some constraint in Graham's paper.
%
data('10c',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 10,
  NumWorkers = 3, % Increasing to 3 workers/team
  %            1  2  3  4  5  6  7  8  9 10
  %           FP FW BW DE GC CW CR RP LP FA
  Duration = [ 7, 7, 7, 2, 2, 2, 2, 8, 8,18],
  Resource = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 40, % optimal: 33
  AllowIdle = false, % Testing of Rule 1
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                           1,10, % FP,FA,
                           2,10, % FW,FA,
                           3,10, % BW,FA,
                           4,10, % DE,FA,
                           5,10, % GC,FA,
                           4,3,  % DE,BW,
                           5,3,  % GC,BW,
                           1,3,  % FP,BW,
                           4,5,  % DG,GC,
                           4,6,  % DG,CW,
                           5,8,  % GC,RP,
                           5,9,  % GC,LP,
                           6,8,  % CW,RP,
                           6,9,  % CW,LP,
                           7,8,  % CR,RP,
                           7,9,  % CR,LP,
                           6,7,  % CW,CR,
                           1,2   % FP,FW
                           ],2),
  Sat = false.


%
% Assembling bicycles
%
% Problem from R.L. Graham: "Combinatorial Scheduling Theory",
% in L. A. Steen (Ed.), Mathematics Today: "Twelve Informal Essays", 
% Springer-Verlag, New York, 1978, pp. 183-211.
%
% http://www.math.ucsd.edu/~ronspubs/78_15_combinatorial_scheduling.pdf
%
% The tasks:
% FP - Frame preparation which includes installation of the
%     front fork and fenders.
% FW - Mounting and aligning front wheel.
% BW - Mounting and aligning back wheel.
% DE - Attaching the derailleur to the frame.
% GC - Installing the gear cluster.
% CW - Attaching the chain wheel to the crank.
% CR - Attaching the crank and chain wheel to the frame.
% RP - Mounting right pedal and toe clip.
% LP - Mounting left pedal and toe clip.
% FA - Final attachments which includes mounting and adjusting
%      handlebars, seat, brakes, etc.
%
%
% Precedences:
%  Job     must be done after  job(s)
%  -----------------------------------------
%  FA                           FP,FW,BW,GC,DE
%  BW                           GC,DE
%  GC,CW                        DE
%  LP, RP                       CR,CW,GC
%  CR                           CW

%
% Also see:
% "A Quick and Gentle Guide to Constraint Logic Programming
%  via ECLiPSe", page 353ff.
%

% Notes: In this problem instance we test two things:
%  - the effect of 
%    Graham's Rule 1, i.e. that there can be no idleness 
%    for a worker until his/her last task (allow_idle = false).
%  - increasing to 3 teams (num_worker = 3)
%  - decreasing the duration for all tasks with 1 time unit.

%
% Results for 2 teams:
% - With Rule 1 (allow_idle = false) then there is a makespan of 34.
% - Without this rule (allow_idle = true) we lower it to 29.
% In comparison with the "normal" durations (and allow_idle = true)
% there is a makespan of 32.
%
data('10d',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 10,
  % Max number of workers/team that can be assigned (with some job): 6
  % (but it don't give better results than with 2 workers/team)
  NumWorkers = 2,
  %            1  2  3  4  5  6  7  8  9 10
  %           FP FW BW DE GC CW CR RP LP FA
  % duration = [ 7, 7, 7, 2, 2, 2, 2, 8, 8,18],
  Duration = [ 6, 6, 6, 1, 1, 1, 1, 7, 7,17],
  Resource = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 53, % (optimal: 34 when = false, 32 when allow_idle=true)
  AllowIdle = false, % Rule 1
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                            1,10, % FP,FA,
                            2,10, % FW,FA,
                            3,10, % BW,FA,
                            4,10, % DE,FA,
                            5,10, % GC,FA,
                            4,3,  % DE,BW,
                            5,3,  % GC,BW,
                            1,3,  % FP,BW,
                            4,5,  % DG,GC,
                            4,6,  % DG,CW,
                            5,8,  % GC,RP,
                            5,9,  % GC,LP,
                            6,8,  % CW,RP,
                            6,9,  % CW,LP,
                            7,8,  % CR,RP,
                            7,9,  % CR,LP,
                            6,7,  % CW,CR,
                            1,2   % FP,FW
                            ],2),
  Sat = false.

%
% Problem from R.L. Graham: "Combinatorial Scheduling Theory",
% in L. A. Steen (Ed.), Mathematics Today: "Twelve Informal Essays", 
% Springer-Verlag, New York, 1978, pp. 183-211.
%
% This problem is from page 194f to show how the critical 
% path method can yield a very bad schedule in some cases.
%
data(11,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 12,
  NumWorkers = 4,
  %           1  2  3  4  5  6  7  8  9 10 11 12
  %           A  B  C  D  E  F  G  H  I  J  K  L
  Duration = [1, 1, 1, 1,10,10,10, 3, 3, 3, 3,10],
  Resource = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 56, % optimal: 14
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                          1, 8,  % A,H
                          1, 9,  % A,I
                          1,10,  % A,J
                          1,11,  % A,K
                          8,12,  % H,L
                          9,12,  % I,L
                          10,12, % J,L
                          11,12  % K,L
                          ],2),
  Sat = false.


%
% Dinner party problem.
%
% Problem from
% Robert A. McGuigan: "Scheduling Problems and Bin Packing",
% from Applications of Discrete Mathematics, chapter 11,
% page 188ff
%
%  Task                   Time (minutes)
%  -------------------------------------
%  Decide guest list (GL)   15
%  Plan the menu (M)        30
%  Clean house (CH)         80
%  Purchase food (PF)       45
%  Cook food (CF)          125
%  Set table (ST)           15
%  Serve food (SF)          15
%
%  Precedences:
% 
%  Task    must be preceeded by   task(s)
%  -------------------------------------- 
%  Decide guest list (GL)          none
%  Plan the menu (M)               GL
%  Clean house (CH)                none
%  Purchase food (PF)              M
%  Cook food (CF)                  CH,PF
%  Set table (ST)                  CH,M
%  Serve food (SF)                 ST,CF
%
data(12,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 7,
  NumWorkers = 2,
  %            1  2  3  4   5  6  7
  %           GL  M CH PF  CF ST SF 
  Duration = [15,30,80,45,125,15,15],
  Resource = [ 1, 1, 1, 1,  1, 1, 1],
  MaxTime = 300, % optimal: 230
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                           1,2,  % GL, M,
                           2,4,  %  M,PF,
                           3,5,  % CH,CF,
                           4,5,  % PF,CF, 
                           3,6,  % CH,ST,
                           2,6,  %  M,ST,
                           6,7,  % ST,SF,
                           5,7   % CF,SF
                           ],2),
  Sat = false.



%
% Service of a plane.
%
% Problem from
% Joseph Malkevitch: "Is it on Time?" in 
% In Discrete Mathematics, November 1994.
% Pages 1, 9f,
% 
% http://dimacs.rutgers.edu/Publications/Modules/Module04-3/Nov94.pdf
%
% Tasks:
% T1 Unload passengers   (13 minutes)
% T2 Unload cargo        (10)
% T3 Refuel              (14)
% T4 Clean               (9)
% T5 Load new cargo      (15)
% T6 Load new passengers (18)
% T7 Late luggage        (4)
% T8 Load food           (7)
%
% Precedences
%
%   T1,T4
%   T2,T5
%   T4,T6
%   T5,T6
%   T6,T7
%   T6,T8  
%
% Note: 
%   - The article states that 50 is the optimal makespan,
%     but we got 55 here. (Note: If all the durations are
%     decreased by 1 then we also get 50. See below.)
%   - It doesn't say how many workers/team there should be.
%     I assume 2 teams (which gives optimal makespan). 
%
data(13,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 8,
  NumWorkers = 2,
  %            1  2  3  4  5  6  7  8
  Duration = [13,10,14, 9,15,18, 4, 7],
  % With these durations (each is 1 less) there is a 
  % makespan of 50.
  % duration = [12,9,13, 8,13,17, 3, 6],
  Resource = [ 1, 1, 1, 1, 1, 1, 1, 1],
  MaxTime = 90, % optimal: 55
  AllowIdle=true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                           1,4,
                           2,5,
                           4,6,
                           6,5,
                           6,7,
                           6,8
                           ],2),
  Sat = false.



%
% Perfect square placement problem.
%
% This problem instance use the flag collect_workers = true
% which requires that "near" workers must solve the tasks.
%
%
% From http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html
% size  = 12;
% n = 14;
% a = [1,1,1,1,2,3,3,3,5,6,6,8];
data(14,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 12,
  NumWorkers = 14,
  %            1  2  3  4  5  6  7  8  9 10 11 12
  Duration = [ 1, 1, 1, 1, 2, 3, 3, 3, 5, 6, 6, 8],
  Resource = [ 1, 1, 1, 1, 2, 3, 3, 3, 5, 6, 6, 8],
  MaxTime = NumWorkers, % optimal: 14
  AllowIdle = true,
  CollectWorkers = true, % This is what we test here
  DoPrecedences = false,
  Precedences = [],
  Sat = true.


%
% Perfect square placement problem.
%
% This problem instance use the flag collect_workers = true
% which requires that "near" workers must solve the tasks.
%
% Problem 1 from 
% http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob009/results
% size = 21;
% n = 112;
% a = [2,4,6,7,8,9,11,15,16,17,18,19,24,25,27,29,33,35,37,42,50];
% This is a hard problem.
%
data('14b',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 21,
  NumWorkers = 112,
  Duration = [2,4,6,7,8,9,11,15,16,17,18,19,24,25,27,29,33,35,37,42,50],
  Resource = Duration,
  MaxTime = NumWorkers, % optimal: 112
  AllowIdle = true,
  CollectWorkers = true,
  DoPrecedences = false,
  Precedences = [],
  Sat = true.



%
% Perfect square placement problem.
%
% This problem instance use the flag collect_workers = true
% which requires that "near" workers must solve the tasks.
%
%
% From http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html
% size  = 12;
% n = 14;
% a = [1,1,1,1,2,3,3,3,5,6,6,8];
%
data('14c',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 8,
  NumWorkers = 4,
  %            1  2  3  4  5  6  7  8
  Duration = [ 2, 2, 2, 2, 2, 2, 2, 2],
  Resource = [ 2, 2, 2, 2, 2, 2, 2, 2],
  MaxTime = 8, % optimal: 8
  AllowIdle = true, % false,
  CollectWorkers = true,
  DoPrecedences = false,
  Precedences = [],
  Sat = true.


%
% Problem from R.L. Graham: "Combinatorial Scheduling Theory",
% in L. A. Steen (Ed.), Mathematics Today: "Twelve Informal Essays", 
% Springer-Verlag, New York, 1978, pp. 183-211.
%
% Problem from page 189.
%
data(15,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 13,
  NumWorkers = 6,
  %           A B C D E F G H I J K L M
  Duration = [7,4,5,6,5,3,7,6,5,5,4,3,12],
  Resource = [1,1,1,1,1,1,1,1,1,1,1,1, 1],
  MaxTime = 60, % optimal: 12
  AllowIdle = false, % Rule 1: no idle worker
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Bin packing as a scheduling problem.
%
% Here we see the bin packing as a scheduling problem (with
% assignments) as follows:
%   - the number of things to pack is the number of jobs
%   - the capacity of each bin is the number of workers
%   - the weight/height of each thing is the resource
%   - all durations is set to 1
%   - max_time is the number of workers
%   - the minimum number of bins to use (to be minimized) 
%     is then - of course - the makespan.
% 
% Cf http://www.hakank.org/minizinc/bin_packing_me.mzn
% where I have took this example.
%
data(16,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 20, % num_stuff = 20,
  NumWorkers = 30,  % bin_capacity = 30,
  Duration = [1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  Resource = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
  MaxTime = 20, % optimal: 7
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.



%
% Bin packing as a scheduling problem.
%
% Here we see the bin packing as a scheduling problem (with
% assignments) as follows:
%   - the number of things to pack is the number of jobs
%   - the capacity of each bin is the number of workers
%   - the weight/height of each thing is the resource
%   - all durations is set to 1
%   - max_time is the number of workers
%   - the minimum number of bins to use (to be minimized) 
%     is then - of course - the makespan.
%     
% 
% Cf http://www.hakank.org/minizinc/bin_packing_me.mzn
% where I have took this example.
% 
% This problem instance is via
% http://yetanothermathprogrammingconsultant.blogspot.com/2011/08/bin-packing.html
% and is "critical" to the result in
% "Bin Packing, What is It?"
% http://www.developerfusion.com/article/5540/bin-packing/
% where the minimum bins are 19,
% whereas Erwin K's code have 17 as the optimal result.
%
% This is a hard problem!
data('16b',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 45, % num_stuff = 45,
  NumWorkers = 80,  % bin_capacity = 80,
  Duration = [1 : _I in 1..NumJobs],  
  Resource = [ 26, 57, 18,  8, 45,
               16, 22, 29,  5, 11,
               8, 27, 54, 13, 17,
               21, 63, 14, 16, 45,
               6, 32, 57, 24, 18,
               27, 54, 35, 12, 43,
               36, 72, 14, 28,  3,
               11, 46, 27, 42, 59,
               26, 41, 15, 41, 68],
  MaxTime = 45, % optimal: 17
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Bin packing as a scheduling problem.
%
% Here we see the bin packing as a scheduling problem (with
% assignments) as follows:
%   - the number of things to pack is the number of jobs
%   - the capacity of each bin is the number of workers
%   - the weight/height of each thing is the resource
%   - all durations is set to 1
%   - max_time is the number of workers
%   - the minimum number of bins to use (to be minimized) 
%     is then - of course - the makespan.
% 
% Cf http://www.hakank.org/minizinc/bin_packing_me.mzn
% where I have took this example.
%
% This is hard!
%
data('16c',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 22, % num_stuff = 20,
  NumWorkers = 250,  % bin_capacity = 250,
  Duration = [1 : _ in 1..NumJobs],  
  Resource = [42,69,67,57,93,90,38,36,45,42,33,79,27,57,44,84,86,92,46,38,85,33],
  MaxTime = 250, % optimal: 6
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Bin packing as a scheduling problem.
%
% Here we see the bin packing as a scheduling problem (with
% assignments) as follows:
%   - the number of things to pack is the number of jobs
%   - the capacity of each bin is the number of workers
%   - the weight/height of each thing is the resource
%   - all durations is set to 1
%   - max_time is the number of workers
%   - the minimum number of bins to use (to be minimized) 
%     is then - of course - the makespan.
% 
% Problem instance from
% Robert A. McGuigan: "Scheduling Problems and Bin Packing",
% from Applications of Discrete Mathematics, chapter 11,
% page 198
%
data('16d',NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 25, % num_stuff = 0,
  NumWorkers = 100,  % bin_capacity = 100,
  Duration = [1 : _ in 1..NumJobs],  
  %           1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  Resource = [7,7,7,7,7,12,12,12,12,12,15,15,15,36,36,36,36,36,52,52,52,52,52,52,52],
  MaxTime = NumJobs, % optimal: 7
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Scheduling problem.
%
% Problem from 
% http://en.wikipedia.org/wiki/Gantt_chart
%
data(17,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 7, 
  NumWorkers = 2,  
  % For simplicity I round the values to nearest integer
  %           A B C D E F G
  %           1 2 3 4 5 6 7
  Duration = [4,5,5,6,5,4,5],
  Resource = [1,1,1,1,1,1,1],
  MaxTime = 34, % optimal 19
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                 1,3, % A,C,
                 1,4, % A,D,
                 2,5, % B,E,
                 3,5, % C,E,
                 4,6, % D,F,
                 6,7  % E,G,
                 ],2),
  Sat = false.



%
% Scheduling problem.
%
% Problem from "CHIP Example Code", page 5
% The Ship Loading Example.
% """
% This example shows how to solve a scheduling problem where 
% cumulative and precedence constraints occur using either the 
% CHIP V5 Prolog, C Library or C++ Library versions. The problem 
% is to find a schedule that minimizes the time to unload and to 
% load a ship.
% The work consists of 34 unloading/loading tasks. Each task 
% requires a number of men and each has a given duration i.e. 
% task1 requires 3 men and will take 4 hours to complete. We
% know that we have a maximum of 8 men for work and the total 
% work should not exceed 100 hours.
% 
% ...
% When executed the CHIP V5 examples produce the following output. 
% The solution given assigns a start date of 0 for task1, 3 for 
% task2, etc. task29 which has a duration of 1 hour should start in 
% hour 65 (hence an optimum solution of 66 hours).
%    [0, 3, 7, 3, 14, 19, 11, 21, 25, 28, 30, 33, 35, 30, 36, 
%     36, 39, 41, 43, 44, 43, 44, 46, 50, 55, 60, 62, 63, 65, 
%     57, 61, 57, 58, 60]
% 
% """
data(18,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 34, 
  NumWorkers = 8,  
  %           1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7  18 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
  Duration = [3,4,4,6,5,2,3,4,3,2,3,2,1,5,2,3,2,  2,1,1,1,2,4,5,2,1,1,2,1,3,2,1,2,2],
  Resource = [4,4,3,4,5,5,4,3,4,8,4,5,4,3,3,3,6,  7,4,4,4,4,7,8,8,3,3,6,8,3,3,3,3,3],
  MaxTime = 87, % optimum: 66
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                 1,2,
                 1,4,
                 2,3,
                 3,5,
                 3,7,
                 4,5,
                 5,6,
                 6,8,
                 7,8,
                 8,9,
                 9,10,
                 9,14,
                 10,11,
                 10,12,
                 11,13,
                 12,13,
                 13,15,
                 13,16,
                 14,15,
                 15,18,
                 16,17,
                 17,18,
                 18,19,
                 18,20,
                 18,21,
                 19,23,
                 20,23,
                 21,22,
                 22,23,
                 23,24,
                 24,25,
                 25,26,
                 25,30,
                 25,31,
                 25,32,
                 26,27,
                 27,28,
                 28,29,
                 30,28,
                 31,28,
                 32,33,
                 33,34
                 ],2),
  Sat = false.


%
% Rectangle placement problem.
%
% From the presentation
% Francois Clautiaux:
% "Exact methods for rectangle placement problems"
% http://contraintes.inria.fr/CPAIOR08/BPPC/Clautiaux.pdf
% page 5
% 
% Placing 6 rectangles:
%    A      B      C      D      E      F
%   (4,4), (8,4), (4,8), (4,4), (6,4), (8,4)
% into a (15,15) rectangle.
%
data(19,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 6,
  NumWorkers = 15, % height
  %           A B C D E F
  %           1 2 3 4 5 6
  Duration = [4,4,8,4,4,4],  % height
  Resource = [4,8,4,4,6,8],  % width
  MaxTime = 15, % width. optimal 12
  AllowIdle = true,
  CollectWorkers = true,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.

%
% Grilling hamburgers problem.
%
% From Edward Sitarski: "When Do We Eat?"
% http://math.ca/crux/v27/n2/public_page124-135.pdf
% """
% Let's say we need to cook some hamburgers on a barbecue.
% Each hamburger has two sides (just in case there was any doubt!), 
% and each side takes 5 minutes to cook. Only one side of the hamburger 
% can be cooked at a time (no "George Foreman" appliances here). 
% Our barbecue is small, and only has two grills to cook the hamburgers 
% [...].
% 
% Let's say we have three hamburgers to cook. The goal is to cook all of
% the hamburgers in the shortest possible time. Simple, right? Because I am so
% nice (or maybe not, as you shall see later), I am going to give you a solution
% to the problem:
%
%         5  10  15  20
%    G1  H1  H1  H3  H3
%    H2  H2  H2
% 
% [...] There are two rows: one for each grill (appropriately called 
% G1 and G2). The columns show the cooking time in minutes. The 
% table shows when each hamburger is cooking on each grill. Each 
% hamburger has the name H1, H2 and H3. The names must appear twice 
% because each hamburger must be cooked on two sides. Since 
% we cannot cook both sides of a hamburger at the same time, a hamburger
% cannot appear twice in the same column. My solution shows a total cooking
% time of 20 minutes. Can you do better? 
% """
%
% Via Mind Your Decisions
% http://mindyourdecisions.com/blog/2012/01/02/answer-to-puzzle-leaving-work-quickly
%
% (There are 48 solution to this problem, 24 with symmetry breaking)
%
data(20,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 6,
  NumWorkers = 2,
  %           H1 H1 H2 H2 H3 H3
  %            1  2  3  4  5  6
  Duration = [ 5, 5, 5, 5, 5, 5],
  Resource = [1,1,1,1,1,1],
  MaxTime = 30, % optimal 15
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([ 
                 1,2,
                 3,4,
                 5,6
                 ],2),
  Sat = false.


%
% Problem from 
% Jacek Blazewicz, Klaus H. Ecker, Erwin Pesch, Gunter Schmidt
% Jan Weglarz: "Handbook of Scheduling", 
% page 61
%
data(21,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 8,
  NumWorkers = 3,
  %           1 2 3 4 5 6 7 8
  Duration = [3,4,1,2,1,2,3,2],
  Resource = [1,1,1,1,1,1,1,1],
  MaxTime = 10, % optimal: 8
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = true,
  Precedences = chunks_of([
                           1,3,
                           2,3,
                           3,6,
                           3,7,
                           4,8,
                           5,8
                           ],2),
  Sat = false.


%
% Problem from 
% 
% Jean-Louis Lauriere ALICE-paper 
% "A Language and a Program for Stating and Solving Combinatorial Problems", 
% page 104
% """
% Example 1. Nine jobs of duration (13,15,9,6,6,8,6,3,2) must be executed
% before the deadline 18.
% """
%
data(22,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 9,
  NumWorkers = 18,
  Resource = [13,15,9,6,6,8,6,3,2],
  Duration = [ 1, 1,1,1,1,1,1,1,1],
  MaxTime = 18, % optimal 4
  AllowIdle = true,
  CollectWorkers = true,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.


%
% Problem from 
% 
% Jean-Louis Lauriere ALICE-paper 
% "A Language and a Program for Stating and Solving Combinatorial Problems", 
% page 105
% """
% Example 2. First case ... In rods of length 396 must be cut in 11 different
% type of bits.
%   type      1   2   3   4   5   6   7   8   9  10  11  
%   length  285 188 126 115 113  75  60  51  12  10   9
%   amount    1   6  18   3   3   1   1   1   3   6  12
% """
%
data(23,NumJobs,NumWorkers,Duration,Resource,MaxTime,AllowIdle,CollectWorkers,Precedences,DoPrecedences,Sat) =>
  NumJobs = 55,
  NumWorkers = 20,
  Duration = [285,
              188,188,188,188,188,188,
              126,126,126,126,126,126,126,126,126,126,126,126,126,126,126,126,126,126,
              115,115,115,
              112,112,112,
              75, 
              60, 
              51, 
              12,12,12, 
              10,10,10,10,10,10,  
              9,9,9,9,9,9,9,9,9,9,9,9
          ],
  Resource = [ 1 : _ in 1..NumJobs],
  MaxTime = 365,  % optimal 285  
  AllowIdle = true,
  CollectWorkers = false,
  DoPrecedences = false,
  Precedences = [],
  Sat = false.