Geoffrey De Smet
by Geoffrey De Smet
Optimized for KPIs
Less than 5%
CPLEX 1.0 in 1988
Expected: -1% driving time
Result: -25% driving time
⇒ -10 million kg CO² emission per year
⇒ -100 million $ cost per year
Timefold mission
Open source
javafor (int i = 0; i < numEmployees; i++) {
for (int j = 0; j < numShifts; j++) {
for (int k = j + 1; k < numShifts; k++) {
model.addConstraint(
LinearExpr.sum(new IntVar[]{s[i][j], d[j], r[i]})
.leq(s[i][k])
).onlyEnforceIf(new IntVar[]{x[i][j], x[i][k]});
}
}
}
javaf.forEach(Shift.class)
.join(Shift.class, equal(Shift::employee),
lessThanOrEqual(Shift::end, Shift::start))
.filter((shift1, shift2) ->
Duration.between(shift1.end, shift2.start)
.compareTo(shift1.employee.restDuration) < 0)
.penalize(ONE_HARD)
.asConstraint("Enough rest between shifts");
A scaling problem
javafor (int i = 0; i < numEmployees; i++) { // 10k loop
for (int j = 0; j < numShifts; j++) { // 50k loop
for (int k = j + 1; k < numShifts; k++) { // 25k loop
model.addConstraint(...).onlyEnforceIf(...);
}
}
}
2 500 000 000 000 CPU loops
2 500 000 000 000 constraints in memory
Out of memory error
javaf.forEach(Shift.class)
.join(Shift.class, equal(Shift::employee)) // ~250k tuples
.filter() // 0-10 tuples
.penalize(ONE_HARD)
.asConstraint("Enough rest between shifts");
1 constraint
Only 250k tuples in memory
Lazy, incremental and indexed
Check the Timefold log:
log08:27:00.867 INFO Solving started: ...
08:27:02.528 INFO Construction Heuristic ended: ...
move evaluation speed (39580/sec) ...
08:27:21.313 INFO Local Search ended: ...
move evaluation speed (101701/sec) ...
08:27:21.317 INFO Solving ended: ...
move evaluation speed (101461/sec) ...
It looks at 100 000 solutions per second
Why not plain java code?
javavar ann = new Employee("Ann", ...);
verifier.verifyThat(employeeMinimalRest)
.given(ann,
new Shift(mon1400, mon2200, ann),
new Shift(tue0600, tue1400, ann))
.penalizes());
Isolated per constraint
docs.timefold.ai
REST API
app.timefold.ai
Much more than
VRP with Time Windows
One example...
REST API
REST API
REST API
We call it ...
Join the PlanningAI revolution
Contact us for assistance,
questions or self-hosting.
Learn more | timefold.ai |
---|---|
Documentation | docs.timefold.ai |
Quickstarts | github.com/TimefoldAI/timefold-quickstarts |
REST APIs | app.timefold.ai |
Feedback |
|