Constraint Programming: Scheduling speakers in shortest time

Question

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

Lars Kotthoff · Accepted Answer · 2013-12-17 13:16:19Z

3

This is turning your satisfaction problem into an optimisation problem. That is, it is not enough to find a solution anymore, you want the optimal one. So for the MiniZinc model, you would need to change

solve :: int_search(x, first_fail, indomain_min, complete) satisfy;

to something like

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

to minimize the largest allocated time.

answered Dec 17, 2013 at 13:16

Lars Kotthoff

109k16 gold badges210 silver badges210 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Marcus Over a year ago

Lars, thanks that makes a lot of sense. However I can't seem to work out how to make MiniZinc or OR-Tools process a non-square matrix like the example.

Lars Kotthoff Over a year ago

Not sure what you mean by non-square matrix -- the MiniZinc model has just a list of lists?

Lars Kotthoff Over a year ago

One of the available slot arrays is empty, i.e. there's no solution.

Marcus Over a year ago

In my example in the OP, there is no availability in slot 2. I'm expecting to see a solution of (A,1), (C,3), (B,4).

Lars Kotthoff Over a year ago

That depends on what you're trying to do. In this particular case you could just drop the no-availability variable. In general, you're looking at a soft constraint or MaxSAT problem. For either you'll need a different modelling language/solver though.

|

jschimpf · Accepted Answer · 2013-12-17 22:00:21Z

1

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

answered Dec 17, 2013 at 22:00

jschimpf

5,04413 silver badges24 bronze badges

4 Comments

Marcus Over a year ago

Thanks so much. I thought of this overnight too and came in this morning to try it, only to find you'd already posted this solution.

Marcus Over a year ago

How would/could you adapt this solution if 'Speaker B' should speak for 2 consecutive slots?

jschimpf Over a year ago

At this point you will have to change model. You could use a matrix of 0/1 variables with one variable per slot and speaker. But closer to what you already have is a model where you consider each talk as a job with a start time variable and a duration. You have to replace the alldifferent with a cumulative constraint, and you could also model the availability constraints as non-overlaps between unavailability and job, with one cumulative per speaker.

Marcus Over a year ago

I've managed to adapt the code, however can't help but think it can be made more efficient. Can you help please? stackoverflow.com/questions/20747059/…

Collectives™ on Stack Overflow

Constraint Programming: Scheduling speakers in shortest time

2 Answers 2

7 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related