Here is my current constraints file for a Timefold timetabling problem.
class Constraints : ConstraintProvider {
override fun defineConstraints(factory: ConstraintFactory): Array<Constraint> {
return arrayOf(
roomClash(factory),
preferPriorityRooms(factory),
sequenceViolation(factory),
avoidEvening(factory),
sessionConflict(factory),
moduleProximity(factory),
roomUnderused(factory),
threadOverloaded(factory),
clearStaffDay(factory),
staffDaysFairness(factory),
threadDaysFairness(factory),
threadProximity(factory),
unnecessaryRoomChange(factory),
threadUnderloaded(factory),
instantRoadCrossing(factory)
)
}
fun ConstraintFactory.forEachMappingPairUnifilter(unifilter: Predicate<Mapping>?,
vararg joiners: BiJoiner<Mapping, Mapping>) =
when (unifilter) {
null -> this.forEachUniquePair(Mapping::class.java, *joiners)
else -> this.forEach(Mapping::class.java).filter(unifilter)
.join(this.forEach(Mapping::class.java).filter(unifilter),
lessThan(Mapping::ID),
*joiners)
}
fun ConstraintFactory.forEachOverlappingMapping(unifilter: Predicate<Mapping>?,
vararg joiners: BiJoiner<Mapping, Mapping>) =
this.forEachMappingPairUnifilter(unifilter,
equal(Mapping::semester),
overlapping(Mapping::start, Mapping::end),
*joiners,
filtering { a, b -> a.session.sharesWeekWith(b.session) })
fun ConstraintFactory.forEachModulePair(unifilter: Predicate<Mapping>?,
vararg joiners: BiJoiner<Mapping, Mapping>) =
this.forEachMappingPairUnifilter(unifilter,
equal(Mapping::semester),
equal(Mapping::module),
*joiners,
filtering { a, b -> a.session.sharesWeekWith(b.session) })
fun ConstraintFactory.forEachDirectlyFollowingModulePair(unifilter: Predicate<Mapping>?,
vararg joiners: BiJoiner<Mapping, Mapping>) =
forEachModulePair(unifilter,
equal(Mapping::end, Mapping::start),
*joiners
)
private fun roomClash(factory: ConstraintFactory): Constraint {
return factory.forEachOverlappingMapping(null,
equal(Mapping::room))
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Room Clash")
}
private fun preferPriorityRooms(factory: ConstraintFactory): Constraint {
return factory.forEach(Mapping::class.java)
.filter { !it.room.priority
&& it.session.students <= 108
&& it.session.viableRooms.size > 1 }
.penalize(HardMediumSoftScore.ONE_SOFT) { m -> m.session.students }
.asConstraint("Prefer Priority Rooms")
}
private fun sequenceViolation(factory: ConstraintFactory): Constraint {
return factory.forEachModulePair( { it.sequence() > 0 },
greaterThanOrEqual(Mapping::slotOrdinal),
lessThan(Mapping::sequence))
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Sequence Violation")
}
private fun avoidEvening(factory: ConstraintFactory): Constraint {
return factory.forEach(Mapping::class.java)
.filter { it.slot.hour + it.session.length > 17 }
.penalize(HardMediumSoftScore.ofSoft(2)) { m -> m.session.students * 2 }
.asConstraint("Avoid Evening Slots")
}
private fun sessionConflict(factory: ConstraintFactory): Constraint {
return factory.forEachOverlappingMapping(null)
.ifExists(
SessionConflict::class.java,
filtering { a, b, c -> c.contains(a.session) && c.contains(b.session) })
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Session Conflict")
}
private fun moduleProximity(factory: ConstraintFactory): Constraint =
factory.forEachModulePair({it.sequence() > 0},
equal(Mapping::sequence, {it.sequence() - 1}))
.penalize(HardMediumSoftScore.ONE_MEDIUM)
{ a, b -> a.effectiveProximity(b) * min(a.session.students, b.session.students) }
.asConstraint("Module Session Proximity")
private fun threadProximity(factory: ConstraintFactory): Constraint {
return factory.forEach(SetThread::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) })
.join(Mapping::class.java, Joiners.filtering { a, b, c -> a.takesMapping(c) && c.ID > b.ID })
.penalize(HardMediumSoftScore.ONE_MEDIUM) { a, b, c -> b.effectiveProximity(c) * a.size }
.asConstraint("Thread Proximity")
}
private fun roomUnderused(factory: ConstraintFactory): Constraint =
factory.forEach(Mapping::class.java)
.filter { it.room.priority == false
&& it.session.module.code != "ENGR4003"
&& it.room.capacity > it.session.students
&& it.session.viableRooms.size > 1
&& it.room.capacity != 9999 } // Specialist rooms
.penalize(HardMediumSoftScore.ONE_SOFT) { it.room.capacity - it.session.students }
.asConstraint("Room Underused")
private fun unnecessaryRoomChange(factory: ConstraintFactory): Constraint =
factory.forEachDirectlyFollowingModulePair({it.session.module.code != "ENGR4003"},
equal(Mapping::type),
filtering{a, b ->
(b.session.allStaff.containsAll(a.session.allStaff) && a.session.allStaff.containsAll(b.session.allStaff)) &&
(a.room != b.room) &&
(a.room.priority || !b.room.priority)}
).penalize(HardMediumSoftScore.ofMedium(100)) { a, b -> min(a.session.students, b.session.students) }
.asConstraint("Unnecessary Room Change")
private fun threadOverloaded(factory: ConstraintFactory): Constraint =
factory.forEach(SetThread::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) && b.session.module.code != "ENGR4003" } )
.groupBy( {a,b -> a}, {a, b -> b.slot.day + (10*b.session.semester) }, ConstraintCollectors.sum { a, b -> b.session.length })
.filter { cohort, day, length -> length >= 8 }
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Thread Overloaded")
private fun clearStaffDay(factory: ConstraintFactory): Constraint =
factory.forEach(Staffer::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> b.session.allStaff.contains(a)} )
.groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
.filter { staffer, semester, days -> days == 5 }
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Clear Staff Day")
private fun staffDaysFairness(factory: ConstraintFactory): Constraint =
factory.forEach(Staffer::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> b.session.allStaff.contains(a)} )
.groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
.penalize(HardMediumSoftScore.ONE_SOFT) { staffer, semester, days -> days * days }
.asConstraint("Staff Attendance Days Fairness")
private fun threadDaysFairness(factory: ConstraintFactory): Constraint =
factory.forEach(SetThread::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) } )
.groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
.penalize(HardMediumSoftScore.ofSoft(5)) { cohort, semester, days -> days * days }
.asConstraint("Thread Attendance Days Fairness")
private fun threadUnderloaded(factory: ConstraintFactory): Constraint =
factory.forEach(SetThread::class.java)
.join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) } )
.groupBy( {a, b -> a}, {a, b -> b.slot.day + (10*b.session.semester) }, ConstraintCollectors.sum { a, b -> b.session.length })
.filter { cohort, day, length -> (length == 1) }
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Thread Underloaded")
private fun instantRoadCrossing(factory: ConstraintFactory): Constraint =
factory.forEachDirectlyFollowingModulePair( { it.session.module.code != "ENGR4003" },
filtering { a,b -> a.room.areaID != b.room.areaID })
.penalize(HardMediumSoftScore.ONE_SOFT) { a, b -> min(a.session.students, b.session.students) }
.asConstraint("Instant Road Crossing")
}
This gives a evaluation speed of around 255/sec which is really slow according to the documentation. Are there any things I can do further to optimize this? I think that threadProximity
has a lot to answer for, but I'm not sure how to deal with that, since there doesn't seem to be a version of groupBy
which can put an entity into multiple groups (takesMapping()
is many-to-many).
发布者:admin,转转请注明出处:http://www.yc00.com/questions/1744742424a4591107.html
评论列表(0条)