How to avoid gaps between lessons for the same student group?

[MichelFonseca1024]

I’m using Timefold (Java) to generate school timetables, with lesson times ranging from 7 AM to 10 PM. However, I’m facing an issue where some student groups end up with gaps between their lessons. For example, a group that should have consecutive lessons from 7 AM to 12 PM ends up with a gap between 10 AM and 11 AM.

I’d like to implement a constraint to penalize (or prohibit) gaps between lessons for the same student group on the same day, encouraging continuous blocks of lessons. I’ve tried implementing this logic as a Constraint, but haven’t had success so far.

Is there a recommended way to handle this kind of restriction in Timefold? Are there any similar examples?

Thanks in advance for your help!

[Christopher-Chianelli]

There are two ways to can do this:

Reward pairs of consecutive lessons (this is what done in the school timetabling quickstart in teacherTimeEfficiency)

    // reward consecutive lessons
    Constraint studentGroupTimeEfficiency(ConstraintFactory constraintFactory) {
        // A student group should have consecutive lessons
        return constraintFactory
                .forEach(Lesson.class)
                .join(Lesson.class, Joiners.equal(Lesson::getStudentGroup),
                        Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()))
                .filter((lesson1, lesson2) -> {
                    Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),
                            lesson2.getTimeslot().getStartTime());
                    return !between.isNegative() && between.compareTo(Duration.ofMinutes(30)) <= 0;
                })
                .reward(HardSoftScore.ONE_SOFT)
                .asConstraint("Student group time efficiency");
    }

Penalize gaps between lessons:

    Constraint studentGroupTimeEfficiency(ConstraintFactory constraintFactory) {
        // A student group should have consecutive lessons
        return constraintFactory
                .forEach(Lesson.class)
                .groupBy(Lesson::getStudentGroup, lesson -> lesson.getTimeslot().getDayOfWeek(),
                         ConstraintCollectors.toConnectedTemporalRanges(Lesson::getStartTime, Lesson::getEndTime))
                .flattenLast(ConnectedRangeChain::getGaps)
                .peanalize(HardSoftScore.ONE_SOFT, gap -> (int) gap.getLength().dividedBy(Duration.ofMinutes(1L)))
                .asConstraint("Student group time efficiency");
    }

[MichelFonseca1024]

Thanks for the reply!

I’ve tried both solutions:

1 - Rewarding consecutive lessons (like in teacherTimeEfficiency)

2 - Penalizing gaps using toConnectedTemporalRanges

But neither worked well for my case. I still get timetables with gaps between lessons for the same student group.

Is there a way to check the full timetable and detect when there are holes between lessons for a group during the day?

Thanks!

[Christopher-Chianelli]

It is possible that there is no feasible solutions that avoid gaps. You can make the penalty HardSoftScore.ONE_HARD instead of HardSoftScore.ONE_SOFT if you want no gaps to be a hard constraint. To verify the constraint is working as expected, you can create a ConstraintVerifier test that checks the "consecutive" case and the "gap" case. You can use SolutionManager to get a ScoreAnalysis of a solution, then find the constraint in constraintMap.