Native Scheduler

Wiki / Graph data science

On this page

• Schedule in one call
• Timelines
• Tasks
• Resources, participants and places
• Needs and eligibility
• Changeover, travel and setups
• Rules
• Penalty curves
• Objective
• Re-planning
• Results
• Projection route
• Search and performance
• Configuration

The Native Scheduler places tasks in time and on the people, rooms or machines they need: carers on visits, dances on stages, operations in theatres, exams in halls, jobs on machines. It runs inside the database, reads its rules straight from the graph through Cypher expressions, and returns nodes you can write back with ordinary Cypher. See it work in the Native Scheduler demo, and find complete examples in the scheduling recipes.

Schedule in one call

MATCH (v:Visit) WITH collect(v) AS visits
MATCH (c:Carer) WITH visits, collect(c) AS carers
CALL gdb.schedule.solve({tasks: visits, resources: carers})
YIELD task, resource, start, end
CREATE (resource)-[:BOOKED {start: start, end: end}]->(task);

With no other options, a task reads duration and an optional target start, and a resource reads its working window from start and end. Everything else is optional and has a default. tasks and resources may be nodes or plain maps, so a schedule can also come from UNWIND of JSON:

CALL gdb.schedule.solve({
  tasks: [{name:'x', duration:30, target:60}, {name:'y', duration:30, target:60}],
  resources: [{name:'solo', windows:[[0, 240]]}]
}) YIELD task, resource, start RETURN task.name, resource.name, start;

Times can be numbers in any unit you choose, or datetime, localdatetime, date, time or localtime values; amounts can be numbers or duration values. Results come back in the same type. Numbers and temporal values can't be mixed in one schedule.

Timelines

Everything a task occupies is a timeline: something that can hold only so many tasks at once and may need time between them.

Every timeline has:

• windows: when it is available; with none it is always available;
• units: how many tasks it holds at once (default 1);
• changeover: the minimum gap between its consecutive tasks.

Tasks

Every task field is a Cypher expression over the task, bound as t. The defaults read same-named properties.

task: {duration: 't.minutes', target: 't.preferred',
       participants: '[(d:Dancer)-[:DANCES_IN]->(t) | d]'}

A value that isn't a string is a literal: participant: {changeover: 15}.

Resources, participants and places

Resource fields are expressions over r; participant and place fields over p.

Needs and eligibility

By default a task needs required resources from resources. List needs to ask for several kinds at once; each need is chosen separately, and one resource never fills two needs:

needs: [{count: 1, where: 'r:Surgeon'}, {count: 1, where: 'r:Anaesthetist'}, {count: 1, where: 'r:Theatre'}]

pair expressions see both t and r and are evaluated once per pair:

Graph patterns make them graph-driven, including hierarchies through paths:

pair: {
  eligible: 'all(s IN [(t)-[:REQUIRES]->(s) | s] WHERE EXISTS { (r)-[:HAS]->(:Skill)-[:IMPLIES*0..]->(s) })',
  affinity: 'size([(r)-[:VISITED]->(:Visit)-[:FOR]->(c)<-[:FOR]-(t) | 1])'
}

Changeover, travel and setups

The gap a timeline needs between two consecutive tasks is the largest of:

• its changeover (a costume change, cleaning a theatre, a rest day);
• travel between the two tasks, when the timeline travels: from travel entries [{from, to, time, distance}], else the distance between their location points at travelSpeedKmh (times then read as minutes);
• for resources, the setups table by task kind: setups: [{from:'latin', to:'ballroom', time:5}], with '*' matching any kind.

Each dancer needing 15 minutes between dances, and each stage needing 5 minutes to change between styles:

MATCH (d:Dance) WITH collect(d) AS dances
MATCH (s:Stage) WITH dances, collect(s) AS stages
CALL gdb.schedule.solve({
  tasks: dances, resources: stages,
  task: {duration: 't.minutes', kind: 't.style',
         participants: '[(p:Dancer)-[:DANCES_IN]->(t) | p]'},
  resource: {windows: '[(r)-[:HAS_SESSION]->(s) | {start: s.start, end: s.end}]'},
  participant: {changeover: 15},
  setups: [{from:'latin', to:'ballroom', time:5}, {from:'ballroom', to:'latin', time:5}],
  constraints: [{type:'maxTasks', count:3, per:'participant'}]
}) YIELD task, resource, start, end
RETURN task.name, resource.name, start, end ORDER BY start;

Rules

constraints is a list of rules. A rule without a penalty (or curve) is hard and never broken; with one it is soft and costs the penalty per unit of violation. Hard minimums can't always be met, so they are scored in the top violations tier instead.

Timeline rules apply to every resource by default; per: 'participant' or 'all' widens them, resources: [...] names timelines, and where filters with an expression over e. period applies a rule per day, shift or round (period: 1440 with minutes, or duration({days: 1})).

Tasks that must never overlap, such as exams sharing students, share a participant: give each student as a participant, or a single shared node.

Penalty curves

A curve turns a violation amount (minutes late, hours over, tasks short) into cost. Use one for drift with lateCurve and earlyCurve (globally or per task), or on any soft rule as curve. Rules apply the curve to each violation separately, so two people ten minutes late cost less than one person twenty minutes late when the curve is steep.

Every shape also takes after (a free allowance, e.g. the first 5 minutes) and cap (the most it can cost). Without a curve, drift costs weight × |drift| ^ driftExponent.

Objective

Plans are compared tier by tier in objective order. A later tier only decides while the earlier ones are within their tolerances, relative to max(|value|, 1).

Reorder the list to change what matters most, or leave tiers out: objective: ['unassigned', 'penalty', 'travel', 'drift'].

Re-planning

Give each task its current booking with baselineStart and baselineResources and the scheduler starts from it. The stability tier counts tasks that moved, so after a change (a carer calls in sick, a dance is withdrawn) only the tasks that have to move do. Lock bookings outright with fixedStart and fixedResources.

task: {baselineStart: '[(r)-[b:BOOKED]->(t) | b.start][0]',
       baselineResources: '[(r)-[:BOOKED]->(t) | r]'}

Results

gdb.schedule.solve returns one row per task:

Each timeline is a path, so writing NEXT relationships turns the plan into a graph you can query and run algorithms on:

... YIELD task, next WHERE next IS NOT NULL CREATE (task)-[:NEXT]->(next)

Unassigned reasons:

gdb.schedule.solve.stats returns counts, objective values, iterations, timings and schedule, a map Explorer can draw as a Gantt chart:

{_schedule: 1, dimensions: ['time', 'resource', 'participant'],
 timelines: [{key, label, kind, units, windows}],
 items: [{task, label, start, end, on: [timeline indexes]}],
 unassigned: [{task, label, reason}], objective: {...}}

label (default coalesce(x.name, x.title, x.id)) names items in it. Explorer's Schedule view draws it, and its schedule builder writes the gdb.schedule.solve call from forms. gdb.schedule.audit(config) lists structural problems without solving.

Projection route

The same engine runs over a projection with gdb.schedule.stream, .stats, .write, .mutate, .<mode>.estimate and .audit(graph, config). It reads the graph by convention, and every label, relationship type and property name is an option:

.write creates (resource)-[:<writeRelationshipType> {start, end}]->(task), and with nextRelationshipType links consecutive tasks on each resource. Stream columns are taskId, resourceId, start, end, drift, travelTime, unassignedReason. Projection-only options: maxDistance (metres between resource and task locations) and resourceMaxWork.

Search and performance

Hardest tasks are seeded first (priority, then fewest candidates, then most needs). Large neighbourhood search then repeatedly removes a group of tasks (at random, close in time, or everything on one timeline), re-inserts them and other waiting tasks at their cheapest feasible start, re-times their neighbours toward their targets, and accepts by simulated annealing. Every state satisfies the hard rules, and the final plan is re-checked from scratch. The same randomSeed always gives the same schedule.

Moves are undone from a journal rather than by copying the plan, timelines store only task ids, and expressions are evaluated once per task, resource or pair while the problem is built, never during the search.

On Galactus DB 1.7.0 (Intel Core i9-13900K, 64 GB RAM), a day of 2,000 tasks on 100 resources, with travel from points, 80 double-ups and a break rule, solves in about 2.5 s with the default four seed runs and 100 search iterations.

searchMillis stops the search after a time budget and returns the best plan; timeoutMillis cancels the call with an error.

Configuration

Reserved words work as map keys, so {where: 'r:Surgeon'} needs no quoting.

Related articles

Graph projections and catalogue · GDS algorithms and execution modes · GDS resources and cancellation · Graph data science