I've been trying to create a Drools file for timetabling, but OptaPlanner takes a long while to run even though the number of entities is quite small (less than 400).
The default Late Acceptance strategy reduces the hard constraint very quickly while leaving the soft constraint high, but hits a performance wall before reaching feasibility. Tabu Search reduces both scores but does so more slowly than Late Acceptance, and also hits the wall before feasibility, earlier than Late Acceptance does.
I wonder if some of the exponential or group evaluators are written wrongly or inefficiently? I've had some trouble with forall giving awkward syntax errors, claiming that ObjectTypes can't be matched.
import data.Module
import data.Session
import data.Slot
import data.Program
import data.Staffer
import data.SessionAlternativeGroup
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScoreHolder
import enums.SessionType
import java.util.Collections
import data.Constants
global HardSoftScoreHolder scoreHolder;
// Check for one tutor overused in the same slot
rule "staffClash"
when
$s1 : Session($tutors : tutors, $id : ID)
$tutor : Staffer() from $tutors
accumulate($s2 : Session($s2.overlaps($s1)); $tuse1 : sum($s2.getTutorWeeks($tutor)))
eval($tuse1 > 12)
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Room used for one module cannot be used for others at the same time
// (But it could be used for the same type of session on the same module)
rule "moduleRoomClash"
when
$s1 : Session($mod : module, $typ : type, $room : room, $id : ID)
$s2 : Session(module != $mod, type != $typ, room == $room, $s2.overlaps($s1))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Apply badness of time slots
rule "timeBadness"
when
Session($slots : allSlots, $count : students)
Slot ($bad : badness) from $slots
then
scoreHolder.addSoftConstraintMatch(kcontext,0-($bad * $count));
end
// Apply staff dislike of time slots
rule "staffDislikedTime"
when
$s : Session($staff : tutors, $slots : allSlots, $count : students)
$st : Staffer($slot : dislikeSlots) from $staff
eval($slots.contains($slot))
then
scoreHolder.addSoftConstraintMatch(kcontext,0-
(Constants.BADNESS_STAFFER_DISLIKES_SLOT) * $count * ($s.getTutorWeeks($st)));
end
// Non computer sessions can be in computer rooms, but it's better not to
rule "unnecessaryComputerRoom"
when
$s : Session(!needsComputer, room!.isComputer, $count : students)
then
scoreHolder.addSoftConstraintMatch(kcontext,0-
(Constants.BADNESS_UNNECESSARY_COMPUTER_ROOM) * $count);
end
// COMPULSORY, MANDATORY sessions must not clash with ANY other mandatory session on that
// program (if they did, it would be impossible to take that module)
rule "CompulsoryMandatoryClash"
when
Program( $comp : compulsories, $all : all )
$s1 : Session( module memberOf $comp, $ID : ID, mandatory == true )
Session( module memberOf $all, ID > $ID, mandatory == true, overlaps($s1) )
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// COMPULSORY, MANDATORY sessions must have at least ONE session in each altgroup on that
// programme that they do not clash with
rule "ProgrammeCompulsoryPracticalWipeout"
when
Program( $comp : compulsories, $all : all )
$s1 : Session(module memberOf $comp, $ID : ID, mandatory)
SessionAlternativeGroup(module memberOf $all, $sessions : sessions)
forall ($s2 : Session(overlaps($s1)) from $sessions)
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// It's bad for elective modules on a programme to clash.
rule "ProgrammeElectiveLectureClash"
when
Program( $el : electives )
$s1 : Session( module memberOf $el, $ID : ID, mandatory == true )
Session( module memberOf $el, ID > $ID, mandatory == true, overlaps($s1) )
then
scoreHolder.addSoftConstraintMatch(kcontext,0-Constants.BADNESS_ELECTIVE_CLASH);
end
// Lectures should be earlier in the week than practicals
rule "LecturesBeforePracticals"
when
Session ($module : module, isLecture, $lecslot : slot)
Session (module == $module, !isLecture, (slot!.ordinal) < ($lecslot!.ordinal))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Mandatory sessions shouldn't overlap any sessions on the same module
// (practicals CAN overlap each other, and normally would)
rule "PracticalOverLecture"
when
$s1 : Session ($mod : module, $ID : ID, mandatory)
$s2 : Session (module == $mod, ID > $ID, $s1.overlaps($s2))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Elective sessions of different types on the same module
// shouldn't completely overlap each other
rule "MultipleTypesOverlap"
when
$s1 : Session ($mod : module, $ID : ID, $type : type, !mandatory)
$ag : SessionAlternativeGroup($mod == module, type == $type, $s2s : sessions)
forall ($s2 : Session(overlaps($s1)) from $s2s);
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Sessions on a module should be as close as possible to each other
rule "PracticalsNearLectures"
when
$lec : Session (lastSlot != null, $mod : module, $ID : ID)
$prac : Session (slot != null, module == $mod, $count : students, ID > $ID)
then
scoreHolder.addSoftConstraintMatch(kcontext,
$count * (Math.min(0,0-($prac.getSlot().ordinal - ($lec.getLastSlot().ordinal+1)))));
end
// 12pm or 1pm slot should be free for staff for lunch
rule "NoLunchForYouStaffer"
when
Session($tutors : tutors, $day : slot.day, containsDayOrdinal(4))
$tutor : Staffer() from $tutors
Session(tutors contains $tutor, slot.day == $day, containsDayOrdinal(5))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// 12pm or 1pm slot should be free for students, for lunch
rule "NoLunchForYouStudent"
when
Program ($comp : compulsories)
Session($day : slot.day, $comp contains module, containsDayOrdinal(4))
Session(slot.day == $day, $comp contains module, containsDayOrdinal(5))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
// Number of days staff members are in should be fairly distributed
rule "StaffInDaysFairness"
when
$s : Staffer(isAL == false)
accumulate(Session(tutors contains $s, $day : slot!.day); $days1 : count($day))
then
scoreHolder.addSoftConstraintMatch(kcontext,(int)-(($days1 ^ 2)));
end
// Staff should have a clear day
rule "StaffClearDay"
when
$s : Staffer(isAL == false)
accumulate(Session(tutors contains $s, $day : slot!.day != 2); $days1 : count($day))
eval(($days1 > 3))
then
scoreHolder.addHardConstraintMatch(kcontext,-1);
end
INFO logging outputs the score calculation speed. The benchmarker (even better) even shows it in a graph. Higher is better.
Do a 40 second run, comment portions of the rules and watch that score calculation speed to find the bottleneck rules.