001package org.cpsolver.ifs.example.tt; 002 003import java.io.File; 004import java.io.FileInputStream; 005import java.io.FileOutputStream; 006import java.io.IOException; 007import java.util.ArrayList; 008import java.util.HashSet; 009import java.util.HashMap; 010import java.util.Iterator; 011import java.util.List; 012import java.util.Map; 013import java.util.Set; 014import java.util.TreeSet; 015 016 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 019import org.cpsolver.ifs.model.Constraint; 020import org.cpsolver.ifs.model.Model; 021import org.cpsolver.ifs.solution.Solution; 022import org.cpsolver.ifs.util.DataProperties; 023import org.cpsolver.ifs.util.ToolBox; 024import org.dom4j.Document; 025import org.dom4j.DocumentException; 026import org.dom4j.DocumentHelper; 027import org.dom4j.Element; 028import org.dom4j.io.OutputFormat; 029import org.dom4j.io.SAXReader; 030import org.dom4j.io.XMLWriter; 031 032/** 033 * Simple Timetabling Problem. <br> 034 * <br> 035 * The problem is modelled in such a way that every lecture was represented by a 036 * variable, resource as a constraint and every possible location of an activity 037 * in the time and space was represented by a single value. It means that a 038 * value stands for a selection of the time (starting time slot), and one of the 039 * available rooms. Binary dependencies are of course represented as constraints 040 * as well. 041 * 042 * @author Tomáš Müller 043 * @version IFS 1.3 (Iterative Forward Search)<br> 044 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 045 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 046 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 047 * <br> 048 * This library is free software; you can redistribute it and/or modify 049 * it under the terms of the GNU Lesser General Public License as 050 * published by the Free Software Foundation; either version 3 of the 051 * License, or (at your option) any later version. <br> 052 * <br> 053 * This library is distributed in the hope that it will be useful, but 054 * WITHOUT ANY WARRANTY; without even the implied warranty of 055 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 056 * Lesser General Public License for more details. <br> 057 * <br> 058 * You should have received a copy of the GNU Lesser General Public 059 * License along with this library; if not see 060 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 061 */ 062public class TimetableModel extends Model<Activity, Location> { 063 private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(TimetableModel.class); 064 private int iNrDays, iNrHours; 065 066 public TimetableModel(int nrDays, int nrHours) { 067 super(); 068 iNrDays = nrDays; 069 iNrHours = nrHours; 070 } 071 072 public int getNrDays() { 073 return iNrDays; 074 } 075 076 public int getNrHours() { 077 return iNrHours; 078 } 079 080 @SuppressWarnings("unchecked") 081 public static TimetableModel generate(DataProperties cfg, Assignment<Activity, Location> assignment) { 082 int nrDays = cfg.getPropertyInt("Generator.NrDays", 5); 083 int nrHours = cfg.getPropertyInt("Generator.NrHours", 20); 084 int nrSlots = nrDays * nrHours; 085 TimetableModel m = new TimetableModel(nrDays, nrHours); 086 087 int nrRooms = cfg.getPropertyInt("Generator.NrRooms", 20); 088 int nrInstructors = cfg.getPropertyInt("Generator.NrInstructors", 20); 089 int nrClasses = cfg.getPropertyInt("Generator.NrClasses", 20); 090 int nrGroupsOfRooms = cfg.getPropertyInt("Generator.NrGroupsOfRooms", 20); 091 int nrRoomsInGroupMin = cfg.getPropertyInt("Generator.NrRoomsInGroupMin", 1); 092 int nrRoomsInGroupMax = cfg.getPropertyInt("Generator.NrRoomsInGroupMax", 10); 093 int nrRoomInGroupMin = cfg.getPropertyInt("Generator.NrRoomInGroupMin", 1); 094 double fillFactor = cfg.getPropertyDouble("Generator.FillFactor", 0.8); 095 int maxLength = cfg.getPropertyInt("Generator.ActivityLengthMax", 5); 096 double hardFreeResource = cfg.getPropertyDouble("Generator.HardFreeResource", 0.05); 097 double softFreeResource = cfg.getPropertyDouble("Generator.SoftFreeResource", 0.3); 098 double softUsedResource = cfg.getPropertyDouble("Generator.SoftUsedResource", 0.05); 099 double softUsedActivity = cfg.getPropertyDouble("Generator.SoftUsedActivity", 0.05); 100 double softFreeActivity = cfg.getPropertyDouble("Generator.SoftFreeActivity", 0.3); 101 double hardFreeActivity = cfg.getPropertyDouble("Generator.HardFreeActivity", 0.05); 102 int nrDependencies = cfg.getPropertyInt("Generator.NrDependencies", 50); 103 104 Resource rooms[] = new Resource[nrRooms]; 105 ArrayList<ArrayList<Resource>> groupForRoom[] = new ArrayList[nrRooms]; 106 for (int i = 0; i < nrRooms; i++) { 107 rooms[i] = new Resource("r" + (i + 1), Resource.TYPE_ROOM, "Room " + (i + 1)); 108 groupForRoom[i] = new ArrayList<ArrayList<Resource>>(); 109 m.addConstraint(rooms[i]); 110 } 111 ArrayList<Resource> groupOfRooms[] = new ArrayList[nrGroupsOfRooms]; 112 for (int i = 0; i < nrGroupsOfRooms; i++) { 113 groupOfRooms[i] = new ArrayList<Resource>(); 114 for (int j = 0; j < ToolBox.random(1 + nrRoomsInGroupMax - nrRoomsInGroupMin) + nrRoomsInGroupMin; j++) { 115 int r = 0; 116 do { 117 r = ToolBox.random(nrRooms); 118 } while (groupOfRooms[i].contains(rooms[r])); 119 groupOfRooms[i].add(rooms[r]); 120 groupForRoom[r].add(groupOfRooms[i]); 121 } 122 } 123 for (int i = 0; i < nrRooms; i++) { 124 int cnt = 0; 125 for (int j = 0; j < nrGroupsOfRooms; j++) 126 if (groupOfRooms[j].contains(rooms[i])) 127 cnt++; 128 while (cnt < nrRoomInGroupMin) { 129 int r = 0; 130 do { 131 r = ToolBox.random(nrGroupsOfRooms); 132 } while (groupOfRooms[r].contains(rooms[i])); 133 groupOfRooms[r].add(rooms[i]); 134 groupForRoom[i].add(groupOfRooms[r]); 135 cnt++; 136 } 137 } 138 Resource instructors[] = new Resource[nrInstructors]; 139 for (int i = 0; i < nrInstructors; i++) { 140 instructors[i] = new Resource("t" + (i + 1), Resource.TYPE_INSTRUCTOR, "Teacher " + (i + 1)); 141 m.addConstraint(instructors[i]); 142 } 143 Resource classes[] = new Resource[nrClasses]; 144 for (int i = 0; i < nrClasses; i++) { 145 classes[i] = new Resource("c" + (i + 1), Resource.TYPE_CLASS, "Class " + (i + 1)); 146 m.addConstraint(classes[i]); 147 } 148 149 int[][] timetable4room = new int[nrRooms][nrSlots]; 150 int[][] timetable4instr = new int[nrInstructors][nrSlots]; 151 int[][] timetable4class = new int[nrClasses][nrSlots]; 152 int act = 0; 153 for (int i = 0; i < timetable4room.length; i++) 154 for (int j = 0; j < timetable4room[i].length; j++) 155 timetable4room[i][j] = 0; 156 for (int i = 0; i < timetable4instr.length; i++) 157 for (int j = 0; j < timetable4instr[i].length; j++) 158 timetable4instr[i][j] = 0; 159 for (int i = 0; i < timetable4class.length; i++) 160 for (int j = 0; j < timetable4class[i].length; j++) 161 timetable4class[i][j] = 0; 162 163 int totalSlots = nrRooms * nrSlots; 164 int usedSlots = 0; 165 ArrayList<Integer> starts = new ArrayList<Integer>(); 166 ArrayList<Integer> arooms = new ArrayList<Integer>(); 167 while ((((double) usedSlots / ((double) totalSlots))) < fillFactor) { 168 int attempt = 0; 169 int slot = ToolBox.random(nrSlots); 170 int room = ToolBox.random(nrRooms); 171 while (attempt < 500 && timetable4room[room][slot] != 0) { 172 slot = ToolBox.random(nrSlots); 173 room = ToolBox.random(nrRooms); 174 } 175 if (attempt == 500) { 176 int s = slot; 177 int r = room; 178 while (timetable4room[r][s] != 0) { 179 r++; 180 if (r == nrRooms) 181 r = 0; 182 if (r == room) 183 s++; 184 if (s == nrSlots) 185 s = 0; 186 } 187 slot = s; 188 room = r; 189 } 190 int length = maxLength;// ToolBox.random(maxLength)+1; 191 int aclass = ToolBox.random(nrClasses); 192 int instr = ToolBox.random(nrInstructors); 193 attempt = 0; 194 while (attempt < 500 && (timetable4class[aclass][slot] != 0 || timetable4instr[instr][slot] != 0)) { 195 aclass = ToolBox.random(nrClasses); 196 instr = ToolBox.random(nrInstructors); 197 } 198 if (attempt == 500) 199 continue; 200 int len = 1; 201 while (len < length) { 202 if ((((slot + len) % nrHours) != 0) && timetable4room[room][slot + len] == 0 203 && timetable4instr[instr][slot + len] == 0 && timetable4class[aclass][slot + len] == 0) 204 len++; 205 else 206 break; 207 } 208 ArrayList<Resource> roomGr = ToolBox.random(groupForRoom[room]); 209 act++; 210 usedSlots += len; 211 Activity a = new Activity(len, "a" + act, "Activity " + act); 212 a.addResourceGroup(roomGr); 213 a.addResourceGroup(instructors[instr]); 214 a.addResourceGroup(classes[aclass]); 215 m.addVariable(a); 216 starts.add(slot); 217 arooms.add(room); 218 for (int i = slot; i < slot + len; i++) { 219 timetable4room[room][i] = act; 220 timetable4instr[instr][i] = act; 221 timetable4class[aclass][i] = act; 222 } 223 } 224 int nrHardFreeRes = 0; 225 int nrSoftFreeRes = 0; 226 int nrSoftUsedRes = 0; 227 for (int slot = 0; slot < nrSlots; slot++) { 228 for (int room = 0; room < nrRooms; room++) { 229 if (timetable4room[room][slot] == 0) { 230 if (ToolBox.random() < hardFreeResource) { 231 nrHardFreeRes++; 232 rooms[room].addProhibitedSlot(slot); 233 } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) { 234 nrSoftFreeRes++; 235 rooms[room].addDiscouragedSlot(slot); 236 } 237 } else if (ToolBox.random() < softUsedResource) { 238 nrSoftUsedRes++; 239 rooms[room].addDiscouragedSlot(slot); 240 } 241 } 242 for (int instr = 0; instr < nrInstructors; instr++) { 243 if (timetable4instr[instr][slot] == 0) { 244 if (ToolBox.random() < hardFreeResource) { 245 nrHardFreeRes++; 246 instructors[instr].addProhibitedSlot(slot); 247 } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) { 248 nrSoftFreeRes++; 249 instructors[instr].addDiscouragedSlot(slot); 250 } 251 } else if (ToolBox.random() < softUsedResource) { 252 nrSoftUsedRes++; 253 instructors[instr].addDiscouragedSlot(slot); 254 } 255 } 256 for (int aclass = 0; aclass < nrClasses; aclass++) { 257 if (timetable4class[aclass][slot] == 0) { 258 if (ToolBox.random() < hardFreeResource) { 259 nrHardFreeRes++; 260 classes[aclass].addProhibitedSlot(slot); 261 } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) { 262 nrSoftFreeRes++; 263 classes[aclass].addDiscouragedSlot(slot); 264 } 265 } else if (ToolBox.random() < softUsedResource) { 266 nrSoftUsedRes++; 267 classes[aclass].addDiscouragedSlot(slot); 268 } 269 } 270 } 271 int nrSoftFreeAct = 0; 272 int nrSoftUsedAct = 0; 273 int nrHardFreeAct = 0; 274 for (int i = 0; i < m.variables().size(); i++) { 275 Activity activity = m.variables().get(i); 276 for (int slot = 0; slot < nrSlots; slot++) { 277 int start = starts.get(i); 278 if (slot < start || slot >= start + activity.getLength()) { 279 if (ToolBox.random() < hardFreeActivity) { 280 nrHardFreeAct++; 281 activity.addProhibitedSlot(slot); 282 } else if (ToolBox.random() < (softFreeActivity / (1.0 - hardFreeActivity))) { 283 nrSoftFreeAct++; 284 activity.addDiscouragedSlot(slot); 285 } 286 } else { 287 if (ToolBox.random() < softUsedActivity) { 288 nrSoftUsedAct++; 289 activity.addDiscouragedSlot(slot); 290 } 291 } 292 } 293 activity.init(); 294 } 295 for (int i = 0; i < nrDependencies;) { 296 int ac1 = ToolBox.random(m.variables().size()); 297 int ac2 = ToolBox.random(m.variables().size()); 298 while (ac1 == ac2) { 299 ac2 = ToolBox.random(m.variables().size()); 300 } 301 int s1 = starts.get(ac1); 302 int s2 = starts.get(ac2); 303 Activity a1 = m.variables().get(ac1); 304 Activity a2 = m.variables().get(ac2); 305 Dependence dep = null; 306 if (s1 < s2) { 307 if (s1 + a1.getLength() == s2) 308 dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_BEFORE); 309 else if (s1 + a1.getLength() < s2) 310 dep = new Dependence("d" + (i + 1), Dependence.TYPE_BEFORE); 311 } else { 312 if (s2 == s1 + a1.getLength()) 313 dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_AFTER); 314 else if (s2 > s1 + a1.getLength()) 315 dep = new Dependence("d" + (i + 1), Dependence.TYPE_AFTER); 316 } 317 if (dep != null) { 318 dep.addVariable(a1); 319 dep.addVariable(a2); 320 m.addConstraint(dep); 321 i++; 322 } 323 } 324 for (int i = 0; i < m.variables().size(); i++) { 325 Activity activity = m.variables().get(i); 326 // sLogger.debug("-- processing activity "+activity.getName()); 327 int start = starts.get(i); 328 int room = arooms.get(i); 329 Location location = null; 330 for (Location l : activity.values(assignment)) { 331 if (l.getSlot() == start && l.getResource(0).getResourceId().equals("r" + (room + 1))) { 332 location = l; 333 break; 334 } 335 } 336 if (location != null) { 337 Set<Location> conflicts = m.conflictValues(assignment, location); 338 if (!conflicts.isEmpty()) { 339 sLogger.warn("Unable to assign " + location.getName() + " to " + activity.getName() + ", reason:"); 340 for (Constraint<Activity, Location> c : activity.constraints()) { 341 Set<Location> cc = new HashSet<Location>(); 342 c.computeConflicts(assignment, location, cc); 343 if (!cc.isEmpty()) 344 sLogger.warn(" -- Constraint " + c.getName() + " causes conflicts " + cc); 345 } 346 } else { 347 assignment.assign(0, location); 348 activity.setInitialAssignment(location); 349 } 350 // sLogger.debug(" -- location "+location.getName()+" found"); 351 activity.setInitialAssignment(location); 352 } else { 353 sLogger.warn("Unable to assign " + activity.getName() + " -- no location matching slot=" + start 354 + " room='R" + (room + 1) + "'"); 355 } 356 } 357 if (!cfg.getPropertyBoolean("General.InitialAssignment", true)) { 358 for (int i = 0; i < m.variables().size(); i++) { 359 Activity activity = m.variables().get(i); 360 assignment.unassign(0, activity); 361 } 362 } 363 364 int forcedPerturbances = cfg.getPropertyInt("General.ForcedPerturbances", 0); 365 if (forcedPerturbances > 0) { 366 List<Activity> initialVariables = new ArrayList<Activity>(); 367 for (Activity v : m.variables()) { 368 if (v.getInitialAssignment() != null) 369 initialVariables.add(v); 370 } 371 for (int i = 0; i < forcedPerturbances; i++) { 372 if (initialVariables.isEmpty()) 373 break; 374 Activity var = ToolBox.random(initialVariables); 375 initialVariables.remove(var); 376 var.removeInitialValue(); 377 } 378 } 379 380 sLogger.debug("-- Generator Info ---------------------------------------------------------"); 381 sLogger.debug(" Total number of " + m.variables().size() + " activities generated."); 382 sLogger.debug(" Total number of " + usedSlots + " slots are filled (" + ((100.0 * usedSlots) / totalSlots) 383 + "% filled)."); 384 sLogger.debug(" Average length of an activity is " + (((double) usedSlots) / m.variables().size())); 385 sLogger.debug(" Total number of hard constraints posted on free slots on activities: " + nrHardFreeAct); 386 sLogger.debug(" Total number of soft constraints posted on free slots on activities: " + nrSoftFreeAct); 387 sLogger.debug(" Total number of soft constraints posted on used slots on activities: " + nrSoftUsedAct); 388 sLogger.debug(" Total number of hard constraints posted on free slots on resources: " + nrHardFreeRes); 389 sLogger.debug(" Total number of soft constraints posted on free slots on resources: " + nrSoftFreeRes); 390 sLogger.debug(" Total number of soft constraints posted on used slots on resources: " + nrSoftUsedRes); 391 sLogger.debug(" Total number of " + nrDependencies + " dependencies generated."); 392 sLogger.debug("---------------------------------------------------------------------------"); 393 394 return m; 395 } 396 397 public static void main(String[] args) { 398 try { 399 // Configure logging 400 ToolBox.configureLogging(); 401 402 // Load properties (take first argument as input file, containing key=value lines) 403 DataProperties properties = new DataProperties(); 404 properties.load(new FileInputStream(args[0])); 405 406 // Generate model 407 Assignment<Activity, Location> assignment = new DefaultSingleAssignment<Activity, Location>(); 408 TimetableModel model = TimetableModel.generate(new DataProperties(), assignment); 409 System.out.println(model.getInfo(assignment)); 410 411 // Save solution (take second argument as output file) 412 model.saveAsXML(properties, true, new Solution<Activity, Location>(model, assignment), assignment, new File(args[1])); 413 } catch (Exception e) { 414 e.printStackTrace(); 415 } 416 } 417 418 public void saveAsXML(DataProperties cfg, boolean gen, Solution<Activity, Location> solution, Assignment<Activity, Location> assignment, File outFile) throws IOException { 419 outFile.getParentFile().mkdirs(); 420 sLogger.debug("Writting XML data to:" + outFile); 421 422 Document document = DocumentHelper.createDocument(); 423 document.addComment("Interactive Timetabling - University Timetable Generator (version 2.0)"); 424 if (assignment == null && solution != null) 425 assignment = solution.getAssignment(); 426 if (assignment == null) 427 assignment = new DefaultSingleAssignment<Activity, Location>(); 428 429 if (!assignedVariables(assignment).isEmpty()) { 430 StringBuffer comments = new StringBuffer("Solution Info:\n"); 431 Map<String, String> solutionInfo = (solution == null ? getInfo(assignment) : solution.getInfo()); 432 for (String key : new TreeSet<String>(solutionInfo.keySet())) { 433 String value = solutionInfo.get(key); 434 comments.append(" " + key + ": " + value + "\n"); 435 } 436 document.addComment(comments.toString()); 437 } 438 439 Element root = document.addElement("Timetable"); 440 if (gen) { 441 Element generator = root.addElement("Generator"); 442 generator.addAttribute("version", "2.0"); 443 generator.addElement("DaysPerWeek").setText(String.valueOf(iNrDays)); 444 generator.addElement("SlotsPerDay").setText(String.valueOf(iNrHours)); 445 generator.addElement("NrRooms").setText(cfg.getProperty("Generator.NrRooms", "20")); 446 generator.addElement("NrInstructors").setText(cfg.getProperty("Generator.NrInstructors", "20")); 447 generator.addElement("NrClasses").setText(cfg.getProperty("Generator.NrClasses", "20")); 448 generator.addElement("FillFactor").setText(cfg.getProperty("Generator.FillFactor", "0.8")); 449 generator.addElement("ActivityLengthMax").setText(cfg.getProperty("Generator.ActivityLengthMax", "5")); 450 generator.addElement("NrGroupsOfRooms").setText(cfg.getProperty("Generator.NrGroupsOfRooms", "20")); 451 generator.addElement("NrRoomsInGroupMin").setText(cfg.getProperty("Generator.NrRoomsInGroupMin", "1")); 452 generator.addElement("NrRoomsInGroupMax").setText(cfg.getProperty("Generator.NrRoomsInGroupMax", "10")); 453 generator.addElement("NrRoomInGroupMin").setText(cfg.getProperty("Generator.NrRoomInGroupMin", "1")); 454 generator.addElement("HardFreeResource").setText(cfg.getProperty("Generator.HardFreeResource", "0.05")); 455 generator.addElement("SoftFreeResource").setText(cfg.getProperty("Generator.SoftFreeResource", "0.3")); 456 generator.addElement("SoftUsedResource").setText(cfg.getProperty("Generator.SoftUsedResource", "0.05")); 457 generator.addElement("SoftUsedActivity").setText(cfg.getProperty("Generator.SoftUsedActivity", "0.05")); 458 generator.addElement("SoftFreeActivity").setText(cfg.getProperty("Generator.SoftFreeActivity", "0.3")); 459 generator.addElement("HardFreeActivity").setText(cfg.getProperty("Generator.HardFreeActivity", "0.05")); 460 generator.addElement("NrDependencies").setText(cfg.getProperty("Generator.NrDependencies", "50")); 461 } 462 463 ArrayList<Resource> rooms = new ArrayList<Resource>(); 464 ArrayList<Resource> classes = new ArrayList<Resource>(); 465 ArrayList<Resource> instructors = new ArrayList<Resource>(); 466 ArrayList<Resource> specials = new ArrayList<Resource>(); 467 ArrayList<Dependence> dependencies = new ArrayList<Dependence>(); 468 469 for (Constraint<Activity, Location> c : constraints()) { 470 if (c instanceof Resource) { 471 Resource r = (Resource) c; 472 switch (r.getType()) { 473 case Resource.TYPE_ROOM: 474 rooms.add(r); 475 break; 476 case Resource.TYPE_CLASS: 477 classes.add(r); 478 break; 479 case Resource.TYPE_INSTRUCTOR: 480 instructors.add(r); 481 break; 482 default: 483 specials.add(r); 484 } 485 } else if (c instanceof Dependence) { 486 dependencies.add((Dependence) c); 487 } 488 } 489 490 Element problem = root.addElement("Problem"); 491 problem.addAttribute("version", "2.0"); 492 Element problemGen = problem.addElement("General"); 493 problemGen.addElement("DaysPerWeek").setText(String.valueOf(iNrDays)); 494 problemGen.addElement("SlotsPerDay").setText(String.valueOf(iNrHours)); 495 Element resourceGen = problemGen.addElement("Resources"); 496 resourceGen.addElement("Classrooms").setText(String.valueOf(rooms.size())); 497 resourceGen.addElement("Teachers").setText(String.valueOf(instructors.size())); 498 resourceGen.addElement("Classes").setText(String.valueOf(classes.size())); 499 resourceGen.addElement("Special").setText(String.valueOf(specials.size())); 500 problemGen.addElement("Activities").setText(String.valueOf(variables().size())); 501 problemGen.addElement("Dependences").setText(String.valueOf(dependencies.size())); 502 503 Element resources = problem.addElement("Resources"); 504 505 Element resEl = resources.addElement("Classrooms"); 506 for (Resource r : rooms) { 507 Element el = resEl.addElement("Resource"); 508 el.addAttribute("id", r.getResourceId()); 509 el.addElement("Name").setText(r.getName()); 510 Element pref = el.addElement("TimePreferences"); 511 for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots())) 512 pref.addElement("Soft").setText(slot.toString()); 513 for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots())) 514 pref.addElement("Hard").setText(slot.toString()); 515 } 516 517 resEl = resources.addElement("Teachers"); 518 for (Resource r : instructors) { 519 Element el = resEl.addElement("Resource"); 520 el.addAttribute("id", r.getResourceId()); 521 el.addElement("Name").setText(r.getName()); 522 Element pref = el.addElement("TimePreferences"); 523 for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots())) 524 pref.addElement("Soft").setText(slot.toString()); 525 for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots())) 526 pref.addElement("Hard").setText(slot.toString()); 527 } 528 529 resEl = resources.addElement("Classes"); 530 for (Resource r : classes) { 531 Element el = resEl.addElement("Resource"); 532 el.addAttribute("id", r.getResourceId()); 533 el.addElement("Name").setText(r.getName()); 534 Element pref = el.addElement("TimePreferences"); 535 for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots())) 536 pref.addElement("Soft").setText(slot.toString()); 537 for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots())) 538 pref.addElement("Hard").setText(slot.toString()); 539 } 540 541 resEl = resources.addElement("Special"); 542 for (Resource r : specials) { 543 Element el = resEl.addElement("Resource"); 544 el.addAttribute("id", r.getResourceId()); 545 el.addElement("Name").setText(r.getName()); 546 Element pref = el.addElement("TimePreferences"); 547 for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots())) 548 pref.addElement("Soft").setText(slot.toString()); 549 for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots())) 550 pref.addElement("Hard").setText(slot.toString()); 551 } 552 553 boolean hasSolution = false; 554 Element actEl = problem.addElement("Activities"); 555 for (Activity a : variables()) { 556 Element el = actEl.addElement("Activity"); 557 el.addAttribute("id", a.getActivityId()); 558 el.addElement("Name").setText(a.getName()); 559 el.addElement("Length").setText(String.valueOf(a.getLength())); 560 if (assignment.getValue(a) != null) 561 hasSolution = true; 562 Element pref = el.addElement("TimePreferences"); 563 for (Integer slot : new TreeSet<Integer>(a.getDiscouragedSlots())) 564 pref.addElement("Soft").setText(slot.toString()); 565 for (Integer slot : new TreeSet<Integer>(a.getProhibitedSlots())) 566 pref.addElement("Hard").setText(slot.toString()); 567 Element reqRes = el.addElement("RequiredResources"); 568 for (List<Resource> gr : a.getResourceGroups()) { 569 if (gr.size() == 1) { 570 reqRes.addElement("Resource").setText(gr.get(0).getResourceId()); 571 } else { 572 Element grEl = reqRes.addElement("Group").addAttribute("conjunctive", "no"); 573 for (Resource r : gr) 574 grEl.addElement("Resource").setText(r.getResourceId()); 575 } 576 } 577 } 578 579 Element depEl = problem.addElement("Dependences"); 580 for (Dependence d : dependencies) { 581 Element el = depEl.addElement("Dependence"); 582 el.addAttribute("id", d.getResourceId()); 583 el.addElement("FirstActivity").setText((d.first()).getActivityId()); 584 el.addElement("SecondActivity").setText((d.second()).getActivityId()); 585 switch (d.getType()) { 586 case Dependence.TYPE_AFTER: 587 el.addElement("Operator").setText("After"); 588 break; 589 case Dependence.TYPE_BEFORE: 590 el.addElement("Operator").setText("Before"); 591 break; 592 case Dependence.TYPE_CLOSELY_BEFORE: 593 el.addElement("Operator").setText("Closely before"); 594 break; 595 case Dependence.TYPE_CLOSELY_AFTER: 596 el.addElement("Operator").setText("Closely after"); 597 break; 598 case Dependence.TYPE_CONCURRENCY: 599 el.addElement("Operator").setText("Concurrently"); 600 break; 601 default: 602 el.addElement("Operator").setText("Unknown"); 603 } 604 } 605 606 if (hasSolution) { 607 Element solutionEl = root.addElement("Solution"); 608 solutionEl.addAttribute("version", "2.0"); 609 for (Activity a : variables()) { 610 Element el = solutionEl.addElement("Activity"); 611 el.addAttribute("id", a.getActivityId()); 612 Location location = assignment.getValue(a); 613 if (location != null) { 614 el.addElement("StartTime").setText(String.valueOf(location.getSlot())); 615 Element res = el.addElement("UsedResources"); 616 for (int i = 0; i < location.getResources().length; i++) 617 res.addElement("Resource").setText(location.getResources()[i].getResourceId()); 618 } 619 } 620 } 621 622 FileOutputStream fos = new FileOutputStream(outFile); 623 (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document); 624 fos.flush(); 625 fos.close(); 626 } 627 628 public static TimetableModel loadFromXML(File inFile, Assignment<Activity, Location> assignment) throws IOException, DocumentException { 629 Document document = (new SAXReader()).read(inFile); 630 Element root = document.getRootElement(); 631 if (!"Timetable".equals(root.getName())) { 632 sLogger.error("Given XML file is not interactive timetabling problem."); 633 return null; 634 } 635 636 Element problem = root.element("Problem"); 637 Element problemGen = problem.element("General"); 638 TimetableModel m = new TimetableModel(Integer.parseInt(problemGen.elementText("DaysPerWeek")), Integer 639 .parseInt(problemGen.elementText("SlotsPerDay"))); 640 641 Element resources = problem.element("Resources"); 642 643 HashMap<String, Resource> resTab = new HashMap<String, Resource>(); 644 645 Element resEl = resources.element("Classrooms"); 646 for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) { 647 Element el = (Element) i.next(); 648 Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_ROOM, el.elementText("Name")); 649 Element pref = el.element("TimePreferences"); 650 for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();) 651 r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText())); 652 for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();) 653 r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText())); 654 m.addConstraint(r); 655 resTab.put(r.getResourceId(), r); 656 } 657 658 resEl = resources.element("Teachers"); 659 for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) { 660 Element el = (Element) i.next(); 661 Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_INSTRUCTOR, el.elementText("Name")); 662 Element pref = el.element("TimePreferences"); 663 for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();) 664 r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText())); 665 for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();) 666 r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText())); 667 m.addConstraint(r); 668 resTab.put(r.getResourceId(), r); 669 } 670 671 resEl = resources.element("Classes"); 672 for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) { 673 Element el = (Element) i.next(); 674 Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_CLASS, el.elementText("Name")); 675 Element pref = el.element("TimePreferences"); 676 for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();) 677 r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText())); 678 for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();) 679 r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText())); 680 m.addConstraint(r); 681 resTab.put(r.getResourceId(), r); 682 } 683 684 resEl = resources.element("Special"); 685 for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) { 686 Element el = (Element) i.next(); 687 Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_OTHER, el.elementText("Name")); 688 Element pref = el.element("TimePreferences"); 689 for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();) 690 r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText())); 691 for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();) 692 r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText())); 693 m.addConstraint(r); 694 resTab.put(r.getResourceId(), r); 695 } 696 697 Element actEl = problem.element("Activities"); 698 HashMap<String, Activity> actTab = new HashMap<String, Activity>(); 699 for (Iterator<?> i = actEl.elementIterator("Activity"); i.hasNext();) { 700 Element el = (Element) i.next(); 701 Activity a = new Activity(Integer.parseInt(el.elementText("Length")), el.attributeValue("id"), el 702 .elementText("Name")); 703 Element pref = el.element("TimePreferences"); 704 for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();) 705 a.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText())); 706 for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();) 707 a.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText())); 708 Element req = el.element("RequiredResources"); 709 for (Iterator<?> j = req.elementIterator(); j.hasNext();) { 710 Element rqEl = (Element) j.next(); 711 if ("Resource".equals(rqEl.getName())) { 712 a.addResourceGroup(resTab.get(rqEl.getText())); 713 } else if ("Group".equals(rqEl.getName())) { 714 if ("no".equalsIgnoreCase(rqEl.attributeValue("conjunctive")) 715 || "false".equalsIgnoreCase(rqEl.attributeValue("conjunctive"))) { 716 List<Resource> gr = new ArrayList<Resource>(); 717 for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();) 718 gr.add(resTab.get(((Element) k.next()).getText())); 719 a.addResourceGroup(gr); 720 } else { 721 for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();) 722 a.addResourceGroup(resTab.get(((Element) k.next()).getText())); 723 } 724 } 725 } 726 m.addVariable(a); 727 a.init(); 728 actTab.put(a.getActivityId(), a); 729 } 730 731 Element depEl = problem.element("Dependences"); 732 for (Iterator<?> i = depEl.elementIterator("Dependence"); i.hasNext();) { 733 Element el = (Element) i.next(); 734 int type = Dependence.TYPE_NO_DEPENDENCE; 735 String typeStr = el.elementText("Operator"); 736 if ("After".equals(typeStr)) 737 type = Dependence.TYPE_AFTER; 738 else if ("Before".equals(typeStr)) 739 type = Dependence.TYPE_BEFORE; 740 else if ("After".equals(typeStr)) 741 type = Dependence.TYPE_AFTER; 742 else if ("Closely before".equals(typeStr)) 743 type = Dependence.TYPE_CLOSELY_BEFORE; 744 else if ("Closely after".equals(typeStr)) 745 type = Dependence.TYPE_CLOSELY_AFTER; 746 else if ("Concurrently".equals(typeStr)) 747 type = Dependence.TYPE_CONCURRENCY; 748 Dependence d = new Dependence(el.attributeValue("id"), type); 749 d.addVariable(actTab.get(el.elementText("FirstActivity"))); 750 d.addVariable(actTab.get(el.elementText("SecondActivity"))); 751 m.addConstraint(d); 752 } 753 754 Element solEl = root.element("Solution"); 755 if (solEl != null) { 756 for (Iterator<?> i = solEl.elementIterator("Activity"); i.hasNext();) { 757 Element el = (Element) i.next(); 758 Activity a = actTab.get(el.attributeValue("id")); 759 if (a == null) 760 continue; 761 int slot = Integer.parseInt(el.elementText("StartTime")); 762 Element usResEl = el.element("UsedResources"); 763 List<Resource> res = new ArrayList<Resource>(); 764 for (Iterator<?> j = usResEl.elementIterator("Resource"); j.hasNext();) 765 res.add(resTab.get(((Element) j.next()).getText())); 766 for (Location loc : a.values(assignment)) { 767 if (loc.getSlot() != slot || loc.getResources().length != res.size()) 768 continue; 769 boolean same = true; 770 for (int j = 0; j < loc.getResources().length && same; j++) 771 if (!res.get(j).equals(loc.getResources()[j])) 772 same = false; 773 if (!same) 774 continue; 775 a.setInitialAssignment(loc); 776 if (assignment != null) 777 assignment.assign(0, loc); 778 break; 779 } 780 } 781 } 782 return m; 783 } 784}