minizincobjective-function

Minizinc Objective Function For Gaps in Schedule

I have a working Miniznic model to schedule individual lessons of 1 professor having n students (Optimization Problem of a Single Lessons Scheduling Model). The model considers availability (hard constraint) and the time preferences (objective function) of the professor as well as of the students.

Now, I want to extend the model and optimize the schedule such that gaps between lessons are minimized.

Example:

  Schedule  : p L p p L L . . p p L L p L L p L p p . L p L L . L p L
  Real Gaps : . L p p L L . . . . L L p L L p L . . . L p L L . L p L

where

 `p` =  0 == Teacher available, but no Lesson
 `L` =  1 == Teacher gives lesson (to student)
 `.` = -1 == Teacher not available

Obviously, the p in slot 1 must not be counted as a gap. Similarly, slots 9 and 10 are no gaps, neither. Eliminating all false gaps, the Schedule should finally look like the Real Gaps array (Note: false gaps are marked with .; the same as not available).

The result would be a gap array [2, 1, 1, 1, 1] (for each gap showing the number of slots it lasts). Based on such an array one could then e.g. formulate an objective to minimize the overall gap slots.

In ruby I was able to formulate an algorithm that does what I want:

def gap_array(schedule_arr)
  # initialize variables
  start_search = false              # flag for break start
  break_slots  = 0                  # counter of break slots
  res_arr      = []                 # resulting array
  schedule_arr.each do |slot|
    if slot == 1                    # start watching for break
      start_search = true
    end
    #
    if start_search                 
      if    slot == 0               # == break
        break_slots += 1
      elsif slot == 1               # == consecutive lesson slot
        if break_slots > 0          # number of break_slots > 0
          res_arr.append(break_slots)
          break_slots = 0
        end
      else                          # == not available
        break_slots  = 0            # any break so far is discarded
        start_search = false         
      end
    end
  end
  return res_arr
end

How can I formulate such an algorithm in Minizinc?

Thanks!

Solution

  • One way to this in MiniZinc would be to extend the model at Optimization Problem of a Single Lessons Scheduling Model in the following way:

    Initially calculate teacher_free as the slots where the teacher is not available combined with adjacent slots where no lesson takes place (this is done in two steps, going from the left teacher_free_left and the right teacher_free_right, respectively, and then combining the results to form teacher_free).

    In the next step the real_gap is calculated as slots where the teacher is not free and no lesson takes place.

    In the objective a penalty term for real_gap is then introduced like (k2 being the gap penalty weight):

    int: k2 = 1;
var int: obj = sum(s in STUDENT, t in TIME)
    (active[s,t] * (prio_time[s,t] + k*prioTeacher_time[t])) - k2*sum(real_gap);

    Here all the other extensions to the model (with some further comments):

    array[DAY,SLOT]           of var 0..1: lesson = array2d(DAY, SLOT, [sum(s in STUDENT)(active[s,time(d,z)]) | d in DAY, z in SLOT]);
array[DAY,SLOT]           of var 0..1: teacher_free_left;
array[DAY,SLOT]           of var 0..1: teacher_free_right;
array[DAY,SLOT]           of var 0..1: teacher_free;
array[DAY,SLOT]           of var 0..1: real_gap;

predicate equals_and(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z <= x /\ z <= y /\ z >= x + y - 1);

predicate equals_or(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z >= x /\ z >= y /\ z <= x + y);

% calculate teacher free left
%    first slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (left slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_left_temp;

constraint forall(d in DAY)
    (teacher_free_left_temp[d,1]=1-lesson[d,1]);
    
constraint forall(d in DAY, z in 2..maxSlots)
    (equals_and(teacher_free_left_temp[d,z], teacher_free_left[d,z-1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_left[d,z], 1 - bool2int(z in teacher[d]), teacher_free_left_temp[d,z]));
    
% calculate teacher free right
%    last slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (right slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_right_temp;

constraint forall(d in DAY)
    (teacher_free_right_temp[d,maxSlots]=1-lesson[d,maxSlots]);
    
constraint forall(d in DAY, z in 1..maxSlots-1)
    (equals_and(teacher_free_right_temp[d,z], teacher_free_right[d,z+1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_right[d,z], 1 - bool2int(z in teacher[d]), teacher_free_right_temp[d,z]));

% teacher free when teacher free left or teacher free right
constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free[d,z], teacher_free_left[d,z], teacher_free_right[d,z]));

% real gap when teacher not free and no lesson
constraint forall(d in DAY, z in SLOT)
   (equals_and(real_gap[d,z], 1-teacher_free[d,z], 1-lesson[d,z]));