Making time: Galactus DB 1.7.1

Most organisations have a scheduling problem somewhere. Care visits have to fit around staff hours and the drive between clients. An operation needs a surgeon, an anaesthetist and a theatre at the same time. Exams need rooms with enough seats, and a paint line loses an hour every time it changes colour. The answer usually lives in a spreadsheet, or in a separate optimiser that the data has to be exported to.

Galactus DB 1.7.0 added a scheduler to the database. 1.7.1 lets you see its plans as a chart and build the call from a form, in Explorer and in Station. We didn't write a post for 1.7.0, so this one covers both releases.

Why schedule in a graph

The hard part of most schedules is the relationships between things, and those are what a graph stores.

Take who can do what. A nurse can take a visit if they hold every qualification it needs, and an engineer can take a job if they are trained on that model of boiler. Qualifications and training are relationships, so the check is a pattern match.

Clashes work the same way. Two exams can't run at the same time if any student sits both. Two fixtures clash if they share a team, and two talks clash if they share a speaker. The scheduler works the clashes out from who is linked to what, so nobody has to list them.

History matters too. A client who has seen the same carer for a year should keep seeing them, and the past visits are already in the graph for the scheduler to prefer. Order is often stored as well: prep before surgery, heats before finals, the delivery before the fitting. One MATCH turns those relationships into rules. Clients, sites and depots are nodes with locations, so travel time is part of the plan from the start.

A separate scheduling tool needs all of this exported into its own format, and the export has to be repeated whenever someone gains a skill or changes a booking. A scheduler inside the database reads the current graph every time it runs.

1.7.0: the Native Scheduler

gdb.schedule.solve takes the tasks and resources you match and reads everything else through Cypher expressions over your own labels and properties. There's no scheduling schema to adopt. Here is a morning of home care visits. Some visits need two people, regular clients get staff who have visited them before, and nobody works more than three hours without a 30-minute break:

MATCH (v:Visit) WHERE v.duration IS NOT NULL WITH collect(v) AS visits
MATCH (s:Staff) WITH visits, collect(s) AS staff
CALL gdb.schedule.solve({
  tasks: visits, resources: staff, randomSeed: 1,
  task: {required: 'coalesce(t.people, 1)'},
  pair: {affinity: 'size([(r)-[:VISITED]->(:Visit)-[:FOR]->(c)<-[:FOR]-(t) | 1])'},
  constraints: [{type: 'maxContinuous', amount: 180, breakLength: 30}]
})
YIELD task, resources, start, end
UNWIND resources AS person
CREATE (person)-[:BOOKED {start: start, end: end}]->(task)
RETURN task.name, person.name, start ORDER BY start;

Each placement comes back as a row with the task, the people it uses and its start and end. Here the plan goes straight back into the graph as BOOKED relationships, where you can query it like any other data. The home care recipe has the data to try it with.

The same call covers very different problems:

People fixed by the data, such as the students sitting an exam or the players in a match, can't be in two places at once and can need a gap between tasks. See resources, participants and places.
A task can need several resources at once, and a room can hold several tasks up to its capacity. See needs and eligibility.
Travel time comes from locations or a table, and setup time from the kind of task that went before. See changeover, travel and setups.
Rules can be hard or soft: most hours, guaranteed hours, breaks, one task before another, or the same person for a whole care plan.
Lateness and other costs can follow a penalty curve, so ten minutes late costs a little and an hour late costs a lot.
When someone calls in sick, you pass in today's bookings and only the tasks that have to move are changed. See re-planning.

On Galactus DB 1.7.0 (Intel Core i9-13900K, 64 GB RAM), a day of 2,000 tasks on 100 resources solves in about 2.5 seconds, with travel, 80 tasks that need two people and a break rule. Search and performance covers the time budget and how to get repeatable plans.

The scheduling recipes are eleven complete examples you can paste into an empty database, among them a hospital theatre list, an exam timetable, sports fixtures, a factory floor and re-planning after a change. The Native Scheduler demo runs six of them in your browser so you can watch the search improve the plan. The scheduling guide has every option.

1.7.0 also added vector.normalize, which scales a list such as a FastRP embedding to unit length, and vector.norm.euclidean, which measures it. See vector norm and normalisation, or the graph embeddings demo for FastRP at work.

1.7.1: see the plan, then build the call

A list of rows is hard to check by eye. In 1.7.1, when you run gdb.schedule.solve.stats in Explorer, the result opens as a Gantt chart. This one is an afternoon of a dance competition, with three stages and dancers who need 15 minutes between dances:

A dance afternoon planned by gdb.schedule.solve

Each stage, carer, theatre or machine gets a lane. Time outside its working hours is shaded, and the share of its time that is booked sits next to its name. You can switch the lanes to participants to see each person's day. Clicking a task highlights every lane it uses, and tasks that couldn't be placed are listed with the reason, such as RuleLimit:maxTasks. The chart also works for any query that returns a start and an end per row, so bookings you wrote back last week chart the same way. The Schedule view guide lists the controls.

The ▤ Schedule button in Explorer opens a builder. You pick the task and resource labels, durations, availability, who can take what, rules and the order of priorities, and the Cypher is written as you go. Labels, relationship types and property names are suggested from your database. You can insert the call into the editor and change it by hand, or run it straight away. See the schedule builder guide.

1.7.1 also gives a clearer error when an expression uses the wrong name. Scheduler expressions refer to the task as t and the resource as r. In 1.7.0, task.minutes quietly evaluated to null and the error was about a missing duration. 1.7.1 names the mistake:

expression `task.minutes` uses `task`, which is not defined here; it can use `t`

In Galactus DB Station

Galactus DB Station 0.3.1 has the same Schedule view and builder, and its built-in database runs 1.7.1, so you can try the scheduler on a laptop with nothing else installed. Station's builder writes the same Cypher as Explorer's, and a test keeps them in step. The Station guide covers the result views.

Upgrading

Pull and restart:

docker pull ianknowles/galactus-db:1.7.1
docker pull ianknowles/galactus-db-explorer:1.7.1

The data, commit log, snapshot and dump formats haven't changed since 1.6.1, so 1.6 and 1.7 releases open each other's databases and there's nothing to migrate.

What's next

Next, the scheduler will take travel times from the road network already stored in your graph, so a visit across the river costs the drive over the bridge rather than the straight-line distance.

← All posts Contact us