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