Миницинк: создать корректный сдвиг

Question

Надеюсь, что кто-то может помочь мне в этом!

Первоначальная проблема заключается в создании действительных сдвигов, как описано ниже:

У меня есть массивы, подобные этому [m, m, m, o, o, l, l, m, m, m, l, m, m, m] с фиксированной длиной (S), где m - работа, o - офис, и l свободен. Мне нужно убедиться, что по крайней мере каждые 6 м у меня есть два л вместе (11). O не считается работой или свободным. Примеры:

mmlmmlmmmll is not valid (7 ms without two ls)
mmlmmlmmll is valid
mmomomommll is valid

Я пытался создать массив с 0 (для ls) и 1 (для мс), но удалив из массива все o и непоследовательные ls. Таким образом, для приведенных выше примеров было бы:

mmlmmlmmmll -> 111111100
mmlmmlmmll -> 11111100
mmomomommll -> 11111100

Таким образом, я мог бы использовать ограничение slip_sum или at_least для его решения. Однако мне не удается создать этот новый массив, так как он будет иметь размер, отличный от исходного (S). Допустимым вариантом является заполнение в конце 0 оставшимися слотами до S.

Любая помощь приветствуется

Редактировать. Это код до сих пор:

enum TypeOfShift = {l,m,o};
enum Staff = {John, Mike, Mary};
array[Staff, 1..30] of TypeOfShift: Roster=[|
m,  m,  m,  l,  l,  o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  l|
l,  l,  l,  l,  l,  m,  m,  m,  o,  o,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  m,  m|
m,  m,  l,  l,  m,  o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  l,  l,  l,  m|];
array[Staff, 1..30] of var 0..2: RosterCalculated = array2d(Staff, 1..30,[if (Roster[i,d]==l) then 0 else (if (Roster[i,d]==o) then 2 else 1 endif) endif | i in Staff, d in 1..30]);
output[if (d==1) then "\n\(i) " ++ " " ++ show(RosterCalculated[i,d]) ++ " " else show(RosterCalculated[i,d]) ++ " " endif | i in Staff, d in 1..30];

Answer 1

Этот ответ предоставляет простое и эффективное решение для проблемы, указанной в вопросе, то есть как определить, является ли данный сдвиг действительным или нет . [Обратите внимание, что в этом случае нет необходимости (на самом деле, это контрпродуктивно) для объявления содержимого любого массива как var $T].

---

Один из вариантов:

• определяет начальную позицию всех ll в массиве (массив double_l_pos)
• определяет позицию каждого o в массиве (массив has_o)
• определяет совокупное число o в массиве с начала (массив cum_has_o)
• фиксирует положение всех ll, так что он игнорирует любые o, предшествующие ему(массив fixed_double_l_pos)
• определяет расстояние между всеми ll начальными позициями (массив double_l_distance)
• , при этом значение расстояния не должно превышать 6

Пример:

include "globals.mzn";

enum TypeOfShift = {l,m,o};
enum Staff = {John, Mike, Mary};

array[Staff, 1..30] of TypeOfShift: Roster=[|
    m,  m,  m,  l,  l, o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  l|
    l,  l,  l,  l,  l,  m,  m,  m,  o,  o,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  m,  m|
    m,  m,  l,  l,  m,  o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  l,  l,  l,  m|];

constraint forall (s in Staff)
(
    let {
        array[int] of TypeOfShift: shifts = [Roster[s, i] | i in 1..30];
        array[int] of int: double_l_pos = [ i - 1 | i in index_set(shifts) where
                                                    i > 1 /\
                                                    shifts[i-1] == l /\
                                                    shifts[i] == l];
        array[int] of int: has_o = [ if el == o then 1 else 0 endif | el in shifts ];
        array[int] of int: cum_has_o = [
                              sum ( j in index_set(shifts) where j <= i) ( has_o[j] )
                              | i in index_set(has_o) ];
        array[int] of int: fixed_double_l_pos = [ pos - cum_has_o[pos] | pos in double_l_pos ];
        array[int] of int: double_l_distance = [fixed_double_l_pos[1]] ++
            [fixed_double_l_pos[i] - fixed_double_l_pos[i-1] - 1 - 1
            | i in index_set(fixed_double_l_pos) where i > 1];
    } in
        forall(dist in double_l_distance) (
            dist <= 6
        )
);

solve satisfy;

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

---

Добавление: поскольку это проблема реестра , вы можете прочитать список и список по вызову моделей в репозитории MiniZinc. Эти файлы могут содержать лучшие подходы для решения вашей проблемы.

Answer 2

Этот новый ответ имеет дело с более общей проблемой генерации действительного расписания. В этом случае мы имеем дело с переменными решения , поэтому другой подход не может быть легко реализован.

Мое предложение состоит в том, чтобы использовать регулярное глобальное ограничение иметь дело с подсчетом чисел m и l. Это гарантирует, что предоставленное решение не помещает в последовательность более 6 подпоследовательный m (игнорируя o и одиночный l).

Пример:

include "globals.mzn";

enum TypeOfShift = {l,m,o};

% sat:
%array[1..30] of var TypeOfShift: shift = [m,  m,  m,  l,  l,  o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  l];

% sat:
%array[1..30] of var TypeOfShift: shift = [l,  l,  l,  l,  l,  m,  m,  m,  o,  o,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  l,  l,  m,  m];

% unsat: too many m
% array[1..30] of var TypeOfShift: shift = [m,  m,  l,  l,  m,  o,  m,  m,  m,  m,  l,  l,  l,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  m,  l,  l,  l,  m];

% unsat: o breaks double l
% array[1..30] of var TypeOfShift: shift = [l,  l,  l,  l,  l,  m,  m,  m,  o,  o,  l,  l,  l,  m,  m,  m,  m,  m,  l,  o,  l,  m,  m,  m,  m,  m,  l,  l,  m,  m];

% free assignment
% [NOTE: this will give a trivial answer because of missing constraints]
array[1..30] of var TypeOfShift: shift;

%          |   1     2     3   <= Input Values
%          |   m     o     l
% ---------------------------- 
%  1 m0_l0 | m1_l0 m0_l0 m0_l1
%  2 m1_l0 | m2_l0 m1_l0 m1_l1
%  3 m2_l0 | m3_l0 m2_l0 m2_l1
%  4 m3_l0 | m4_l0 m3_l0 m3_l1
%  5 m4_l0 | m5_l0 m4_l0 m4_l1
%  6 m5_l0 | m6_l0 m5_l0 m5_l1
%  7 m6_l0 |   -   m6_l0 m6_l1
%  8 m0_l1 | m1_l0 m0_l0 m0_l0
%  9 m1_l1 | m2_l0 m1_l0 m0_l0
% 10 m2_l1 | m3_l0 m2_l0 m0_l0
% 11 m3_l1 | m4_l0 m3_l0 m0_l0
% 12 m4_l1 | m5_l0 m4_l0 m0_l0
% 13 m5_l1 | m6_l0 m5_l0 m0_l0
% 14 m6_l1 |   -   m6_l0 m0_l0
% ^
% states
array[1..14, 1..3] of 0..14: transition_relation =
    [|  2,  1,  8,  % m0_l0
     |  3,  2,  9,  % m1_l0
     |  4,  3, 10,  % m2_l0
     |  5,  4, 11,  % m3_l0
     |  6,  5, 12,  % m4_l0
     |  7,  6, 13,  % m5_l0
     |  0,  7, 14,  % m6_l0
     |  2,  1,  1,  % m0_l1
     |  3,  2,  1,  % m0_l2
     |  4,  3,  1,  % m0_l3
     |  5,  4,  1,  % m0_l4
     |  6,  5,  1,  % m0_l5
     |  7,  6,  1,  % m0_l6
     |  0,  7,  1,  % m0_l7
    |];

constraint regular(
    [ if s == m then 1 else
      if s == o then 2 else
                     3 endif
                       endif
      | s in shift],                % sequence of input values
    14,                             % number of states
    card(TypeOfShift),              % number of different input values of state machine
    transition_relation,            % transition relation
    1,                              % initial state
    1..14,                          % final states
 );

solve satisfy;

Важные примечания:

• также можно использовать для проверки существующих решений;

• следует поместить ограничение normal в предикат , чтобы его можно было легко применить ко всем сотрудникам без дублирования кода;

• MiniZinc печатает тривиальный ответ для этой модели только потому, что нет никаких других ограничений на массив shifts (т. Е. минимальное число m, требуемое в месяц ).