У меня есть рабочая модель Miniznic для планирования индивидуальных уроков для 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
(Примечание: ложные пробелы помечены .
; то же самое, что и недоступно).
Результатом будет массив промежутков [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
Как я могу сформулировать такой алгоритм в Minizinc?
Спасибо!