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