Minizin c Объективная функция для пробелов в расписании - PullRequest
Новая
       100

Minizin c Объективная функция для пробелов в расписании

1 голос
/ 19 июня 2020

У меня есть рабочая модель Minizni c для планирования индивидуальных занятий 1 профессора с n студентами ( Задача оптимизации модели планирования отдельных уроков ). Модель учитывает доступность (жесткое ограничение) и временные предпочтения (целевая функция) профессора и студентов.

Теперь я хочу расширить модель и оптимизировать расписание таким образом, чтобы промежутки между уроками были сведены к минимуму.

Пример: 

  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

где 

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

Очевидно, что p в слоте 1 не следует рассматривать как пробел. Точно так же слоты 9 и 10 тоже не имеют зазоров. Устраняя все ложные пробелы, Schedule должен, наконец, выглядеть как массив Real Gaps (Примечание: false пробелы отмечены .; то же, что недоступно ).

Результатом будет массив [2, 1, 1, 1, 1] промежутков (для каждого промежутка, показывающего количество слотов, на которые он длится). На основе такого массива затем можно было бы, например, сформулировать цель минимизировать общие промежутки времени.

В ruby Я смог сформулировать алгоритм, который делает то, что я хочу: 

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

Как в Minizin сформулировать такой алгоритм c?

Спасибо!

1 Ответ

2 голосов
/ 22 июня 2020

Один из способов сделать это в MiniZin c - это расширить модель на Задача оптимизации модели планирования отдельных уроков следующим образом:

Первоначально вычислить teacher_free как слоты, в которых учитель недоступен, объединены с соседними слотами, где не проводится урок (это делается в два этапа, начиная слева teacher_free_left и справа teacher_free_right, соответственно, а затем объединяя результаты в форму teacher_free).

На следующем этапе real_gap рассчитывается как интервалы, в которых учитель не свободен и урок не проходит.

В задаче штраф за real_gap равен затем вводится как (k2 - вес штрафа за разрыв): 

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);

Здесь все другие расширения модели (с некоторыми дополнительными комментариями): 

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]));
...