Search code examples
constraintsscheduled-tasksminizinc

Schedule minizinc no overlapping

I want to do a schedule with no overlapping only 1 teacher can be booked at 1 timeslot. I want to create a 2darray like teachers a rows and timeslot is coloumns.

Solution

  • The general constraints to use for these kind of constraints ("something should be distinct") are the two global constraints all_different or alldifferent_except_0.

    Note: I changed to 3 teachers, 3 timeslots, and 5 presentations to make a more general point of using alldifferent_except_0, since there can be assignments where there are no teacher/timeslot for a presentation.

    Also, I'm not sure I would use the specific representation as you did, since it the representation depends on further constraints (if any) in the model.

    Here are some approaches that might be useful.

    1) Simple model with just a "timetable" matrix

    If you only want to assign T teachers, TS timeslots, and P presentations with no further constraints, then a single constraint "all_different_except_0" on a timetable matrix will suffice (together with a sum explained below). The dimension of "timetable" is T x TS (Teachers x Timeslots) where we assign the presentation, or 0 if there is no presentation for this teacher and timeslot.

    include "globals.mzn"; 

set of int: Timeslots = 1..3;
set of int: Teachers = 1..3; 
set of int: Presentations = 1..5;

solve satisfy;

% Decision variables
array[Teachers, Timeslots] of var {0} union Presentations: timetable;

constraint 
    alldifferent_except_0(array1d(timetable))

    % ensure that there are 5 assigned presentations
   /\ sum([timetable[t,ts]>0 | t in Teachers, ts in Presentations]) = card(Presentations)
;

% output [....];

    The drawback of this model is that it's not easy to state further constraints that might be needed, and also that we have to count the number of non-0 assignments in the "timetable" matrix to ensure that there are exactly 5 presentations assigned.

    So we will expand with more decision variables.

    2) Adding decision variables

    This model connects the original presentation with the "timetable" matrix and its constraint shown above. This means that we can keep the constraint on "timetable" to ensure unicity and we can work with constraint on the other decision variables as well. Here's a model with the two original arrays "presentation_teacher" and "presentation_time" and their constraints.

     include "globals.mzn"; 
 set of int: Timeslots = 1..3;
 set of int: Teachers = 1..3; 
 set of int: Presentations = 1..5;

 % Decision variables
 % Which teacher has this presentation
 array[Presentations] of var Teachers: presentation_teacher;

 % Which timeslot for this presentation
 array[Presentations] of var Timeslots: presentation_time;

 % Which combination of teacher and timeslot for a presentation, if any
 array[Teachers, Timeslots] of var {0} union Presentations: timetable;
 solve satisfy;

 constraint

   alldifferent_except_0(array1d(timetable))
   % This constraint is not needed now
   % /\ sum([timetable[t,ts]>0 | t in Teachers, ts in Presentations]) = card(Presentations)

   /\ % connect timetable and presentation_teacher and presentation_time
  forall(p in Presentations) (
     timetable[presentation_teacher[p],presentation_time[p]] = p
  )
 ;

    The constraint "forall(p in Presentations) ( ... ) " connects the two representations: the "timetable" representation and the two added arrays.

    3) Alternative version

    An alternative version of ensuring distinct timeslots and presentations for the teachers is to add constraints on the "presentation_teacher", "presentation_time". This don't really need a timetable matrix so it's skipped here. (One can add these constraints with the timetable approach might be faster.)

    include "globals.mzn"; 
set of int: Timeslots = 1..3;
set of int: Teachers = 1..3; 
set of int: Presentations = 1..5;

% Decision variables

% Which teacher has this presentation
array[Presentations] of var Teachers: presentation_teacher;

% Which timeslot for this presentation
array[Presentations] of var Timeslots: presentation_time;

solve satisfy;

constraint 
  % variant A
  forall(t in Teachers) (
      % the time for this teacher is distinct (or 0)
     alldifferent_except_0([presentation_time[p] * (presentation_teacher[p]=t) | p in Presentations])
  )

 /\ 
 % variant B
 forall(t in Teachers) (
    % combination of (time + teacher) for this teacher is unique
    alldifferent([presentation_time[p]+(presentation_teacher[p]*card(Presentations)) | p in Presentations])
 )

;

    This model has two variants, where the first ("A") use alldifferent_except_0 to ensure that the presentations for each teacher are distinct.

    For each teacher it loops through all the presentations ("p") and picks those time assigned for "this" teacher and ensures that they are distinct.

    The second variant ("B") is kind of a hack, though quite useful sometimes: It builds an list of integers for which the teacher is assigned ( time + teacher_id * number of presentations) and ensure that these are distinct.

    Since this model don't have an explicit timetable one have to extract the timetable in the output. Here is one way:

    output [
  "Teacher " ++ show(t) ++ " has these presentations" ++ show([p | p in Presentations where fix(presentation_teacher[p]) = t]) ++ "\n"
  | t in Teachers
]
;

    As mentioned above, the representation of the model (which decision variables to select) depends much on what one want to do further.