调度 minizinc 不重叠

Question

我想做一个没有重叠的时间表，只能在 1 个时间段预订 1 位老师。我想创建一个像老师一样的 2darray，行和时隙是列。

Answer 1

用于此类约束 ("something should be distinct") 的一般约束是两个全局约束 all_different 或 alldifferent_except_0。

注意：我更改为 3 名教师、3 个时间段和 5 个演示文稿，以更普遍地使用 alldifferent_except_0，因为可以在没有 teacher/timeslot 的情况下进行演示文稿.

此外，我不确定我是否会像您那样使用特定的表示，因为它的表示取决于模型中的进一步约束（如果有的话）。

以下是一些可能有用的方法。

1) 只有一个 "timetable" 矩阵的简单模型

如果您只想分配 T 个教师、TS 个时间段和 P 个演示而没有进一步的限制，那么时间表矩阵上的单个限制 "all_different_except_0" 就足够了（连同下面解释的总和）。 "timetable" 的维度是我们分配演示文稿的 T x TS（教师 x 时隙），如果没有针对该教师和时隙的演示文稿，则为 0。

include "globals.mzn"; 

set of int: Timeslots = 1..3;
set of int: Teachers = 1..3; 
set of int: Presentations = 1..5;

solve satisfy;

% Decision variables
array[Teachers, Timeslots] of var {0} union Presentations: timetable;

constraint 
    alldifferent_except_0(array1d(timetable))

    % ensure that there are 5 assigned presentations
   /\ sum([timetable[t,ts]>0 | t in Teachers, ts in Presentations]) = card(Presentations)
;

% output [....];

这个模型的缺点是不容易说明可能需要的进一步约束，而且我们必须计算 "timetable" 矩阵中非 0 赋值的数量以确保存在恰好分配了 5 个演示文稿。

因此我们将使用更多决策变量进行扩展。

2) 添加决策变量

此模型将原始演示文稿与 "timetable" 矩阵及其如上所示的约束连接起来。这意味着我们可以保持对 "timetable" 的约束以确保唯一性，并且我们也可以对其他决策变量进行约束。这是一个包含两个原始数组 "presentation_teacher" 和 "presentation_time" 及其约束的模型。

 include "globals.mzn"; 
 set of int: Timeslots = 1..3;
 set of int: Teachers = 1..3; 
 set of int: Presentations = 1..5;

 % Decision variables
 % Which teacher has this presentation
 array[Presentations] of var Teachers: presentation_teacher;

 % Which timeslot for this presentation
 array[Presentations] of var Timeslots: presentation_time;

 % Which combination of teacher and timeslot for a presentation, if any
 array[Teachers, Timeslots] of var {0} union Presentations: timetable;
 solve satisfy;

 constraint

   alldifferent_except_0(array1d(timetable))
   % This constraint is not needed now
   % /\ sum([timetable[t,ts]>0 | t in Teachers, ts in Presentations]) = card(Presentations)

   /\ % connect timetable and presentation_teacher and presentation_time
  forall(p in Presentations) (
     timetable[presentation_teacher[p],presentation_time[p]] = p
  )
 ;

约束 "forall(p in Presentations) ( ... ) " 连接两个表示："timetable" 表示和两个添加的数组。

3) 替代版本

确保教师有不同的时间段和演示的另一种方法是在 "presentation_teacher"、"presentation_time" 上添加限制。这实际上并不需要时间表矩阵，因此此处将其跳过。（可以使用时间表方法添加这些约束可能会更快。）

include "globals.mzn"; 
set of int: Timeslots = 1..3;
set of int: Teachers = 1..3; 
set of int: Presentations = 1..5;

% Decision variables

% Which teacher has this presentation
array[Presentations] of var Teachers: presentation_teacher;

% Which timeslot for this presentation
array[Presentations] of var Timeslots: presentation_time;

solve satisfy;

constraint 
  % variant A
  forall(t in Teachers) (
      % the time for this teacher is distinct (or 0)
     alldifferent_except_0([presentation_time[p] * (presentation_teacher[p]=t) | p in Presentations])
  )

 /\ 
 % variant B
 forall(t in Teachers) (
    % combination of (time + teacher) for this teacher is unique
    alldifferent([presentation_time[p]+(presentation_teacher[p]*card(Presentations)) | p in Presentations])
 )

;

此模型有两个变体，其中第一个 ("A") 使用 alldifferent_except_0 来确保每个教师的演示文稿都是不同的。

对于每位教师，它循环遍历所有演示文稿 ("p") 并选择分配给 "this" 教师的时间，并确保它们是不同的。

第二个变体 ("B") 是一种 hack，但有时非常有用：它构建了一个整数列表，为教师分配（时间 + teacher_id * 演示次数) 并确保它们是不同的。

由于此模型没有明确的时间表，因此必须在输出中提取时间表。这是一种方法：

output [
  "Teacher " ++ show(t) ++ " has these presentations" ++ show([p | p in Presentations where fix(presentation_teacher[p]) = t]) ++ "\n"
  | t in Teachers
]
;

如上所述，模型的表示（select 的决策变量）在很大程度上取决于人们想进一步做什么。

调度 minizinc 不重叠

Schedule minizinc no overlapping

constraints

scheduled-tasks

minizinc