時間表minizinc不重疊

Question

我想做一個沒有重疊的時間表，只有1位老師可以預訂1個時隙。我想創建一個像教師一樣的行，並且時隙是coloumns。

Answer 1

用於這些類型約束的一般約束（「應該是不同的」）是兩個全局約束all_different或alldifferent_except_0。

注意：我更改爲3位教師，3個時間片和5個演示文稿，以便更全面地使用alldifferent_except_0，因爲可以在沒有教師/時間段的情況下進行演示。

另外，我不確定我會如何使用特定表示，因爲它的表示取決於模型中的其他約束（如果有）。

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

1）只是一個「時間表」矩陣簡單的模型

如果你只是想在一個時間表矩陣分配牛逼教師，TS時隙，並沒有進一步的限制，那麼一個約束「all_different_except_0」 P演講就足夠了（連同下面解釋的總和）。 「時間表」的維度是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 [....]; 

這種模式的缺點是，它是不容易的聲明，可能需要進一步限制，也是我們要算在「時間表」矩陣非0的任務數量，以確保有正好分配了5個演示文稿。

所以我們將擴大更多的決策變量。

2）添加決策變量

該模型的原始演示文稿與上面顯示的「時間表」矩陣及其約束連接。這意味着我們可以保留「時間表」的約束來確保唯一性，並且我們也可以對其他決策變量進行約束。這是一個包含兩個原始數組「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）（......）」連接兩個表示：在「時間表」表示和兩個附加陣列。

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」）並選擇分配給「此」教師的時間，並確保它們不同。

第二個變體（「B」）雖然有時非常有用，但它是一種破解類型：它構建了一個老師分配的整數列表（時間+ teacher_id *演示文稿數量），並確保這些變量是獨特的。

由於此模型沒有明確的時間表，因此必須在輸出中提取時間表。這裏有一種方法：

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

如上所述，該模型（決策變量來選擇其中）的表現在很大程度上取決於什麼人需要做進一步。