约束编程：调度多个工人
Constraint Programming: Scheduling with multiple workers
我是约束规划的新手。我想这是一个简单的问题，但我无法解决这个问题。问题是：
- 我们有多台机器 (N)，每台机器都有有限的资源（比方说内存，所有机器都可以相同。）
- 我们有 T 个任务，每个任务都有持续时间，每个任务都需要一定数量的资源。
- 一台机器可以同时处理多项任务，只要不超出其资源。
- 一项任务不能在机器之间拆分，必须一次完成（即没有暂停）。
我们如何将任务分配给机器以最小化结束时间或使用的机器数量？
似乎我应该能够通过累积谓词实现这一点，但它似乎仅限于将一组任务安排给具有有限全局资源的一个工人，而不是可变数量的工人。
我正在学习 CP 和 MiniZinc。关于如何概括累积的任何想法？或者，是否有一个我能理解的现有 MiniZinc 模型可以做这样的事情（或足够接近？）
谢谢，
PS：我没有任何具体数据，因为这大部分是 hypothetical/learning 练习。假设您有 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 的内存。
这是一个似乎正确的模型。但是，它根本不使用 "cumulative" 因为我想尽可能多地可视化（见下文）。
主要思想是 - 对于每个时间步，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
]
;
该模型有两个"modes"：一个是最小化时间（"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)
----------
==========
第一部分 "Machine memory per time" 显示每台机器 (1..10) 每个时间步 (1..30) 的负载情况。
第二部分 "Time / task: machine(task's memory)" 以 "machine(memory of the machine)".
的形式显示每个时间步长（行）和任务（列）使用的机器和任务的内存
第二种使用模型的方式，尽量减少使用机器的数量，给出这个结果（编辑保存space）。 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)
.....
----------
==========
这是一个老问题，但这是针对此问题的 CP 优化器模型（在 Python 中）。
在这个版本中，我最小化了一个字典顺序 objective ：首先最小化 makespan（最佳值为 12），然后给定这个 makespan，最小化使用的机器数量（这里，一个人可以在一台机器上执行所有任务，并且仍然在 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)
我是约束规划的新手。我想这是一个简单的问题，但我无法解决这个问题。问题是：
- 我们有多台机器 (N)，每台机器都有有限的资源（比方说内存，所有机器都可以相同。）
- 我们有 T 个任务，每个任务都有持续时间，每个任务都需要一定数量的资源。
- 一台机器可以同时处理多项任务，只要不超出其资源。
- 一项任务不能在机器之间拆分，必须一次完成（即没有暂停）。
我们如何将任务分配给机器以最小化结束时间或使用的机器数量？
似乎我应该能够通过累积谓词实现这一点，但它似乎仅限于将一组任务安排给具有有限全局资源的一个工人，而不是可变数量的工人。
我正在学习 CP 和 MiniZinc。关于如何概括累积的任何想法？或者，是否有一个我能理解的现有 MiniZinc 模型可以做这样的事情（或足够接近？）
谢谢，
PS：我没有任何具体数据，因为这大部分是 hypothetical/learning 练习。假设您有 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 的内存。
这是一个似乎正确的模型。但是，它根本不使用 "cumulative" 因为我想尽可能多地可视化（见下文）。
主要思想是 - 对于每个时间步，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
]
;
该模型有两个"modes"：一个是最小化时间（"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)
----------
==========
第一部分 "Machine memory per time" 显示每台机器 (1..10) 每个时间步 (1..30) 的负载情况。 第二部分 "Time / task: machine(task's memory)" 以 "machine(memory of the machine)".
的形式显示每个时间步长（行）和任务（列）使用的机器和任务的内存第二种使用模型的方式，尽量减少使用机器的数量，给出这个结果（编辑保存space）。 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)
.....
----------
==========
这是一个老问题，但这是针对此问题的 CP 优化器模型（在 Python 中）。 在这个版本中，我最小化了一个字典顺序 objective ：首先最小化 makespan（最佳值为 12），然后给定这个 makespan，最小化使用的机器数量（这里，一个人可以在一台机器上执行所有任务，并且仍然在 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)