schedulingor-toolsconstraint-programmingminizinc

Constraint Programming: Scheduling speakers in shortest time


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     |          |
+---+----------+----------+----------+

Solution

  • 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)
    ----------