javaspring-bootconstraintsoptaplannertimefold

How to get consecutive pairs (based on their Timeslot) of Lessons in Timefold?


Based on GitHub project provided by Timefold (https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/technology/java-spring-boot) I want to implement a constraint for the following scenario that can occur in the university:

Let's say that for a specific Day (Monday), we have 7 Timeslots (8AM - 10AM, 10AM - 12AM, ..., 8PM-10PM) and 4 different Lessons to assign in that day. We want to ensure that there is not any gaps (bigger than 2 hours for example) in the schedule for the specific day.

My current attempt is the following:

Constraint tooMuchGap(ConstraintFactory constraintFactory){
        // 4 hours gaps between lessons for students in the same day
        //todo solve this problem-> we receive pairs that are not consecutives
        return constraintFactory
                //select each 2 pair of different lessons
                .forEach(Lesson.class)
                .join(Lesson.class,
                        //with the same student group
                        Joiners.equal(Lesson::getStudentGroup),
                        //in the same day
                        Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()),
                        Joiners.lessThan((lesson -> lesson.getTimeslot().getId())))
                .filter((lesson1, lesson2) -> {
                    
                    Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),
                            lesson2.getTimeslot().getStartTime());
                    return !between.isNegative() && between.compareTo(Duration.ofHours(3)) > 0;
                })
                .penalize(HardSoftScore.ONE_SOFT)
                //.justifyWith()
                .asConstraint("Too much gap between the courses");
    }

For this test case:

@Test
    void tooMuchGap(){
        StudentGroup studentGroup = new StudentGroup(1L,"Group1");
        Lesson firstTuesdayLesson = new Lesson(1, "subject1", new Teacher(1L, "Teacher2"), studentGroup, TIMESLOT2, ROOM1);
        Lesson secondTuesdayLesson = new Lesson(2, "subject2", new Teacher(2L, "Teacher1"), studentGroup, TIMESLOT3, ROOM1);
        Lesson thirdTuesdayLesson = new Lesson(3, "subject3", new Teacher(3L, "Teacher3"), studentGroup, TIMESLOT6, ROOM1);
        Lesson fourthTuesdayLesson = new Lesson(4, "subject4", new Teacher(4L, "Teacher3"), studentGroup, TIMESLOT7, ROOM1);
        constraintVerifier.verifyThat(TimetableConstraintProvider::tooMuchGap)
                .given(firstTuesdayLesson, secondTuesdayLesson, thirdTuesdayLesson, fourthTuesdayLesson)
                .penalizesBy(1);
    }

I receive the following output:

2024-03-13 22:45:12.697  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00)
2024-03-13 22:45:12.707  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=3, dayOfWeek=TUESDAY, startTime=14:30, endTime=16:30)
2024-03-13 22:45:12.707  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------
2024-03-13 22:45:12.707  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00)
2024-03-13 22:45:12.707  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=6, dayOfWeek=TUESDAY, startTime=19:00, endTime=21:00)
2024-03-13 22:45:12.707  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=3, dayOfWeek=TUESDAY, startTime=14:30, endTime=16:30)
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=6, dayOfWeek=TUESDAY, startTime=19:00, endTime=21:00)
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00)
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=7, dayOfWeek=TUESDAY, startTime=21:00, endTime=23:00)
2024-03-13 22:45:12.709  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=3, dayOfWeek=TUESDAY, startTime=14:30, endTime=16:30)
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=7, dayOfWeek=TUESDAY, startTime=21:00, endTime=23:00)
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson1's timeslot: Timeslot(id=6, dayOfWeek=TUESDAY, startTime=19:00, endTime=21:00)
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - The lesson2's timeslot: Timeslot(id=7, dayOfWeek=TUESDAY, startTime=21:00, endTime=23:00)
2024-03-13 22:45:12.710  INFO [main           ] - c.t.t.s.TimetableConstraintProvider - ----------------------------------

java.lang.AssertionError: Broken expectation.
        Constraint: com.timetablealgo.testingtimetablealgo.solver/Too much gap between the courses
  Expected penalty: 1 (class java.lang.Integer)
    Actual penalty: 3 (class java.lang.Integer)

  Explanation of score (0hard/-3soft):
    Constraint matches:
        -3soft: constraint (Too much gap between the courses) has 3 matches:
            -1soft: justified with ([Lesson(id=2, subject=subject2, teacher=Teacher(id=2, name=Teacher2, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null)), Lesson(id=5, subject=subject3, teacher=Teacher(id=3, name=Teacher3, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=6, dayOfWeek=TUESDAY, startTime=19:00, endTime=21:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))])
            -1soft: justified with ([Lesson(id=2, subject=subject2, teacher=Teacher(id=2, name=Teacher2, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null)), Lesson(id=6, subject=subject4, teacher=Teacher(id=3, name=Teacher3, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=7, dayOfWeek=TUESDAY, startTime=21:00, endTime=23:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))])
            ...
    Indictments:
        -2soft: indicted with (Lesson(id=2, subject=subject2, teacher=Teacher(id=2, name=Teacher2, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=2, dayOfWeek=TUESDAY, startTime=12:00, endTime=14:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))) has 2 matches:
            -1soft: constraint (Too much gap between the courses)
            -1soft: constraint (Too much gap between the courses)
        -2soft: indicted with (Lesson(id=6, subject=subject4, teacher=Teacher(id=3, name=Teacher3, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=7, dayOfWeek=TUESDAY, startTime=21:00, endTime=23:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))) has 2 matches:
            -1soft: constraint (Too much gap between the courses)
            -1soft: constraint (Too much gap between the courses)
        -1soft: indicted with (Lesson(id=5, subject=subject3, teacher=Teacher(id=3, name=Teacher3, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=6, dayOfWeek=TUESDAY, startTime=19:00, endTime=21:00), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))) has 1 matches:
            -1soft: constraint (Too much gap between the courses)
        -1soft: indicted with (Lesson(id=3, subject=subject1, teacher=Teacher(id=1, name=Teacher1, preferredTimeslot=null), studentGroup=StudentGroup(id=1, year=null, name=Group1, group=null, semiGroup=null, numberOfStudents=30), type=null, year=null, timeslot=Timeslot(id=3, dayOfWeek=TUESDAY, startTime=14:30, endTime=16:30), room=Room(id=1, name=Room1, capacity=0, type=null, building=null, dotari=null))) has 1 matches:
            -1soft: constraint (Too much gap between the courses)

My question is how get consecutive pairs (based on their Timeslots) for the evaluation? For this case, I want to get the following pairs only: (Timeslot2 and Timeslot3), (Timeslot3 and Timeslot6), (Timeslot6 and Timeslot7).


Solution

  • Since the definition of consecutive is "two timeslots assigned to the same student group on the same day without another timeslot in between them", I would use an ifNotExists:

    Constraint tooMuchGap(ConstraintFactory constraintFactory){
            // 4 hours gaps between lessons for students in the same day
            return constraintFactory
                    //select each 2 pair of different lessons
                    .forEach(Lesson.class)
                    .join(Lesson.class,
                            //with the same student group
                            Joiners.equal(Lesson::getStudentGroup),
                            //in the same day
                            Joiners.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()),
                            // First starts before second
                            Joiners.lessThan((lesson) -> lesson.getTimeslot().getStartTime())
                    )
                    .ifNotExists(Lesson.class,
                            //with the same student group
                            Joiners.equal((a,b) -> a.getStudentGroup(), Lesson::getStudentGroup),
                            //in the same day
                            Joiners.equal((a,b) -> a.getTimeslot().getDayOfWeek(), (lesson) -> lesson.getTimeslot().getDayOfWeek()),
                            //is between the two timeslots
                            Joiners.lessThan((a,b) -> a.getTimeslot().getStartTime(), (lesson) -> lesson.getTimeslot().getStartTime()),
                            Joiners.greaterThan((a,b) -> b.getTimeslot().getStartTime(), (lesson) -> lesson.getTimeslot().getStartTime())
                    )
                    .filter((lesson1, lesson2) -> {
                        
                        Duration between = Duration.between(lesson1.getTimeslot().getEndTime(),
                                lesson2.getTimeslot().getStartTime());
                        return !between.isNegative() && between.compareTo(Duration.ofHours(3)) > 0;
                    })
                    .penalize(HardSoftScore.ONE_SOFT)
                    //.justifyWith()
                    .asConstraint("Too much gap between the courses");
        }