Optimizing working scheduling MiniZinc code - constraint programming

Question 1

I'm hakank (author of the original model). If I understand it correctly, your question now is how to present the table for the optimal solution, not really about finding the solution itself (all FlatZinc solvers I tested solved it in no time).

One way of creating the table is to have a help matrix ("m") which contain information if a speaker is selected (1), busy (-1) or not available (0):

array[1..num_slots, 1..num_speakers] of var -1..1: m;

Then one must connect info in this the matrix and the other decision variables ("starting_slot" and "ending_slot"):

% connect to matrix m
constraint
   forall(t in 1..num_slots) (
      forall(s in 1..num_speakers) (
         (not(t in speaker_availability[s]) <-> m[t,s] = -1) 
          /\
          ((t >= starting_slot[s] /\ t <= ending_slot[s]) <-> m[t,s] = 1)
     )
 )

;

Then the matrix "m" can be printed like this:

% ...
++
[ 
   if s = 1 then "\n" else " " endif ++
   if fix(m[t,s]) = -1 then 
      "Busy    " 
   elseif fix(m[t,s]) =  1 then 
      "SELECTED" 
   else
      "        "
   endif
 | t in 1..num_slots, s in 1..num_speakers

] ;

As always, there are more than one way of doing this, but I settled with this since it's quite direct.

Here's the complete model: http://www.hakank.org/minizinc/scheduling_speakers_optimize.mzn

Update: Adding the output of the model:

Starting:  [1, 4, 3]
Durations: [1, 2, 1]
Ends:      [1, 5, 3]
z:         5

SELECTED Busy             
Busy     Busy     Busy    
Busy     Busy     SELECTED
         SELECTED         
         SELECTED Busy    
Busy     Busy             
----------
==========

Update 2: Another way is to use cumulative/4 instead of no_overlap/4 which should be more effective, i.e.

constraint 
    forall(i in 1..num_speakers) (
    ending_slot[i] = starting_slot[i] + app_durations[i] - 1
    ) 
    % /\ % use cumulative instead (see below)
    % forall(i,j in 1..num_speakers where i < j) (
    %   no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
    % ) 
    /\
    forall(i in 1..num_speakers) (
    forall(j in 1..app_durations[i]) (
        starting_slot[i]+j-1 in speaker_availability[i]
           )
    ) 

    /\ cumulative(starting_slot, app_durations, [1 | i in 1..num_speakers], 1)
;

Here's the altered version (which give the same result) http://www.hakank.org/minizinc/scheduling_speakers_optimize2.mzn (I've also skipped the presentation matrix "m" and do all presentation in the output section.)

For this simple problem instance, there is no discernible difference, but for larger instances this should be faster. (And for larger instances, one might want to test different search heuristics instead of "solve minimize z".)

Question 2

As I commented on your previous question Constraint Programming: Scheduling speakers in shortest time, the cumulative constraint is appropriate for this. I don't have Minizinc code handy, but there is the model in ECLiPSe (http://eclipseclp.org):

:- lib(ic).
:- lib(ic_edge_finder).
:- lib(branch_and_bound).

solve(JobStarts, Cost) :-
    AllUnavStarts = [[2,6],[1,6],[2,5]],
    AllUnavDurs   = [[2,1],[3,1],[1,1]],
    AllUnavRess   = [[1,1],[1,1],[1,1]],
    JobDurs = [1,2,1],
    Ressources = [1,1,1],
    length(JobStarts, 3),
    JobStarts :: 1..9,

    % the jobs must not overlap with each other
    cumulative(JobStarts, JobDurs, Ressources, 1),

    % for each speaker, no overlap of job and unavailable periods
    (
        foreach(JobStart,JobStarts),
        foreach(JobDur,JobDurs),
        foreach(UnavStarts,AllUnavStarts),
        foreach(UnavDurs,AllUnavDurs),
        foreach(UnavRess,AllUnavRess)
    do
        cumulative([JobStart|UnavStarts], [JobDur|UnavDurs], [1|UnavRess], 1)
    ),

    % Cost is the maximum end date
    ( foreach(S,JobStarts), foreach(D,JobDurs), foreach(S+D,JobEnds) do true ),
    Cost #= max(JobEnds),

    minimize(search(JobStarts,0,smallest,indomain,complete,[]), Cost).