Planning is a tricky subject. Whole study courses are setup to learn how to plan production and transport. The tricky thing is that planning is about what should or could happen in the future, so it includes uncertainty by definition.

The code used in this presentation

We want to plan transports.
For our logistics plan we have to recon with four things:

Availability of the product to be transported and the latest time it should be delivered.
This provides a time window: Not before, no later as.
Next we have the resources needed to do the transport.
The trailer to hold the product. It may already be planned (in use in some future).
The truck to pull the trailer. It also may already be planned.
The driver to drive the combination. He or she may already be planned.

The last three in the list above can be seen as resources with limited availability, the first in the list gives the boundary of a valid transport plan.

1. Avoid double plans

In the simplest model, which applies to our case, a resource can be used only once during any period of time. This is relatively easily checked.

For one resource, say the driver, this is what it looks like.

Figure 1. Legal and illegal resource plans.

In postgresql, ranges are not restricted to time lines, they can also be applied to integers and floating point numbers.

Because it is important to avoid overlaps, we want to protect conflicts with the already planned transports. We are using a database and if it is any good, that should help us protect the planned transports, by means o constraints.

Computing conflicts is a bit involved. Say we have a plan with start point a, endpoint b and a candidate plan with start point c and end point d. To compute a conflict, you need to compute the following:

\( \text{conflict} = ( c <= a \land a < d) \lor (c <= b \land b < d) \\ \lor \\ (a <= c \land c < b \land a <=d \land d <= b) \)

In text: There is overlap if

  • either end point a or b is between c and d.

  • or end point c or d is between a and b.

Conflicts are the things we want to avoid.

With a easily installed extension this can be expressed in PostgreSQL quite easily.

Create extension btree_gist that enables overlap test

In the following we use time stamp ranges (tsrange). It specifies the planned time on a time line, on which a plan is demarcated by a begin timestamp and end timestamp. The range is half open meaning that the start is included, but the end is not.

Truck plan table with timestamp ranges (tsrange) and avoid overlap constraint
CREATE TABLE truckplans(
       truckid INTEGER REFERENCES trucks,
       plan TSRANGE,
       EXCLUDE USING GIST ( truckid WITH =, plan WITH &&) (1)
1 The exclude constraint specifies that the same truck (by truckid) can’t have overlapping plans,
specified by the && operator which is defined on ranges.

This first approach is the most natural, be cause the human in the equation (the driver) has some special constraints the constraints can become quite involved, even for a simple worker.

  • A worker has rights to have the weekends off

  • works no more that 8 hours per day

  • takes vacations

  • or planned absence, e.g. to visit a doctor or take a course

  • and can be unavailable without prior plan, like calling in ill.

The last two bullets, with a grain of salt also applies to trucks and trailers and other resources that

  • need maintenance, which can be planned

  • can break, or are involved in accidents, which is unplanned.

Dealing with the uncertainties in the above is both easy and expensive. Because risks also happen in the future, the only way to deal with them is not to plan them, because you can’t, but instead keep some resource of a type in reserve as a kind of buffer.

From the above you can infer that trying to exact is complex, even though the database can ensure that no overlap occurs. The complexity lies in finding the gaps between plans.

2. Finding the gaps between plans

Figure 2. planning a duration

The (un)availability of the required resources and a required duration of the plan will yield a plan using resource 1a, 2a, and 3b at the time shown in the diagram above.

In the following a plan is a reserved period (java) or interval (postgres) on the time line for a reservation.

  1. Compute the gaps between plans.

  2. Keep track of the gaps.

Option 1 can be computationally intensive, option 2 is certainly space intensive, since each gap takes a record in a timeline table, such the truckplans above.

Window functions are an interesting feature in modern SQL, worth studying.

PostgreSQL support so called window functions in queries. They make it relatively easy to relate a plan to its predecessor(s) or successor(s). This helps computing the gaps.

Truckplans and gaps following them.
  conf as (select current_date+ '7 days'::interval as plans_end_date), (1)
  gaps as (
       select truckplanid, truckid, plan,
              tsrange( upper( plan ),
                       coalesce( lower(
                                     lead( plan, 1 ) over win         (2)
                                 ),	 plans_end_date                   (3)
              ) gap
       from conf,truckplans
       where upper(plan) <=  plans_end_date
       window win as (partition by truckid order by plan)             (4)
  select truckid,plan,gap from gaps order by truckid,gap;             (5)
1 plans_end_date is a parameter to this query
2 find the gap between the plan in the current row and the row it leads by one, which is the successor row
It takes the upper of this tsrange and the lower of the next. The gap is of course a also a tsrange. Note the use of over win, which refers to the window declared further down.
3 We want to keep both start and end dates of the gaps for later use. Here the same window win is reused.
4 Here we declare the window name win that is used in the lead(plan, 1) over win expression, in which the lead(…​) is a window function defined over a window. Lead means that the current row leads and the number in the lead method call is the number after that lead.
5 Using the result from the gaps expression.
Resulting gaps in truckplans.
│ truckid │                     plan                      │                      gap                      │
│       1 │ ["2020-03-30 07:00:00","2020-03-30 11:00:00") │ ["2020-03-30 11:00:00","2020-03-30 12:00:00") │
│       1 │ ["2020-03-30 12:00:00","2020-03-30 16:00:00") │ ["2020-03-30 16:00:00","2020-03-31 09:00:00") │
│       1 │ ["2020-03-31 09:00:00","2020-03-31 16:00:00") │ ["2020-03-31 16:00:00","2020-04-06 00:00:00") │
│       2 │ ["2020-03-30 09:00:00","2020-03-30 11:30:00") │ ["2020-03-30 11:30:00","2020-03-30 15:00:00") │
│       2 │ ["2020-03-30 15:00:00","2020-03-30 16:30:00") │ ["2020-03-30 16:30:00","2020-03-31 08:00:00") │
│       2 │ ["2020-03-31 08:00:00","2020-03-31 12:30:00") │ ["2020-03-31 12:30:00","2020-03-31 15:00:00") │
│       2 │ ["2020-03-31 15:00:00","2020-03-31 16:30:00") │ ["2020-03-31 16:30:00","2020-04-06 00:00:00") │
│       3 │ ["2020-03-30 15:00:00","2020-03-30 16:30:00") │ ["2020-03-30 16:30:00","2020-04-01 15:00:00") │
│       3 │ ["2020-04-01 15:00:00","2020-04-01 17:00:00") │ ["2020-04-01 17:00:00","2020-04-06 00:00:00") │
(9 rows)

Time: 4,888 ms

A Window specification partitions the relation data. The window functions can then process some or all elements of a partition. For example
SELECT depname, empno, salary, avg(salary) OVER (PARTITION BY depname) FROM empsalary
computes the average salary per department. See the postgresql documentation .