# 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:

```cypher
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](/docs/gds/scheduling-recipes#home-care-visits) 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](/docs/gds/scheduling#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](/docs/gds/scheduling#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](/docs/gds/scheduling#changeover-travel-and-setups).
- [Rules](/docs/gds/scheduling#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](/docs/gds/scheduling#penalty-curves),
  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](/docs/gds/scheduling#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](/docs/gds/scheduling#search-and-performance)
covers the time budget and how to get repeatable plans.

The [scheduling recipes](/docs/gds/scheduling-recipes) are eleven complete
examples you can paste into an empty database, among them a
[hospital theatre list](/docs/gds/scheduling-recipes#hospital-theatre-list), an
[exam timetable](/docs/gds/scheduling-recipes#exam-timetable),
[sports fixtures](/docs/gds/scheduling-recipes#sports-fixtures), a
[factory floor](/docs/gds/scheduling-recipes#factory-floor) and
[re-planning after a change](/docs/gds/scheduling-recipes#re-planning-after-a-change).
The [Native Scheduler demo](/demos/native-scheduler) runs six of them in your
browser so you can watch the search improve the plan. The
[scheduling guide](/docs/gds/scheduling) 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](/docs/gds/similarity-functions#vector-norm-and-normalisation),
or the [graph embeddings demo](/demos/graph-embeddings) 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](/blog/charts/release-171-schedule.svg)

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](/docs/integrations/explorer#schedule-view)
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](/docs/integrations/explorer#schedule-builder).

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:

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

## In Galactus DB Station

[Galactus DB Station](/product/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](/docs/station/queries#results) covers the result views.

## Upgrading

Pull and restart:

```text
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.