Hi,
I am taking a 2nd attempt at Opta to solve astronomical observation scheduling after focussing more into the Choco constraint solver. I would very much appreciate your comments whether the approach taken is ok, and scalable. So far, Choco seems to be much much faster and I wonder if I am modelling my problem poorly in Opta. I see the advantage of Opta in simpler expression of constraints. Benchmarking seems to indicate that I should be using FIRST_FIT / TABU_SEARCH. I only have 5 constraints.
Any comment what could be improved is greatly appreciated. Thanks a lot !
Problem
- ~ 3000 Observations (OBs) are scheduled to time slots in nights by assigning the start slot
- There is a total of 180 nights
- each night has 20 time slots of 30min
- OBs have variable duration and may need one ore several time slots
- OBs belong to observing runs. If they are "visitor mode", i.e somebody travels to the mountain, additional constraints apply.
- the time slots in the below domain model are precomputed and assigned to the solution
Domain Model (snippet in Groovy)
@PlanningEntity
public class OB {
@PlanningVariable(nullable = false, valueRangeProviderRefs = "timeslotRange")
Timeslot start
@PlanningId
int obId
int runId // OB belongs to an observing run
boolean[] observable // whether the OB is observable in time slot n
int reqNoOfSlots // the required number of slots for this observation
EObservingMode observingMode
int getStartSlot() {
start.slot
}
int getEndSlot() {
start.slot + reqNoOfSlots - 1
}
int getNight() {
startSlot.intdiv(SLOTS_PER_NIGHT)
}
// compute a chunk ID that is unique per run per night
int getChunkID() {
1000 * runId + getNight()
}
boolean isVisitor() {
observingMode == EObservingMode.Visitor
}
}
class Timeslot {
@PlanningId
int slot
Date start
Date end
...
}
@PlanningSolution
class Schedule {
@ValueRangeProvider(id = "timeslotRange")
@ProblemFactCollectionProperty
List<Timeslot> timeslots
@PlanningEntityCollectionProperty
List<OB> observations
@PlanningScore
HardSoftScore score
}
Constraints
// OBs must not overlap
Constraint noOverlap(ConstraintFactory factory) {
factory.fromUniquePair(OB.class,
overlapping(ob -> ob.startSlot, ob -> ob.endSlot + 1))
.penalize("overlap", HardSoftScore.ONE_HARD)
}
// OBs must be observable
Constraint observable(ConstraintFactory factory) {
factory.from(OB.class)
.filter(ob -> !ob.observable[ob.startSlot])
.penalize("not observable", HardSoftScore.ONE_HARD)
}
// in any given night, visitor mode OBs of the same run must be consecutive with no gaps
Constraint consecutiveVMChunks(ConstraintFactory factory) {
factory.from(OB.class).filter(ob -> ob.visitor)
.groupBy(OB::getChunkID,
min(OB::getStartSlot as Function),
max(OB::getEndSlot as Function),
sum(OB::getReqNoOfSlots as ToIntFunction))
.filter((chunk, minStart, maxEnd, noOfSlots) -> maxEnd + 1 - minStart > noOfSlots)
.penalize("non-consecutive VM chunk", HardSoftScore.ONE_HARD)
}
// in any given night, OBs of not more than 2 different visitor mode runs my be scheduled
Constraint onlyTwoVMChunksPerNight(factory) {
factory.from(OB.class).filter(ob -> ob.visitor)
.groupBy(OB::getNight, countDistinct(OB::getRunId as Function))
.filter({ night, noOfRuns -> noOfRuns > 2 })
.penalize("only 2 VM runs per night", HardSoftScore.ONE_HARD)
}
// total duration of a visitor mode run must not exceed 2 * required number of slots
Constraint maxVMRunLength(ConstraintFactory constraintFactory) {
constraintFactory.from(OB.class).filter(ob -> ob.visitor)
.groupBy(OB::getRunId,
min(OB::getStartSlot as Function),
max(OB::getEndSlot as Function))
.filter((runId, minStart, maxEnd) ->
maxEnd + 1 - minStart > 2 * TatooSolver.vmRunLengths[runId])
.penalize("VM run must be shorter", HardSoftScore.ONE_HARD)