1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 using Google.OrTools.ConstraintSolver; 15 using Google.OrTools.Graph; 16 using System.Collections.Generic; 17 using System.Diagnostics; 18 using System.Linq; 19 using System; 20 21 public class SpeakerScheduling 22 { 23 public class FlowAssign : NetDecisionBuilder 24 { FlowAssign(IntVar[] vars, int first_slot, IntVar last_slot_var)25 public FlowAssign(IntVar[] vars, int first_slot, IntVar last_slot_var) 26 { 27 vars_ = vars; 28 first_slot_ = first_slot; 29 last_slot_var_ = last_slot_var; 30 } 31 Next(Solver solver)32 public override Decision Next(Solver solver) 33 { 34 int large = 100000; 35 int number_of_variables = vars_.Length; 36 long last_slot = last_slot_var_.Max(); 37 // Lets build a bipartite graph with equal number of nodes left and right. 38 // Variables will be on the left, slots on the right. 39 // We will add dummy variables when needed. 40 // Arcs will have a cost x is slot x is possible for a variable, a large 41 // number otherwise. For dummy variables, the cost will be 0 always. 42 LinearSumAssignment matching = new LinearSumAssignment(); 43 for (int speaker = 0; speaker < number_of_variables; ++speaker) 44 { 45 IntVar var = vars_[speaker]; 46 for (int value = first_slot_; value <= last_slot; ++value) 47 { 48 if (var.Contains(value)) 49 { 50 matching.AddArcWithCost(speaker, value - first_slot_, value); 51 } 52 else 53 { 54 matching.AddArcWithCost(speaker, value - first_slot_, large); 55 } 56 } 57 } 58 // The Matching algorithms expect the same number of left and right nodes. 59 // So we fill the rest with dense zero-cost arcs. 60 for (int dummy = number_of_variables; dummy <= last_slot - first_slot_; ++dummy) 61 { 62 for (int value = first_slot_; value <= last_slot; ++value) 63 { 64 matching.AddArcWithCost(dummy, value - first_slot_, 0); 65 } 66 } 67 if (matching.Solve() == LinearSumAssignment.Status.OPTIMAL && 68 matching.OptimalCost() < large) // No violated arcs. 69 { 70 for (int speaker = 0; speaker < number_of_variables; ++speaker) 71 { 72 vars_[speaker].SetValue(matching.RightMate(speaker) + first_slot_); 73 } 74 } 75 else 76 { 77 solver.Fail(); 78 } 79 return null; 80 } 81 82 private IntVar[] vars_; 83 private int first_slot_; 84 private IntVar last_slot_var_; 85 } 86 Solve(int first_slot)87 private static void Solve(int first_slot) 88 { 89 Console.WriteLine("----------------------------------------------------"); 90 Solver solver = new Solver("SpeakerScheduling"); 91 92 // the slots each speaker is available 93 int[][] speaker_availability = { 94 new int[] { 1, 3, 4, 6, 7, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35, 95 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59 }, 96 new int[] { 1, 2, 7, 8, 10, 11, 16, 17, 18, 21, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38, 97 39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 60 }, 98 new int[] { 5, 6, 7, 10, 12, 14, 16, 17, 21, 22, 23, 24, 33, 35, 37, 38, 99 39, 40, 41, 42, 43, 44, 45, 46, 51, 53, 55, 56, 57, 58, 59 }, 100 new int[] { 1, 2, 3, 4, 5, 6, 7, 11, 13, 14, 15, 16, 20, 24, 25, 33, 34, 35, 37, 38, 101 39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60 }, 102 new int[] { 4, 7, 8, 9, 16, 17, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35, 36, 103 37, 38, 39, 40, 41, 42, 43, 49, 50, 51, 53, 55, 56, 57, 58, 59, 60 }, 104 new int[] { 4, 7, 9, 11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 24, 33, 34, 105 35, 36, 38, 39, 42, 44, 46, 48, 49, 51, 53, 54, 55, 56, 57 }, 106 new int[] { 1, 2, 3, 4, 5, 6, 7, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 54, 55, 56, 57, 58, 59, 60 }, 107 new int[] { 1, 3, 11, 14, 15, 16, 17, 21, 22, 23, 24, 25, 33, 35, 36, 37, 39, 40, 108 41, 42, 43, 44, 45, 47, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }, 109 new int[] { 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 18, 19, 20, 21, 22, 23, 24, 25, 33, 34, 35, 110 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 50, 51, 52, 53, 54, 55, 56, 57, 59, 60 }, 111 new int[] { 24, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 112 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }, 113 new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 114 19, 20, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 115 44, 45, 46, 47, 48, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60 }, 116 new int[] { 3, 4, 5, 6, 13, 15, 16, 17, 18, 19, 21, 22, 24, 25, 33, 34, 35, 117 36, 37, 39, 40, 41, 42, 43, 44, 45, 47, 52, 53, 55, 57, 58, 59, 60 }, 118 new int[] { 4, 5, 6, 8, 11, 12, 13, 14, 17, 19, 20, 22, 23, 24, 25, 33, 34, 119 35, 36, 37, 39, 40, 41, 42, 43, 47, 48, 49, 50, 51, 52, 55, 56, 57 }, 120 new int[] { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 121 20, 21, 22, 23, 24, 25, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 122 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 }, 123 new int[] { 12, 25, 33, 35, 36, 37, 39, 41, 42, 43, 48, 51, 52, 53, 54, 57, 59, 60 }, 124 new int[] { 4, 8, 16, 17, 19, 23, 25, 33, 34, 35, 37, 41, 44, 45, 47, 48, 49, 50 }, 125 new int[] { 3, 23, 24, 25, 33, 35, 36, 37, 38, 39, 40, 42, 43, 44, 49, 50, 53, 54, 55, 56, 57, 58, 60 }, 126 new int[] { 7, 13, 19, 20, 22, 23, 24, 25, 33, 34, 35, 38, 40, 41, 127 42, 44, 45, 46, 47, 48, 49, 52, 53, 54, 58, 59, 60 } 128 }; 129 130 // how long each talk lasts for each speaker 131 int[] durations = { 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; 132 int sum_of_durations = durations.Sum(); 133 134 int number_of_speakers = durations.Length; 135 // calculate the total number of slots (maximum in the availability array) 136 // (and add the max durations) 137 int last_slot = (from s in Enumerable.Range(0, number_of_speakers) select speaker_availability[s].Max()).Max(); 138 Console.WriteLine("Scheduling {0} speakers, for a total of {1} slots, during [{2}..{3}]", number_of_speakers, 139 sum_of_durations, first_slot, last_slot); 140 141 // Start variable for all talks. 142 IntVar[] starts = new IntVar[number_of_speakers]; 143 // We store the possible starts for all talks filtered from the 144 // duration and the speaker availability. 145 int[][] possible_starts = new int [number_of_speakers][]; 146 147 for (int speaker = 0; speaker < number_of_speakers; ++speaker) 148 { 149 int duration = durations[speaker]; 150 // Let's filter the possible starts. 151 List<int> filtered_starts = new List<int>(); 152 int availability = speaker_availability[speaker].Length; 153 for (int index = 0; index < availability; ++index) 154 { 155 bool ok = true; 156 int slot = speaker_availability[speaker][index]; 157 if (slot < first_slot) 158 { 159 continue; 160 } 161 for (int offset = 1; offset < duration; ++offset) 162 { 163 if (index + offset >= availability || 164 speaker_availability[speaker][index + offset] != slot + offset) 165 { 166 // discontinuity. 167 ok = false; 168 break; 169 } 170 } 171 if (ok) 172 { 173 filtered_starts.Add(slot); 174 } 175 possible_starts[speaker] = filtered_starts.ToArray(); 176 } 177 starts[speaker] = solver.MakeIntVar(possible_starts[speaker], "start[" + speaker + "]"); 178 } 179 180 List<IntVar>[] contributions_per_slot = new List<IntVar>[last_slot + 1]; 181 for (int slot = first_slot; slot <= last_slot; ++slot) 182 { 183 contributions_per_slot[slot] = new List<IntVar>(); 184 } 185 for (int speaker = 0; speaker < number_of_speakers; ++speaker) 186 { 187 int duration = durations[speaker]; 188 IntVar start_var = starts[speaker]; 189 foreach (int start in possible_starts[speaker]) 190 { 191 for (int offset = 0; offset < duration; ++offset) 192 { 193 contributions_per_slot[start + offset].Add(start_var.IsEqual(start)); 194 } 195 } 196 } 197 // Force the schedule to be consistent. 198 for (int slot = first_slot; slot <= last_slot; ++slot) 199 { 200 solver.Add(solver.MakeSumLessOrEqual(contributions_per_slot[slot].ToArray(), 1)); 201 } 202 203 // Add minimum start info. 204 for (int speaker = 0; speaker < number_of_speakers; ++speaker) 205 { 206 solver.Add(starts[speaker] >= first_slot); 207 } 208 209 // Creates makespan. 210 IntVar[] end_times = new IntVar[number_of_speakers]; 211 for (int speaker = 0; speaker < number_of_speakers; speaker++) 212 { 213 end_times[speaker] = (starts[speaker] + (durations[speaker] - 1)).Var(); 214 } 215 IntVar last_slot_var = end_times.Max().VarWithName("last_slot"); 216 217 // Add trivial bound to objective. 218 last_slot_var.SetMin(first_slot + sum_of_durations - 1); 219 220 // Redundant scheduling constraint. 221 IntervalVar[] intervals = solver.MakeFixedDurationIntervalVarArray(starts, durations, "intervals"); 222 DisjunctiveConstraint disjunctive = solver.MakeDisjunctiveConstraint(intervals, "disjunctive"); 223 solver.Add(disjunctive); 224 225 // 226 // Search 227 // 228 List<IntVar> short_talks = new List<IntVar>(); 229 List<IntVar> long_talks = new List<IntVar>(); 230 for (int speaker = 0; speaker < number_of_speakers; ++speaker) 231 { 232 if (durations[speaker] == 1) 233 { 234 short_talks.Add(starts[speaker]); 235 } 236 else 237 { 238 long_talks.Add(starts[speaker]); 239 } 240 } 241 OptimizeVar objective_monitor = solver.MakeMinimize(last_slot_var, 1); 242 DecisionBuilder long_phase = 243 solver.MakePhase(long_talks.ToArray(), Solver.CHOOSE_MIN_SIZE_LOWEST_MIN, Solver.ASSIGN_MIN_VALUE); 244 DecisionBuilder short_phase = new FlowAssign(short_talks.ToArray(), first_slot, last_slot_var); 245 DecisionBuilder obj_phase = 246 solver.MakePhase(last_slot_var, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); 247 DecisionBuilder main_phase = solver.Compose(long_phase, short_phase, obj_phase); 248 249 solver.NewSearch(main_phase, objective_monitor); 250 while (solver.NextSolution()) 251 { 252 Console.WriteLine("\nLast used slot: " + (last_slot_var.Value())); 253 Console.WriteLine("Speakers (start..end):"); 254 for (int s = 0; s < number_of_speakers; s++) 255 { 256 long sstart = starts[s].Value(); 257 Console.WriteLine(" - speaker {0,2}: {1,2}..{2,2}", (s + 1), sstart, (sstart + durations[s] - 1)); 258 } 259 } 260 261 Console.WriteLine("\nSolutions: {0}", solver.Solutions()); 262 Console.WriteLine("WallTime: {0}ms", solver.WallTime()); 263 Console.WriteLine("Failures: {0}", solver.Failures()); 264 Console.WriteLine("Branches: {0} ", solver.Branches()); 265 solver.EndSearch(); 266 } 267 Main(String[] args)268 public static void Main(String[] args) 269 { 270 int start = 17; 271 if (args.Length == 1) 272 { 273 start = int.Parse(args[0]); 274 } 275 Stopwatch s = new Stopwatch(); 276 s.Start(); 277 Solve(start); 278 s.Stop(); 279 Console.WriteLine("Finished in " + s.ElapsedMilliseconds + " ms"); 280 } 281 } 282