Minizinc: создать действительную смену

Question

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

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

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

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

Я пытался создать массив с 0 (для ls) и 1 (для ms), но удалив из массива все 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;

Важные заметки:

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

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

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