约束规划：在最短的时间内调度音箱 [英] Constraint Programming: Scheduling speakers in shortest time

问题描述

我想通过哈坎Kjellerstrand （@hakankless），以适应一个已经解决了约束规划问题，可以做一些帮助，请。

原件解决的问题：的有6个演讲家和6间客房。每位发言者都应该被分配到一个房间，没有空间空并在一个房间里的每个扬声器而已。

解决方案在这里：谷歌或-工具和放大器; MiniZinc

帮助与此相适应：的有3个演讲家和6个时隙（即一个房间）。每个扬声器应该分配给一个时隙，其目的在于减少从开始时隙的持续时间（假设从插槽1开始，或者如果所有占线，从下一个可用时隙开始）。

  + --- + ------ + ------ + ------ +
| | A | B | C |
+  -  + ------ + ------ + ------ +
| 1 | |忙| |
| 2 |忙|忙|忙|
| 3 |忙|忙| |
| 4 | | | |
| 5 | | |忙|
| 6 |忙|忙| |
+  -  + ------ + ------ + ------ +
 

的解决方案将是（A，1），（C，3），（B，4）。如果我们开始与（C，1），然后将完成与（A，5）或（B，5）。由于4℃图5，第一解决方案是正确的。 我该如何解决这个问题？

可视化解决方案：

  +  -  + ---------- + ---------- + ---------- +
| | A | B | C |
+  -  + ---------- + ---------- + ---------- +
| 1 | SELECTED |忙| |
| 2 |忙|忙|忙|
| 3 |忙|忙| SELECTED |
| 4 | | SELECTED | |
| 5 | | |忙|
| 6 |忙|忙| |
+  -  + ---------- + ---------- + ---------- +
 

解决方案

你有你的阵列尺寸混淆。它帮助，如果你给你的变量更有意义的名称，使之更明显的是什么范围过一下。

 包括globals.mzn;

INT：N = 3;扬声器的数量％
INT：S = 6;插槽数量％
ARRAY [1..1]组1..s的：可用; ％可用插槽
ARRAY [1..1]的VAR 1..s：speaks_at; ％在规定的扬声器插槽

解决:: int_search（speaks_at，first_fail，indomain_min，完成）
         尽量减少最大（speaks_at）;

约束
   all_different（speaks_at）
   / \
   FORALL（我在1..N）（
      speaks_at [i]于可用的[I]
   ）
;

％在该插槽可说每一个音箱
可用= [
    {1,4,5}，
    {4,5}，
    {1,3,4,6}
]。

产量
[
    显示（speaks_at）
]。
 

这给出了预期的答案：

 ％开始搜索
发现与成本4的溶液
speaks_at = array1d（1..3，[1,4,3]）;
％的最低目标价值= 4
％总时间0.016s CPU（0.000设定+ 0.000搜索）
----------
 

I'm trying to adapt an already solved constraint programming problem by Hakan Kjellerstrand (@hakankless) and could do with some help please.

Original solved problem: There are 6 public speakers and 6 rooms. Each speaker should be assigned to a room, with no room left empty and each speaker in one room only.

Solutions here: Google OR-Tools & MiniZinc

Help with this adaptation: There are 3 public speakers and 6 time slots (i.e. one room). Each speaker should be assigned to one time slot, with the aim to minimize the duration from the starting slot (assumed to be starting from Slot 1, or if all busy, starting from the next available slot).

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| 1 |      | Busy |      |
| 2 | Busy | Busy | Busy |
| 3 | Busy | Busy |      |
| 4 |      |      |      |
| 5 |      |      | Busy |
| 6 | Busy | Busy |      |
+---+------+------+------+

The solution would be (A,1), (C,3), (B,4). If we started with (C,1) then it would finish with (A,5) or (B,5). Since 4 < 5, the first solution is correct. How can I solve this?

Visual solution:

+---+----------+----------+----------+
|   |    A     |    B     |    C     |
+---+----------+----------+----------+
| 1 | SELECTED | Busy     |          |
| 2 | Busy     | Busy     | Busy     |
| 3 | Busy     | Busy     | SELECTED |
| 4 |          | SELECTED |          |
| 5 |          |          | Busy     |
| 6 | Busy     | Busy     |          |
+---+----------+----------+----------+

解决方案

You got your array dimensions mixed up. It helps if you give your variables more meaningful names to make it more obvious what ranges over what.

include "globals.mzn";

int: n = 3; % number of speakers
int: s = 6; % number of slots
array[1..n] of set of 1..s: available; % the available slots
array[1..n] of var 1..s: speaks_at; % the allotted speaker slot

solve :: int_search(speaks_at, first_fail, indomain_min, complete)
         minimize max(speaks_at);

constraint
   all_different(speaks_at)
   /\
   forall(i in 1..n) (
      speaks_at[i] in available[i]
   )
;

% at which slot is each speaker available to speak
available = [
    {1,4,5},  
    {4,5},  
    {1,3,4,6}  
];

output
[
    show(speaks_at)
];

This gives the expected answer:

% Starting search
Found a solution with cost 4
speaks_at = array1d(1..3, [1,4,3]);
% Minimum objective value = 4
% Total time 0.016s cpu (0.000 setup + 0.000 search)
----------

这篇关于约束规划：在最短的时间内调度音箱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！