協調計劃的班次與空餘空間

Question

我正在編寫一個計劃，根據預先定義的班次（時間塊）和學生可用性（也包括時間塊），幫助安排我們大學的學生員工。

除了對員工不是簡單普遍可用的約束進行建模之外，這讓我感到與Air Crew問題類似：這取決於他們的日程安排。

更經驗的約束程序員推薦什麼建模策略來解決這個問題？

（我使用Gecode。）

Answer 1

這樣做的最好的（或好）的方式確實取決於你的日程安排的表示。

一個簡單的變體是添加二進制可用性矩陣，其中x [i，j] = 1表示第i個人在第j天可用（或根據您對時間表的表示進行轉置） 。

一個（簡單的）例子是通過MiniZinc的護士護理標準模型（「tutorial/nurse.mzn」，一個展示「常規」約束的例子），然後添加一個可用性矩陣。這裏是我的版本認爲：http://www.hakank.org/minizinc/nurse_rostering_with_availability.mzn

分配了一個人特定的插槽必須確保，一個人是可以工作的某一天，如下圖所示（「可用的[I，J] = 1」）。

% availability matrix 
array[1..num_nurses, 1..num_days] of int: available = 
    array2d(1..num_nurses, 1..num_days, 
    [ 
    % days 
    1,1,0,1,1,1,1, 1,1,1,0,1,1,1, % nurses 
    0,1,1,1,0,1,1, 0,1,1,1,1,1,1, 
    1,0,1,1,0,1,1, 1,0,0,1,1,0,1, 
    1,1,1,1,1,0,1, 1,0,1,1,1,1,0, 
    1,1,1,0,1,1,1, 1,1,1,1,0,1,1, 
    1,1,0,1,1,0,1, 1,1,0,1,1,1,0, 
    1,1,1,0,1,1,1, 1,1,1,0,1,1,1, 
    ]); 


% ... 

% for each day the must be at least 3 nurses with day shift, 
% and 2 nurses with night shifht 
constraint 
    forall(j in 1..num_days) (
     sum(i in 1..num_nurses) ( 
       bool2int(x[i,j] == day_shift /\ available[i,j] = 1)) >= 3 
     /\ 
     sum(i in 1..num_nurses) ( 
       bool2int(x[i,j] == night_shift /\ available[i,j] = 1)) >= 2 
    ) 
; 

此外，強迫一個人是下班的日子，他/她是不可用的，我們將其設置爲在該模型「off_shift」。

constraint 
    forall(i in 1..num_nurses, j in 1..num_days) (
     if available[i,j] = 0 then 
      x[i,j] = off_shift 
     else 
      true 
     endif 
    ) 
;