MiniZinc не находит решение проблемы планирования

Question

У меня проблема с поиском решения с помощью MiniZinc.

Задача: Необходимо составить график смен для сотрудников. В один день есть три смены: дневная (D), вечерняя (E) и ночная (N). Необходимо составить оптимальный график, по возможности избегая нежелательных ситуаций:

• Избегайте одиночных смен (одна смена между двумя перерывами)

• Избегайте одиночных перерывов (смена, перерыв, смена)

• Избегайте двойных перерывов (сдвиг, разрыв, разрыв, смещение)

• После ночной смены должен быть полный выходной (три перерыва подряд)

Чтобы найти решение, я минимизирую количество нежелательных ситуаций. Когда я начинаю расчет, MiniZinc отображает несколько промежуточных вариантов, но не находит окончательного решения.

Можно ли как-то оптимизировать расчеты?

include "regular.mzn"; 
int: n = 21;   
int: m = 6;

set of int: D = 1..n;
set of int: E = 1..m;

% Number of employees per shift
                         %|Sun    |Mon    |Tue      |Wen      |Thur   |Fri     |Sat    |
array[D] of int: SHIFTS = [2, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1];
                         /*2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1,
                           2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1,
                           2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2];*/

% The range of the number of shifts per employee for the period ([|from, to)                         
array[E, 1..2] of int: DC_SHIFTS = [|0, 10 %emp1
                                    |0, 10 %emp2
                                    |0, 10 %emp3
                                    |0, 10 %emp4
                                    |0, 10 %emp5
                                    |0, 10 %emp6
                                    |];

%-------------------------------------------------
% Variables
%-------------------------------------------------

array[E, D] of var 1..4: X;
% Counters of avoidable situations
var int: OS_PENALTY; % break, shift, break (single shift)
var int: NS_PENALTY; % night shift, not break, not break, not break (full day off after a night shift)
var int: DS_PENALTY; % shift, break, break, shift (two breaks between shifts)
var int: OO_PENALTY; % shift, break, shift (one break between shifts)

%-------------------------------------------------
% Constraints
%-------------------------------------------------

constraint
  forall(d in D)(
      sum(e in E)(bool2int(X[e, d] != 4)) = SHIFTS[d]
  );

constraint
  forall(e in E)(
      sum(d in D)(bool2int(X[e, d] != 4)) >= DC_SHIFTS[e, 1]
      /\
      sum(d in D)(bool2int(X[e, d] != 4)) < DC_SHIFTS[e, 2]
  );

constraint
  forall(d in D)(
      if d mod 3 = 1 then forall(e in E)(X[e, d] = 1 \/ X[e, d] = 4) else
      if d mod 3 = 2 then forall(e in E)(X[e, d] = 2 \/ X[e, d] = 4) else
      forall(e in E)(X[e, d] = 3 \/ X[e, d] = 4) endif endif
  );


NS_PENALTY = sum(e in E, d in D where d < max(D) - 2)(bool2int(
    X[e, d] = 3 \/ (X[e,d+1] != 4 /\ X[e,d + 2] != 4 /\ X[e,d + 3] != 4)
));

DS_PENALTY = sum(e in E, d in D where d < max(D) - 2)(bool2int(X[e, d] != 4 \/ X[e, d + 1] = 4 \/ X[e, d + 2] = 4 \/ X[e, d + 3] != 4));

OS_PENALTY = sum(e in E, d in D where d < max(D) - 1)(bool2int(X[e, d] = 4 /\ X[e, d + 1] != 4 /\ X[e, d + 2] = 4));

OO_PENALTY = sum(e in E, d in D where d < max(D) - 1)(bool2int(X[e, d] != 4 \/ X[e, d + 1] = 4 \/ X[e, d + 2] != 4));

%-------------------------------------------------
% Solve
%-------------------------------------------------

solve minimize OS_PENALTY + NS_PENALTY + DS_PENALTY + OO_PENALTY;

%-------------------------------------------------
% Output
%-------------------------------------------------

array[1..4] of string: rest_view = ["D", "E", "N", "-"];

output 
[ 
   rest_view[fix(X[e, d])] ++
   if d = n then "\n" else "" endif
   | e in E, d in D
];

Answer 1

Я предлагаю следующие изменения в вашей модели:

Изменить объявление X в array[E, D] of var 0..1: X; где 0 означает сломать и 1 сдвиг. Будь то дневная, вечерняя или ночная смена обрабатываются в секции вывода, где результаты преобразуются для отображения типа смены, например if fix(X[e, d]) == 0 then "-" else rest_view[1 + (d-1) mod 3] endif,

Перепишите ограничения, используя глобальные переменные, такие как:

import "globals.mzn"; 
constraint
  forall(d in D)(
      exactly(SHIFTS[d], col(X, d), 1)
      %sum(e in E)(bool2int(X[e, d] != 0)) = SHIFTS[d]
  );

constraint
  forall(e in E)(
      global_cardinality_low_up(row(X, e), [1], [DC_SHIFTS[e, 1]], [DC_SHIFTS[e, 2] - 1])
      %sum(d in D)(bool2int(X[e, d] != 0)) >= DC_SHIFTS[e, 1]
      %/\
      %sum(d in D)(bool2int(X[e, d] != 0)) < DC_SHIFTS[e, 2]
  );

%constraint
%  forall(d in D)(
%      if d mod 3 = 1 then forall(e in E)(X[e, d] = 1 \/ X[e, d] = 4) else
%      if d mod 3 = 2 then forall(e in E)(X[e, d] = 2 \/ X[e, d] = 4) else
%      forall(e in E)(X[e, d] = 3 \/ X[e, d] = 4) endif endif
%  );

Перепишите штрафы как:

NS_PENALTY = sum(e in E, d in 1..n - 3 where d mod 3 = 0)(bool2int(
    X[e, d] = 1 /\ (sum(i in 1..3)(X[e,d+i]) > 0)
));

DS_PENALTY = sum(e in E, d in 1..n - 3)(bool2int(X[e, d] != 0 /\ X[e, d + 1] = 0 /\ X[e, d + 2] = 0 /\ X[e, d + 3] != 0));

OS_PENALTY = sum(e in E, d in 1..n - 2)(bool2int(X[e, d] = 0 /\ X[e, d + 1] != 0 /\ X[e, d + 2] = 0));

OO_PENALTY = sum(e in E, d in 1..n - 2)(bool2int(X[e, d] != 0 /\ X[e, d + 1] = 0 /\ X[e, d + 2] != 0));