我是约束编程的新手。我想这是一个简单的问题，但我无法解决它。这是问题所在：
我们如何将任务分配给机器以最小化结束时间或使用的机器数量？
似乎我应该能够使用累积谓词来实现这一点，但它似乎仅限于将一组任务安排给一个具有有限全局资源的工作人员，而不是可变数量的工作人员。
我只是在学习 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
]
;
该模型有两种“模式”：一种是最小化时间（“minimize last_time”），另一种是最小化使用的机器数量（“minimize 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) 的负载情况。第二部分“时间/任务：机器（任务的内存）”以“机器（机器的内存）”的形式显示每个时间步（行）和任务（列）使用了哪台机器以及任务的内存.
使用模型的第二种方式，尽量减少使用机器的数量，给出这个结果（编辑以节省空间）。即一台机器足以在允许的时间内（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)