最小锌:产生有效的转变 [英] Minizinc: generate a valid shift

问题描述

希望有人可以帮助我！

最初的问题是生成有效的班次，如下所述:

The original problem is to generate valid shifts like explained below:

我有这样的数组，[m，m，m，o，o，l，l，m，m，m，l，m，m，m]具有固定长度(S)，其中m是有效的，o是办公室，我有空.我需要确保的是，至少每6m我就有两个l(ll). o不算作工作或免费.例子:

I have arrays like this [m,m,m,o,o,l,l,m,m,m,l,m,m,m] with a fixed length (S) where m is work, o is office and l free. What I need to make sure is that at least every 6m I have two l together (ll). The o does not count as work or as free. Examples:

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

我正在尝试创建一个数组(0(对于ls)和1(对于ms)，但是从数组中删除所有o和非连续的ls.因此，对于以上示例将是:

What I was trying is to create an array with 0 (for ls) and 1 (for ms) but removing from the array all the o and the non consecutive ls. So, for the above examples would be:

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

这样，我可以使用slide_sum或at_least约束来解决它.但是，我无法创建此新数组，因为它的大小将与原始数组(S)不同.一个有效的选择是在剩余的插槽末尾填充0，直到S.

This way I could use a sliding_sum or at_least constraint to solve it. However, I cannot manage to create this new array as it would have a different size than the original (S). A valid option is to pad at the end with 0 the remaining slots until S.

感谢您的帮助

编辑.到目前为止，这是代码:

Edit. This is the code so far:

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

推荐答案

此答案提供了简单的&问题中提出的有效解决方案，即如何确定给定班次是否有效. [请注意，在这种情况下，不必(实际上适得其反)将任何数组的内容声明为var $T].

This answer provides a simple & effective solution for the problem stated in the question, that is, how to determine if a given shift is valid or not. [Note that in this case it is not necessary (actually, it is counterproductive) to declare the content of any array as var $T].

一个选择是:

• 确定所有ll在数组(数组double_l_pos)中的起始位置
• 确定每个o在数组(数组has_o)中的位置
• 确定从开头(数组cum_has_o)开始的数组中o的累积数量
• 固定所有ll的位置，以使其忽略在其之前的任何o(数组fixed_double_l_pos)
• 确定所有ll个起始位置(数组double_l_distance)之间的距离
• 要求距离值不能大于6

• determine the starting position of all ll in the array (array double_l_pos)
• determine the position of each o in the array (array has_o)
• determine the cumulative number of o in the array from the beginning (array cum_has_o)
• fix the position of all ll so that it ignores any o preceding it (array fixed_double_l_pos)
• determine the distance between all ll starting positions (array double_l_distance)
• require that no distance value is larger than 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;

这里的所有内容都是静态计算的，因此即使在开始实际求解之前，也可以检测到模型不一致.

Everything here is statically computed, so the model inconsistency can be detected even before the actual solving is started.

附录:由于这是一个花名册问题，您可能需要详细阅读名册和模型.这些文件可能包含更好的方法来处理您的问题.

Addendum: since this is a roster problem, you may want to read in detail the roster and the on-call-rostering models in the MiniZinc benchmarks repository. Those files may contain better approaches for dealing with your problem.

这篇关于最小锌:产生有效的转变的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！