OptaPlanner hilft bei verteilten Schulstandorten (Teil 2/5)

Nachdem der erste Teil dieser Blogserie das fachliche Problem beschreibt, folgt hier der erste Teil der Modellierung.

Modellierung des Problems

In unserem Beispiel muss der Stundenplan nicht komplett neu erstellt werden. Wir können von einem bereits erstellten Stundenplan ausgehen und diesen optimieren. Zur Erstellung der Stundenpläne wird am ONG das weit verbreitete Stundenplanprogramm Untis genutzt. Der damit von der Schulleitung erstellte Stundenplan wird den Schülern und Lehrern u.a. über einen HTML-Export zur Verfügung gestellt. Zur Weiterverarbeitung in externen Programmen stellt das Modul Infostundenplan einen sogenannten Datenbank-Export zur Verfügung.

Eingangsdaten

Über den Datenbank-Export werden alle für den Stundenplan benötigten Daten in einer CSV Datei zur Verfügung gestellt. Für unsere Optimierung ist die von der Exportfunktion erstellte Datei „lesson.txt“ relevant. Im Folgenden ist ein Auszug aus der Datei abgebildet:

Arnd    5   5   Ma  F13 177 1   10.3    ----------------------------------------1------------   0
Arnd    5   6   Ma  F13 177 1   10.3    ----------------------------------------1------------   0
Bau     1   7   Ek  F24 154 0   9.3     ----------------------------------------1------------   0
Bau     1   8   Ek  F24 154 0   9.3     ----------------------------------------1------------   0

Dank der Dokumentation von Untis, lässt sich der Export leicht interpretieren. Der Auszug zeigt beispielsweise, dass der Lehrer Arnd am Freitag der Kalenderwoche 41 in der 5ten und 6ten Stunde für die Klasse 10.3 Mathematik im Raum F13 unterrichtet. Die komplette Datei enthält zu jeder Unterrichtsstunde des gewählten Exportzeitraumes eine Zeile mit den jeweiligen Informationen.

Mit Hilfe des CSV Parser opencsv erzeugen wir für jede Zeile des Exports eine einfache Java Bean und erhalten damit eine Liste aller Unterrichtsstunden des aktuellen Stundenplans als Grundlage für die Optimierung:

public static List csvToLessons(String filename) throws FileNotFoundException, UnsupportedEncodingException {

CSVReader reader = new CSVReader(new InputStreamReader(new FileInputStream(filename), "ISO-8859-1"), '\t');

CsvToBean csvToBean = new CsvToBean();

ColumnPositionMappingStrategy mappingStrategy = new ColumnPositionMappingStrategy();

mappingStrategy.setColumnMapping(new String[]{"teacher&quot", "day","timeslot","course", "room", "id","notused", "grade","week","unknown"});
mappingStrategy.setType(Lesson.class);

List lessons = csvToBean.parse(mappingStrategy, reader);
return lessons;
}

Für die Optimierung sind außerdem die Anordnung der Pausen, welche unterschiedlich lang sind, relevant:

Datenmodell

Das Datenmodell beschreibt das Zuordnungsproblem. Es bildet alle Klassen ab, die den Stundenplan (CourseSchedule) ausmachen. Verschiedene Kurse (Course) werden von jeweils einem Lehrer (Teacher) gegeben und von einer Klasse (Grade) besucht. Die Kurse finden in einer bestimmten Schulstunde statt (Period). An jedem Tag (Day) der Woche steht eine bestimmte Anzahl von Stunden (Timeslot) zu Verfügung. Die Zuordnung von Kurs, Schulstunde und Raum (Room) bildet eine Unterrichtsstunde (Lecture).

Um dieses fachliche Datenmodell mit OptaPlanner nutzen zu können, müssen drei Hauptelemente bekannt gemacht werden:

Hierzu werden die entsprechenden Klassen mit Java Annotationen ausgezeichnet.

Die später von der Planning Engine erstellten Stundenpläne (CourseSchedule) werden mit @PlanningSolution annotiert, implementieren das Interface org.optaplanner.core.api.domain.solution.Solution (genaueres zum Score später) und referenzieren alle Klassen, die das Problem beschreiben: Die zu verplanenden Lectures (annotiert mit @PlanningEntityCollectionProperty) und eine Liste der Schulstunden einer Woche (periods).  Die periods (annotiert mit @ValueRangeProvider) können im Zuge der Planung auf die einzelnen Lectures verteilt werden.

@PlanningSolution
public class CourseSchedule implements Solution {

    private String name;

    private List teachers;
    private List courses;

    private List days;
    private List timeslots;
    private List periods;

    private List rooms;
    private List grades;

    private List lectures;

    @ValueRangeProvider(id = "periodRange")
    public List getPeriods() {
        return periods;
    }

    @PlanningEntityCollectionProperty
    public List getLectures() {
        return lectures;
    }
..

Die Elemente einer PlanningEntityCollection sind unsere Planungsentitäten und die Klasse Lecture wird daher mit @PlanningEntity annotiert. Neben einer Referenz auf den Kurs hält diese zudem eine Referenz auf die von der Planning Engine, im Zuge der Optimierung, zugewiesene Schulstunde @PlanningVariable(valueRangeProviderRefs = {„periodRange“}):

@PlanningEntity
public class Lecture {

private Course course;
private Period period;

private ArrayList subsequentLectures = new ArrayList();
private ArrayList coupledLectures = new ArrayList();

@PlanningVariable(valueRangeProviderRefs = {"periodRange"})
public Period getPeriod() {
return period;
}
}

In dieses Datenmodell können die zuvor importierten Eingangsdaten (LessonCourseScheduleSolutionBuilder) nun überführt werden. In diesem Zug werden auch die zu verplanenden periods erzeugt. Eine so erzeugte initiale Solution bildet den Lösungsraum für die Optimierung.

public class LessonCourseScheduleSolutionBuilder {
..

    @Override
    public Solution extractDomain() {
    ..
        createPeriodListAndDayListAndTimeslotList(schedule, NUMBER_OF_DAYS, NUMBER_OF_TIMESLOTS);

        List<Lecture> lectures = new ArrayList<Lecture>(entities.size());

        long lectureId = 0L;
        for (Lesson current : entities) {

            if (current.getRoom() != null && current.getRoom().isEmpty()) {
                logger.warn("Ignoring lecture without room");
                continue;
            }

            Course c = new Course();
            c.setCode(current.getCourse());
            c.setGrade(findOrCreateGrade(current.getGrade()));
            c.setTeacher(findOrCreateTeacher(current.getTeacher()));

            if (current.getRoom() != null && !current.getRoom().isEmpty())
                c.setRoom(findOrCreateRoom(current.getRoom()));

            Lecture lecture = new Lecture();
            lecture.setId((long) lectureId);
            lectureId++;

            lecture.setCourse(findOrCreateCourse(c));
            lecture.setPeriod(findPeriod(schedule, Integer.parseInt(current.getDay()),
                                            Integer.parseInt(current.getTimeslot())));
            lecture.setUntisId(Integer.parseInt(current.getId()));
            lecture.setWeek(current.getWeek());
            lecture.setUnknown(current.getUnknown());
            lecture.setNotused(current.getNotused());
            lectures.add(lecture);
        }

        ..

        schedule.setCourses(courses);
        schedule.setTeachers(teachers);
        schedule.setGrades(grades);
        schedule.setRooms(rooms);
        schedule.setLectures(lectures);

        return schedule;
    }
    ..
}

Der nächste Teil dieser Serie zeigt den zweiten Teil der Modellierung unseres Problems, die Formulierung der Restriktionen in Form von Drools Regeln.