约束编程:与多名工人一起计划 [英] Constraint Programming: Scheduling with multiple workers
问题描述
我是约束编程的新手.我想这是一个简单的问题，但是我无法解决这个问题.问题出在这里:
I'm new to constraint programming. I imagine this is an easy problem but I can't wrap my head around it. Here's the problem:
- 我们有多台计算机(N)，每台计算机都有有限的资源(比如说内存，并且对于所有计算机，它都可以是相同的.)
- 我们有T个任务，每个任务都有持续时间，每个任务都需要一定数量的资源.
- 一台机器可以同时处理多个任务，只要不超出其资源即可.
- 一项任务无法在多台机器之间进行拆分，必须一次性完成(即不暂停).
我们如何将任务分配给计算机，以最大程度地减少结束时间或所用计算机的数量?
How do we assign the tasks to the machines to minimize the end-time or the number of machines used?
似乎我应该可以使用累积谓词来实现这一目标，但似乎仅限于将一组任务调度给具有有限全局资源(而不是可变数量的工人)的一个工人.
It seems like I should be able to achieve this with the cumulative predicate but it seems like it's limited to scheduling one set of tasks to one worker with a limited global resource rather than a variable number of workers.
我正在学习CP&迷你锌.关于如何概括累积的任何想法?另外，是否有一个我可以理解的现有MiniZinc模型(是否足够接近?)
I'm just learning CP & MiniZinc. Any ideas on how to generalize cumulative? Alternatively, is there an existing MiniZinc model I can understand that does something like this (or close enough?)
谢谢
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的内存.
PS: I don't have any concrete data since this is a hypothetical/learning exercise for the most part. Imagine you have 10 machines and 10 tasks with various durations (in hours): 2,4,6,5,2,1,4,6,3,2,12 with memory requirements (GBs): 1,2,4,2,1,8,12,4,1,10. Each machine has 32 GBs of ram.
推荐答案
这里的模型似乎是正确的.但是，它根本不使用累计"，因为我想尽可能地可视化(请参阅下文).
Here's a model that seems to be correct. However, it don't use "cumulative" at all since I wanted to visualize as much as possible (see below).
主要思想是-对于每个时间步1..max_step-每台计算机必须仅具有< = 32 GB的任务.对于每个计算机，foreach循环都会检查当时在该计算机上处于活动状态的每个任务的内存总和是否低于32GB.
The main idea is that - for each time step, 1..max_step - each machine must have only tasks <= 32 GB. The foreach loop checks - for each machine - that the sum of memory of each task that is active at that time on that machine is below 32GB.
输出部分以不同方式显示解决方案.请参阅下面的评论.
The output section shows the solution in different ways. See comments below.
该模型是 http://hakank.org/minizinc/scheduling_with_multiple_workers.mzn
更新:我还应该提到，此模型允许机器上的RAM大小不同，例如有些机器有64GB，有些则有32GB.我的网站上的模型对此进行了演示-但对此进行了评论.由于该模型使用value_precede_chain/2(可确保按顺序使用计算机)，因此建议对计算机进行排序以减小RAM的大小(因此，首先使用较大的计算机).
Update: I should also mention that this model allows for different size of RAM on the machines, e.g. some machines have 64GB and some 32GB. This is demonstrated - but commented - in the model on my site. Since the model use value_precede_chain/2 - which ensures that the machines are used in order - it's recommended that the machines are ordered of decreasing size of RAM (so the bigger machines are used first).
(此外，我已经在Picat中对问题进行了建模: http://hakank.org/picat/schedule_with_multiple_workers.pi )
(Also, I've modeled the problem in 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").
The model has two "modes": one to minimize the time ("minimize last_time") and one to minimize the number of machine used ("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..30)加载每台计算机(1..10)的方式. 第二部分时间/任务:机器(任务的内存)"针对每个时间步(行)和任务(列)以机器(机器的内存)"的形式显示使用的机器以及任务的内存
The first part "Machine memory per time" shows how loaded each machine (1..10) is per time step (1..30). The second part "Time / task: machine(task's memory)" shows for each time step (rows) and tasks (columns) which machine that is used and the memory of the task in the form "machine(memory of the machine)".
使用模型的第二种方法，以减少使用的计算机数量，给出此结果(已编辑以节省空间). IE.一台机器足以在允许的时间内(1..22个时间步长)处理所有任务.
The second way of using the model, to minimize the number of used machines, give this result (edited to save space). I.e. one machine is enough for handling all the tasks during the allowed time (1..22 time steps).
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)
.....
----------
==========
这篇关于约束编程:与多名工人一起计划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
