001 package net.sf.cpsolver.ifs.example.tt;
002
003 import java.io.File;
004 import java.io.FileInputStream;
005 import java.io.FileOutputStream;
006 import java.io.IOException;
007 import java.util.ArrayList;
008 import java.util.HashSet;
009 import java.util.HashMap;
010 import java.util.Iterator;
011 import java.util.List;
012 import java.util.Map;
013 import java.util.Set;
014 import java.util.TreeSet;
015
016 import net.sf.cpsolver.ifs.model.Constraint;
017 import net.sf.cpsolver.ifs.model.Model;
018 import net.sf.cpsolver.ifs.solution.Solution;
019 import net.sf.cpsolver.ifs.util.DataProperties;
020 import net.sf.cpsolver.ifs.util.ToolBox;
021
022 import org.dom4j.Document;
023 import org.dom4j.DocumentException;
024 import org.dom4j.DocumentHelper;
025 import org.dom4j.Element;
026 import org.dom4j.io.OutputFormat;
027 import org.dom4j.io.SAXReader;
028 import 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 Tomas Muller<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 */
059 public 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 }