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).
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");
}