MiniZinc 没有找到调度问题的解决方案
MiniZinc does not find a solution to the scheduling problem
我在使用 MiniZinc 寻找解决方案时遇到问题。
任务:
有必要为员工制定轮班时间表。
一日三班:白班(D)、晚班(E)、夜班(N)。
有必要制定一个最佳时间表,尽可能避免不良情况:
避免单班(两次休息之间换班)
避免单断(shift,break,shift)
避免双重中断(shift, break, break, shift)
上夜班后应该休息一整天(连续三休)
为了找到解决方案,我尽量减少不良情况的数量。
当我开始计算时,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
];
我建议对您的模型进行以下更改:
将X
的声明改为array[E, D] of var 0..1: X;
,其中0
表示break,1
shift。无论是白班、晚班还是夜班都在输出部分处理,结果在输出部分进行转换以显示轮班类型,如 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));
我在使用 MiniZinc 寻找解决方案时遇到问题。
任务: 有必要为员工制定轮班时间表。 一日三班:白班(D)、晚班(E)、夜班(N)。 有必要制定一个最佳时间表,尽可能避免不良情况:
避免单班(两次休息之间换班)
避免单断(shift,break,shift)
避免双重中断(shift, break, break, shift)
上夜班后应该休息一整天(连续三休)
为了找到解决方案,我尽量减少不良情况的数量。 当我开始计算时,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
];
我建议对您的模型进行以下更改:
将X
的声明改为array[E, D] of var 0..1: X;
,其中0
表示break,1
shift。无论是白班、晚班还是夜班都在输出部分处理,结果在输出部分进行转换以显示轮班类型,如 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));