Optimizing Work Planning Programming with Code Restriction MiniZinc

Question

Please help optimize this MiniZinc working code:

Task: There is a conference with a 6-time interval. There are 3 speakers at the conference, each of which is available in specific slots. Each speaker will be displayed for a given number of slots.

Purpose: To produce a schedule that has the earliest end of the speakers.

Example: Speakers A, B, and C. Talk Duration = [1, 2, 1]

Speaker Availability:

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

Link to MiniZinc working code: http://pastebin.com/raw.php?i=jUTaEDv0

What I hope to optimize:

 % ensure allocated slots don't overlap and the allocated slot is free for the speaker constraint forall(i in 1..num_speakers) ( ending_slot[i] = starting_slot[i] + app_durations[i] - 1 ) /\ 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] ) ) ; 

Expected Solution:

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

Answer 1

I am hakank (author of the original model). If I understood correctly, now your question is how to present a table for the optimal solution, and not about the search for the solution itself (all the solvers that I tested FlatZinc solved in the shortest possible time).

One way to create a table is to have a help matrix ("m") that contains information if the speaker (1) is selected, busy (-1) or unavailable (0):

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

Then you need to link the information in this matrix and other decision variables ("start_slot" and "end_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 as follows:

 % ... ++ [ 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 several ways to do this, but I decided with this because it is pretty direct.

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

Update: adding model output:

 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 efficient, 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 a modified version (which gives the same result) http://www.hakank.org/minizinc/scheduling_speakers_optimize2.mzn (I also skipped the "m" view matrix and completed the entire presentation in the output section.)

There is no noticeable difference for this simple instance of the problem, but for larger instances it should be faster. (And for large instances, you might need to test various search heuristics, rather than "enable z minimization.")

Answer 2

When I commented on your previous question, Programming constraints: scheduling schedules as soon as possible , a cumulative constraint is suitable for this. I do not have Minizinc code, but ECLiPSe has a model ( 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).