Interval sets

1. What is an interval

An interval is the set of all numbers lying between two fixed end points with no "gaps". Each end point is either a real number or positive or negative infinity, indicating the interval extends without a bound.

In mathematics, intervals can both include and exclude its end points. However, in the majority of real-world tasks, the intervals that include its end points are more useful. So, in Amalgama Platform, all intervals are closed, meaning they always include their end points. Some examples of intervals are shown on the figure below:

In scheduling and simulation models, intervals typically represent time periods, for example, time period when a resource, such as an employee or a machine, is available. For example, if a machine is available from 8 am till 8 pm, in Amalgama Platform this fact can be represented with an Interval class:

// A machine is available from 8 am till 8 pm
var machineAvailableInterval = Interval.of(8, 20);

// This will print 16
System.out.println("Duration of available interval: " + machineAvailableInterval.length());

// This will print 8
System.out.println("Min bound of the interval: " + machineAvailableInterval.min());

// This will print 20
System.out.println("Max bound of the interval: " + machineAvailableInterval.max());

It is quite natural to have some typical operations with intervals, such as union, intersection, and exclusion. Interval class API provides method for them. However the result of some of these operations is not necessarily in interval. For example, a result of union of the two intervals [1, 2] and [3, 4] is a set of these intervals, namely {[1, 2], [3, 4]}. This is where we need a notion of interval set.

2. What is an interval set and why it is useful

An interval set, as the name suggests, is a set of zero, one, or several intervals. To avoid ambiguity, in Amalgama Platform all interval sets have the following properties:

All intervals of an interval set are pairwise-disjoint, that is, no two intervals intersect with each other
The intervals of an interval set are always sorted in ascending order by their min bounds

Here is the simple example of using an interval set to represent a working day consisting of 2 4-hour shifts:

var morningShift = Interval.of(8, 12);

var afternoonShift = Interval.of(13, 17);

IntervalSet workingDay = morningShift.union(afternoonShift);

// This will print {[8.0, 12.0], [13.0, 17.0]}
System.out.println("Working day: " + workingDay);

// This will print 8
System.out.println("Min bound of the interval: " + workingDay.length());

3. First example: find a time slot for treatment in a hospital

Consider we need to model a hospital where patients are treated by doctors and nurses. Regardless of whether we are implementing logic of a scheduling or a simulation model, we will often need to find time gaps for treatments based on when our doctors and nurses are available.

Assume by the time of the planning, both doctor’s and nurse’s schedules have been partially filled with activities. So, their availability can then be represented by interval sets. Also, there is a lunch break, when no treatments can be done:

// A doctor is available 8-9, 10-11, and 12-16 (the number are hours of the day)
var doctorAvailability = IntervalSet.of(Interval.of(8, 9), Interval.of(10, 11), Interval.of(12, 16));

// A nurse is available 8-13 and 14-18
var nurseAvailability = IntervalSet.of(Interval.of(8, 13), Interval.of(14, 18));

// Lunch time is 12-13, no treatments can be done at during lunch time
var lunchtime = IntervalSet.of(12, 13);

To find the possible intervals for our treatment, we need:

first, intersect time intervals when both doctor and nurse are available
then, exclude lunch time:

// Intersect availability interval of both doctor and nurse
var bothAvailable = doctorAvailability.intersection(nurseAvailability);

// Exclude lunch time
var possibleTreatmentIntervals = bothAvailable.exclusion(lunchtime);

// This will print  {[8.0, 9.0], [10.0, 11.0], [14.0, 16.0]}
System.out.println("Possible treatment intervals are: " + possibleTreatmentIntervals);

So far, we have found set of time intervals (represented by an IntervalSet instance) when a treatment can be done. Let us now add some more details into our task by saying:

our treatment takes 1.5 hours
the treatment must be performed within a single solid time interval, without interruptions.

Finding such interval can be done with the following code:

// Intersect availability intervals of the doctor and the nurse, and exclude lunch time
var firstTreatmentInterval = doctorAvailability.intersection(nurseAvailability)
		.exclusion(lunchtime)
		// Retain only intervals longer than 1.5 hours
		.withIntervalsMatching(i -> i.length() >= 1.5)
		// Get the first (earliest) such interval 
		.firstInterval()
		// Throw exception if such interval is absent
		.orElseThrow();
// This will print [14.0, 16.0]
System.out.println("First possible 1.5h treatment interval is: " + firstTreatmentInterval);

4. Second example: find processing interval at a shop floor

Let us now look at another example. This time we are modeling a shop floor where we have 2 machines - machine A and machine B. Similar to the example with a hospital, we now need to schedule an activity, this time it is a task, which has to be done by our 2 machines simultaneously.

This time we know the intervals when our machines are busy. Every such interval might represent some previously scheduled task:

// Machine A is busy during the following time intervals
var machineABusyInvetrvals = IntervalSet.of(Interval.of(1, 3), Interval.of(8, 10), Interval.of(10, 12), Interval.of(18, 20));

// Machine B is busy during the following time intervals
var machineBBusyInvetrvals = IntervalSet.of(Interval.of(0, 4), Interval.of(4, 5), Interval.of(7, 11), Interval.of(14, 16));

Like in the previous example, to understand when both machines are available simultaneously we need to intersect their available interval sets. However, now we are given their busy intervals. So, we need to inverse these intervals to get available interval sets for our machines. Such operation is called complement in mathematics and can be done with the corresponding method:

// Intersect the complements of the two interval sets to get
// the time intervals when both machines are available (i.e., not busy)
var bothMachinesAvailableIntervals = machineABusyInvetrvals.complement().intersection(machineBBusyInvetrvals.complement());
// This will print {[-∞, 0.0], [5.0, 7.0], [12.0, 14.0], [16.0, 18.0], [20.0, +∞]}
System.out.println("Both machines available intervals: " + bothMachinesAvailableIntervals);

Now we know when both machines are available for our task. Note that checking the correctness of this answer is already not a trivial exercise, let alone writing a code that would calculate something like this.

Typically we want to do our scheduling in the future, meaning we do not want to plan our task to be done at negative time. To only consider positive time intervals, we can intersect our result with an interval of [0, +∞]. We also want to exclude potential one-point intersections that are represented with zero-length intervals:

// Intersect the complements of the two interval sets to get
// the time intervals when both machines are available (i.e., not busy)
var bothMachinesAvailableIntervals = machineABusyInvetrvals.complement()
		.intersection(machineBBusyInvetrvals.complement())
		// We are only interested in intervals in the future
		.intersection(Interval.of(0, Double.POSITIVE_INFINITY))
		// We are not interested in single moments when both machines are available
		.withoutZeroIntervals();

System.out.println("Both machines available non-zero intervals in the future: " + bothMachinesAvailableIntervals);

Now let us add some real life complexity and assume that our task takes 4.5 hours to complete and it can be done in several sessions. Additionally, we want to schedule this task as early as possible. To calculate, when exactly we can perform this task, we need to take the "leftest 4.5 hours" of our available interval set:

// We know that our task takes 4.5h and it can be split across several intervals
var intervalsForTask = bothMachinesAvailableIntervals.leftSubset(4.5);
// This will print {[5.0, 7.0], [12.0, 14.0], [16.0, 16.5]}
System.out.println("We can schedule a splittable 4.5h task for the following intervals " + intervalsForTask);

Now we have an interval set which tells us exactly where we can schedule our task without breaking any real-world constraints and, more importantly, without having to solve programming quizes.