Fold time and space
for maintenance scheduling and
school timetabling

The world is full
of scheduling problems

For example

The world is full
of scheduling problems

Some are automated

Few are optimized

Let's optimize them
with Java and AI

Is optimization worth it?

Vehicle routing case study

Expected: -1% driving time

Result: -25% driving time

⇒ -10 million kg CO² emission per year

⇒ -100 million $ cost per year

Maintenance Scheduling

School timetabling

The web UI

Calculate score

public long calculateScore(TimeTable timeTable) {
    long hardScore = 0;
    for (Lesson lesson1 : timeTable.lessons) {
        for (Lesson lesson2 : timeTable.lessons) {
            if (lesson1.room == lesson2.room
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.teacher == lesson2.teacher
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.studentGroup == lesson2.studentGroup
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
        }
    }
    return hardScore;
}

Greedy algorithm

Greedy code

for (Lesson lesson : timeTable.lessons) {
    long bestScore = Long.MIN_VALUE;
    Room bestRoom = null;
    Timeslot bestTimeslot = null;
    for (Timeslot timeslot : timeTable.timeslots) {
        lesson.setTimeslot(timeslot);
        for (Room room : timeTable.rooms) {
            lesson.setRoom(room);
            long score = calculateScore(timeTable);
            if (score > bestScore) {
                bestScore = score;
                bestRoom = room;
                bestTimeslot = timeslot;
            }
        }
    }
    lesson.setTimeslot(bestTimeslot);
    lesson.setRoom(bestRoom);
}

DEMO

Greedy algorithm

Algorithm comparison

Brute force

Brute force code

long bestScore = Long.MIN_VALUE;
for (Timeslot timeslotLesson1 : timeslots) {
    lesson1.setTimeslot(timeslotLesson1);
    for (Room roomLesson1 : rooms) {
        lesson1.setRoom(roomLesson1);

        for (Timeslot timeslotLesson2 : timeslots) {
            lesson2.setTimeslot(timeslotLesson2);
            for (Room roomLesson2 : rooms) {
                lesson2.setRoom(roomLesson2);
                ...

                for (Timeslot timeslotLessonN : timeslots) {
                    lessonN.setTimeslot(timeslotLessonN);
                    for (Room roomLessonN : rooms) {
                        lessonN.setRoom(roomLessonN);
                        int score = calculateScore(timeTable);
                        if (score > bestScore)
                            ...

DEMO

Brute Force

How big is the search space?

Search space for n lessons: nⁿ

Search space for 400 lessons: 10¹⁰⁴⁰

Atoms in observable universe: 10⁸⁰

Algorithm comparison

Metaheuristics

• Local Search
• Tabu Search
• Simulated Annealing
• Late Acceptance
• ...

+ advanced subsystem algorithms

Implement yourself?

Planning optimization made easy

• Library of optimization algorithms
• AI, not ML
• Open Source (Apache license)
• Actively developed by our Open Core company

Easy score calculator

public HardSoftScore calculateScore(TimeTable timeTable) {
    long hardScore = 0;
    for (Lesson lesson1 : timeTable.lessons) {
        for (Lesson lesson2 : timeTable.lessons) {
            if (lesson1.room == lesson2.room
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.teacher == lesson2.teacher
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.studentGroup == lesson2.studentGroup
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
        }
    }
    return HardSoftScore.of(hardScore, 0);
}

DEMO

Metaheuristics

Algorithm comparison

How good are humans?

Result comparison

Maintenance Scheduling

The web UI

DEMO

Live coding