约束编程：多个工人的调度

我是约束编程的新手。我想这是一个简单的问题，但我无法解决它。问题是这样的：

• 我们有多台机器 (N)，每台机器的资源都是有限的（比如说内存，所有机器的资源可以相同。）
• 我们有 T 个任务，每个任务都有一个持续时间，并且每个任务都需要一定量的资源。
• 只要不超出其资源，一台机器可以同时处理多个任务。
• 一项任务不能在机器之间拆分，并且必须一次性完成（即没有暂停）。

我们如何将任务分配给机器以最小化结束时间或使用的机器数量？

看起来我应该能够通过累积谓词来实现这一点，但它似乎仅限于将一组任务调度给具有有限全局资源的一个工作人员，而不是可变数量的工作人员。

我刚刚学习 CP 和 MiniZinc。关于如何概括累积的任何想法？或者，是否有我可以理解的现有 MiniZinc 模型可以执行类似的操作（或足够接近？）

Thanks,

PS：我没有任何具体数据，因为这在很大程度上是一个假设/学习练习。假设您有 10 台机器和 10 个任务，其持续时间（以小时为单位）：2,4,6,5,2,1,4,6,3,2,12，内存要求（GB）：1,2,4， 2,1,8,12,4,1,10。每台机器都有 32 GB 的 RAM。

这是一个似乎是正确的模型。然而，它根本不使用“累积”，因为我想尽可能多地可视化（见下文）。

主要思想是 - 对于每个时间步长 1..max_step - 每台机器必须只有

输出部分以不同的方式显示解决方案。请参阅下面的评论。

该模型是稍微编辑过的版本http://hakank.org/minizinc/scheduling_with_multiple_workers.mzn

更新：我还应该提到，该模型允许机器上使用不同大小的 RAM，例如有些机器有 64GB，有些机器有 32GB。这在我网站上的模型中得到了演示 - 但进行了评论。由于模型使用 value_precede_chain/2 - 这确保了机器按顺序使用 - 建议按 RAM 大小递减的顺序对机器进行排序（因此首先使用较大的机器）。

（另外，我在 Picat 中对问题进行了建模：http://hakank.org/picat/scheduling_with_multiple_workers.pi )

include "globals.mzn"; 
int: num_tasks = 10; 
int: num_machines = 10;

array[1..num_tasks] of int: duration = [2,4,6,5,2,1,4,6,3,12]; % duration of tasks

array[1..num_tasks] of int: memory   = [1,2,4,2,1,8,12,4,1,10];  % RAM requirements (GB)
int: max_time = 30; % max allowed time

% RAM for each machine (GB)
array[1..num_machines] of int: machines_memory = [32 | i in  1..num_machines];


% decision variables
array[1..num_tasks] of var 1..max_time: start_time; % start time for each task
array[1..num_tasks] of var 1..max_time: end_time;   % end time for each task
array[1..num_tasks] of var 1..num_machines: machine; % which machine to use
array[1..num_machines,1..max_time] of var 0..max(machines_memory): machine_used_ram;

var 1..num_machines: machines_used = max(machine);
var 1..max_time: last_time = max(end_time);

% solve :: int_search(start_time ++ machine ++ array1d(machine_used_ram), first_fail, indomain_split, complete)  minimize last_time;
solve :: int_search(start_time ++ machine ++ array1d(machine_used_ram), first_fail, indomain_split, complete) minimize machines_used;

constraint
  forall(t in 1..num_tasks) (
    end_time[t] = start_time[t] + duration[t] -1
  ) 
  % /\ cumulative(start_time,duration,[1 | i in  1..num_tasks],machines_used)
  /\
  forall(m in 1..num_machines) (
     % check all the times when a machine is used
     forall(tt in 1..max_time) (
        machine_used_ram[m,tt] = sum([memory[t]*(machine[t]=m)*(tt in start_time[t]..end_time[t]) | t in 1..num_tasks]) /\ 
        machine_used_ram[m,tt] <= machines_memory[m]

        % sum([memory[t]*(machine[t]=m)*(tt in start_time[t]..end_time[t]) | t in 1..num_tasks]) <= machines_memory[m]
     )

  )

  %  ensure that machine m is used before machine m+1 (for machine_used)
  /\ value_precede_chain([i | i in 1..num_machines],machine)
;

output [
  "start_time: \(start_time)\n",
  "durations : \(duration)\n",
  "end_time  : \(end_time)\n",
  "memory    : \(memory)\n",
  "last_time : \(last_time)\n",
  "machine   : \(machine)\n",
  "machines_used: \(machines_used)\n",
]
++
[ "Machine memory per time:\n    "]
++
[ show_int(3,tt) | tt in 1..max_time ]
++
[
  if tt = 1 then "\n" ++ "M" ++ show_int(2, m) ++ ": "  else " " endif ++
 show_int(2,machine_used_ram[m,tt])
  | m in 1..num_machines, tt in 1..max_time
]
++ ["\n\nTime / task: machine(task's memory)\n  Task "] ++
[
  show_int(7,t)
  | t in 1..num_tasks
]
++ 
[
  if t = 1 then "\nTime " ++ show_int(2,tt) ++ " " else " " endif ++
    if tt in fix(start_time[t])..fix(end_time[t]) then
      show_int(2,fix(machine[t])) ++ "(" ++ show_int(2,memory[t]) ++    ")"
    else 
       "      " 
    endif 
   | tt in 1..fix(last_time), t in 1..num_tasks
 ] 
;

该模型有两种“模式”：一种是最小化时间（“最小化last_time”），另一种是最小化所使用的机器数量（“最小化machines_used”）。

最小化时间的结果是：

start_time: [11, 8, 3, 8, 11, 8, 9, 7, 8, 1]
durations : [2, 4, 6, 5, 2, 1, 4, 6, 3, 12]
end_time  : [12, 11, 8, 12, 12, 8, 12, 12, 10, 12]
memory    : [1, 2, 4, 2, 1, 8, 12, 4, 1, 10]
last_time : 12
machine   : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
machines_used: 1
Machine memory per time:
       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
M 1: 10 10 14 14 14 14 18 31 31 31 32 30  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 2:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 3:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 4:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 5:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 6:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 7:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 8:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M 9:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
M10:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

 Time / task: machine(task's memory)
  Task       1      2      3      4      5      6      7      8      9     10
 Time  1                                                                 1(10)
 Time  2                                                                 1(10)
 Time  3                1( 4)                                            1(10)
 Time  4                1( 4)                                            1(10)
 Time  5                1( 4)                                            1(10)
 Time  6                1( 4)                                            1(10)
 Time  7                1( 4)                              1( 4)         1(10)
 Time  8         1( 2)  1( 4)  1( 2)         1( 8)         1( 4)  1( 1)  1(10)
 Time  9         1( 2)         1( 2)                1(12)  1( 4)  1( 1)  1(10)
 Time 10         1( 2)         1( 2)                1(12)  1( 4)  1( 1)  1(10)
 Time 11  1( 1)  1( 2)         1( 2)  1( 1)         1(12)  1( 4)         1(10)
 Time 12  1( 1)                1( 2)  1( 1)         1(12)  1( 4)         1(10)
 ----------
 ==========

第一部分“每次机器内存”显示每台机器 (1..10) 每个时间步 (1..30) 的负载情况。 第二部分“时间/任务：机器（任务的内存）”以“机器（机器的内存）”的形式显示每个时间步（行）和任务（列）所使用的机器以及任务的内存。

使用模型的第二种方法是最大限度地减少使用的机器数量，给出此结果（经过编辑以节省空间）。 IE。一台机器足以在允许的时间内（1..22 个时间步长）处理所有任务。

 start_time: [19, 11, 3, 9, 20, 22, 13, 7, 17, 1]
 durations : [2, 4, 6, 5, 2, 1, 4, 6, 3, 12]
 end_time  : [20, 14, 8, 13, 21, 22, 16, 12, 19, 12]
 memory    : [1, 2, 4, 2, 1, 8, 12, 4, 1, 10]
 last_time : 22
 machine   : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 machines_used: 1
 Machine memory per time:
       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 M 1: 10 10 14 14 14 14 18 18 16 16 18 18 16 14 12 12  1  1  2  2  1  8  0  0  0  0  0  0  0  0
 M 2:  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 ....
 Time / task: machine(task's memory)
   Task       1      2      3      4      5      6      7      8      9     10
 Time  1                                                                 1(10)
 Time  2                                                                 1(10)
 Time  3                1( 4)                                            1(10)
 Time  4                1( 4)                                            1(10)
 .....
 ----------
 ==========