我是限制编程的新手。我想这是一个简单的问题，但我无法绕过它。这是问题所在：
我们如何将任务分配给机器以最小化结束时间或使用的机器数量？
看起来我应该能够通过累积谓词来实现这一点，但似乎仅限于将一组任务安排到一个具有有限全局资源而不是可变数量的工作者的工作者。
我刚刚学习CP和MiniZinc。关于如何概括累积的任何想法？或者，是否存在我能理解的现有MiniZinc模型，它可以做到这样（或者足够接近？）
谢谢，
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的内存。
这是一个似乎正确的模型。但是，它根本不使用“累积”，因为我想尽可能地想象（见下文）。
主要思想是 - 对于每个时间步，1..max_step - 每台机器必须只有<= 32 GB的任务。 foreach循环检查 - 对于每台机器 - 该机器上当时处于活动状态的每个任务的内存总和低于32GB。
输出部分以不同方式显示解决方案。见下面的评论。
该模型是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”），另一个用于最小化所用机器的数量（“最小化机器_用途”）。
最小化时间的结果是：
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）的加载方式。第二部分“时间/任务：机器（任务的内存）”显示每个时间步骤（行）和任务（列）使用的机器以及“机器（机器的内存）”形式的任务的内存。
使用模型的第二种方法是最小化已用机器的数量，给出这个结果（编辑以节省空间）。即一台机器足以在允许的时间内处理所有任务（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)
.....
----------
==========
这是一个老问题，但这是针对此问题的CP Optimizer模型（在Python中）。在这个版本中，我最小化了一个词典编纂目标：首先最小化完工时间（最佳值为12），然后给定这个完工时间，最小化使用过的机器的数量（这里，一个人可以在一台机器上执行所有任务，仍然在12 ）。
DUR = [2,4,6,5,2,1,4,6,3,12]
MEM = [1,2,4,2,1,8,12,4,1,10]
CAP = 32
TASKS = range(len(DUR))
MACHINES = range(10)
from docplex.cp.model import *
model = CpoModel()
# Decision variables: tasks and alloc
task = [interval_var(size=DUR[i]) for i in TASKS]
alloc = [ [interval_var(optional=True) for j in MACHINES] for i in TASKS]
# Objective terms
makespan = max(end_of(task[i]) for i in TASKS)
nmachines = sum(max(presence_of(alloc[i][j]) for i in TASKS) for j in MACHINES)
# Objective: minimize makespan, then number of machine used
model.add(minimize_static_lex([makespan, nmachines]))
# Allocation of tasks to machines
model.add([alternative(task[i], [alloc[i][j] for j in MACHINES]) for i in TASKS])
# Machine capacity
model.add([sum(pulse(alloc[i][j],MEM[i]) for i in TASKS) <= CAP for j in MACHINES])
# Resolution
sol = model.solve(trace_log=True)
# Display solution
for i in TASKS:
for j in MACHINES:
s = sol.get_var_solution(alloc[i][j])
if s.is_present():
print('Task ' + str(i) + ' scheduled on machine ' + str(j) + ' on [' + str(s.get_start()) + ',' + str(s.get_end()) + ')')
结果是：
! ----------------------------------------------------------------------------
! Minimization problem - 110 variables, 20 constraints
! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
! . Log search space : 66.4 (before), 66.4 (after)
! . Memory usage : 897.0 kB (before), 897.0 kB (after)
! Using parallel search with 8 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 110 -
+ New bound is 12; 0
* 12 111 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 7
* 12 131 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 6
* 12 151 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 5
* 12 171 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 4
* 12 191 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 3
* 12 211 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 2
* 12 231 0.01s 1 (gap is 100.0% @ crit. 2 of 2)
New objective is 12; 1
! ----------------------------------------------------------------------------
! Search completed, 7 solutions found.
! Best objective : 12; 1 (optimal)
! Best bound : 12; 1
! ----------------------------------------------------------------------------
! Number of branches : 1318
! Number of fails : 40
! Total memory usage : 6.7 MB (6.6 MB CP Optimizer + 0.1 MB Concert)
! Time spent in solve : 0.00s (0.00s engine + 0.00s extraction)
! Search speed (br. / s) : 131800.0
! ----------------------------------------------------------------------------
Task 0 scheduled on machine 4 on [4,6)
Task 1 scheduled on machine 4 on [4,8)
Task 2 scheduled on machine 4 on [1,7)
Task 3 scheduled on machine 4 on [0,5)
Task 4 scheduled on machine 4 on [4,6)
Task 5 scheduled on machine 4 on [0,1)
Task 6 scheduled on machine 4 on [0,4)
Task 7 scheduled on machine 4 on [1,7)
Task 8 scheduled on machine 4 on [4,7)
Task 9 scheduled on machine 4 on [0,12)