SCHEDULING ALGORITHMS FOR CONCURRENT EVENTS

Haiku Laboratories Technical Memorandum 061001, October 2006

By Rick Martinelli and Neil Rhoads

This memo provides a rigorous foundation for the development of algorithms to optimally schedule concurrent events.  While the algorithms are general and can be used for any type of events, a typical application is the assignment of guest reservations to rooms in a large hotel.  In the case of a hotel or condominium property, optimal scheduling means achieving maximum occupancy by never rejecting a reservation due to inefficient scheduling.  In what follows, we find the minimum number of rooms required to accommodate a given set of reservations, and we describe an algorithm for automatically making assignments in situations where guests can be freely assigned to any room.  We then consider the more realistic situation where certain reservations must be assigned to particular rooms and we provide a second algorithm for handling this more difficult case.

For greatest applicability of the algorithms we will speak of events, keeping in mind that guest reservations are one specific type of event. We define an event e as a set of consecutive, non-negative integers ranging from p to q, with q ≥ p:

e = { p, p+1, …, q }.

We regard the elements of e as times (e.g., elapsed days, seconds, etc.) with p being the start time of event e and q being its end time. We assume p = 0 implies an event that begins “now” (today in our example).  Two events e1 and e2 overlap, or are said to be in-conflict, whenever their intersection is non-empty.  Conversely, a set of N events

S = e1e2, …, eN }

is conflict-free if its members are pair-wise disjoint.  We now have:

Definition: the scheduling problem is to find the smallest number of conflict-free subsets of the set of N events S = e1e2, …, eN }.

That is, find disjoint, conflict-free subsets of S, S1, S2,…, SM, such that their union is all of S,

S = S1 U S2 UU SM

and M, the number of subsets, has the smallest possible value.  This is called scheduling S, and the collection of sets Sk is called a partition of S.  To calculate M, let N > 0 and

S = { en | n=1,…, N }

be a set of events where

en = { pn, pn+1, …, qn }

for each n.  Letting

T = maxn (qn)

be the largest time value we create a matrix A with N rows and T+1 columns.  The events in S are mapped to the matrix A by placing a one in cell (n,t) if event n is occurring at time t, and zeros elsewhere. This may be written

A(n,t) = 1   if  pn  ≤  t  ≤ q n

= 0   otherwise

for each en in S.  Since A(n,t) is 1 if and only if event en is occurring at time t, and 0 otherwise, summing A(n,t) on events n for a fixed time t (adding the elements in column t) gives the number of events occurring at that time.

Definition: Mt is the number of events in S occurring at time t:

Mt = Mt(S) = ΣnA(n,t),

where the sum is over all events, and

Definition: M is the largest of the Mt taken over all t in [0, T] :

M = M(S) = Maxt { Mt(S) }.

For each t, these definitions imply

Mt(S) ≤ M(S)

and, if W Ì S then

Mt(W) ≤ Mt(S)

with equality only if W = S.  The following theorem demonstrates that M so defined is in fact the smallest number of subsets that will partition S.

The theorem requires two lemmas.  The first lemma uses the simple fact that if a new event that occurs at time t is appended to set S, then Mt(S) increases by one.

Lemma 1:  If S1, S2 are disjoint subsets of S and t a value in [0, T] then

Mt(S1 U S2) = Mt(S1) + Mt(S2)

Proof: Let A1, A2 and A3 be the matrices associated with S1, S2 and S1 U S2 respectively.  Then

Mt(S1) + Mt(S2) = Σn A1(n,t)  +  Σn A2(n,t)

where the first sum is over all en in S1 and the second is over all en in S2.  But

Σn A1(n,t)  +  Σn A2(n,t) = Σn A3(n,t)

where the third sum is over all en in S1 U S2. Recognizing

Σn A3(n,t) = Mt(S1 U S2)

completes the proof.

The same reasoning allows Lemma 1 to be extended to:

Lemma 2:  If S1, S2,…, SL are disjoint subsets of S where L ≤ N and t e [0, T], and

S = S1 U S2 UU SL

is a partition of S, then

Mt(S) = Mt(S1) + Mt(S2) + …+ Mt(SL).

The following Theorem contains the central idea that allows us to schedule S.

Theorem: The minimum number of conflict-free subsets sufficient to schedule S is M.

Proof:  First sufficiency will be proved followed by the minimality of M.  In the matrix A, the N events in S have been partitioned into N conflict-free subsets of one event each.  We may call this a maximal partition.  Scheduling S into M conflict-free subsets amounts to re-arranging the events in A to occupy only the first M rows without overlap; this is a minimal partition.  So consider the M by (T+1) matrix B of zeros.  We prove this theorem by providing an algorithm that maps events in S to matrix B so that each row of B is conflict free and no events from S are left out.  Then the k-th row of B contains the events in the conflict-free subset Ck.  For each t in [0, T] let

St = { en in S | pn = t }

be the subset of S consisting of all events starting at time t.  Note that some St may be empty.  Since each en in S belongs to exactly one St, the St are disjoint and their union is S.  Hence Lemma 2 implies

Mt(S) = Mt(S0) + Mt(S1) + … + Mt(ST)

for all t in [0, T] and this together with Lemma 1 imply

Mt(S0 U S1 UU Sk) ≤ M

for all k ≤ T and all t in [0, T].  Hence, if events in S0 are first mapped to matrix B, followed by those in S1, then S2, and so on (i.e., from left to right), this last inequality guarantees enough rows at each stage of the process to map the next set Sk. This proves the first part of the theorem, and we have:

Algorithm 1: Partition S into subsets St according to their start times t, then map them to matrix B in order from S0 to ST.  Events in St may be mapped to B in any order, but, for definiteness, we will use a “top-down” order, i.e., smaller row numbers are used first.  Note that some St may be empty.

Now assume we limit the number of rows in matrix B to M* < M.  But we know from the fact that M is the largest of the Mt (S) that there is a t for which

Mt(S) = M > M*.

Hence there is at least one event that cannot be mapped to matrix B.  This then implies M is the smallest number of rows (conflict-free subsets) that will schedule S.

Note that Lemma 2 implies Mt (Sj UU Sm) £ M for arbitrary unions of the St so matrix B may be mapped using any order of the St, not just left to right.  However, in most applications, e.g., assigning guests to hotel rooms, S0 plays a special role because it represents guests who are continuing a reservation already under way. Hence the members of S0 cannot be arbitrarily mapped to rows in B; they must remain in the rows to which they were assigned on the previous day.  Events in S0 are said to be locked in place and must be mapped first to avoid conflicts.

Because Algorithm 1 maps events in S0 first, their locked condition poses no problem.  The Theorem’s proof, and hence the algorithm it contains, made the tacit assumption that no other events are locked.  However, additional events may be locked in practical situations, for example, if guests request specific room numbers.  The addition of locked events sprinkled out in time results in irregular gaps of availability for the affected resources.  During periods of time when many events occur concurrently, the pattern of fragmentation from locked events can preclude Algorithm 1’s addition of certain free events that otherwise could be accommodated if no locked events were present. In such situations, the calculated value of M would indicate that an event could be added whereas the locked events make it impossible to do so.  If this happens, Algorithm 1 would fail because more than M rows of B would be required to schedule S.  Clearly, another algorithm is needed.  The only way to achieve optimum efficiency is to carefully fit free events into available gaps with a minimum of waste, which leads us to Algorithm 2.

Assume now that the set S contains two kinds of events, locked and free.  Free events can be mapped to any row of B, but locked events must be placed in pre-assigned rows.  (It is assumed that the subset of locked events is conflict-free.)  Algorithm 1 mapped events is S to matrix B in order of their start times.  In what follows we develop a second algorithm which first maps locked events to their pre-assigned row, then maps free events according to their degree of difficulty, which is calculated by summing the degree of overlap of concurrent events.  We start with two analogs of Mt:

Definition: Ft is the number of free events in S occurring at time t.  :

Ft = Ft(S) = ΣnAF(n,t),

where the sum is over all free events and the mapping function is given by

AF(n,t)   = 1   if  pn  ≤  t  ≤ qn and en is free

= 0   otherwise             .

Definition: Lt is the number of locked events in S occurring at time t:

Lt = Lt(S) = ΣnAL(n,t),

where the sum is over all locked events and the mapping function is given by

AL(n,t)   = 1   if  pn  ≤  t  ≤ qn and en is locked

= 0   otherwise.

Clearly, Mt = Ft + Lt for each t.  For each event en in S define two numbers

DF(n) = Σt Ft   and   DL(n) = Σt Lt ,

where each sum is taken over event times from pn to qn, inclusive.  Each of these numbers indicates a degree of difficulty in mapping the event to matrix B.  Reasoning that locked events pose greater difficulty than free ones, we have

Definition: the degree of difficulty (DOD) for event n is

D(n) = DF(n) + α DL(n) , where α > 1

In the work cited below we use α = 2, which is equivalent to saying that locked events pose twice as much difficulty as free ones.  In a separate paper we will explore how different values of α affect algorithm performance.

Definition: Sk is the set of events having degree difficulty k :

Sk = { en in S | D(n) = k }.

(Again, some of the Sk may be empty.)

Algorithm 2 maps events in S in decreasing order of their DOD, so events in Sk are mapped prior to those in Sk-1. This avoids most of the conflicts with locked and previously-mapped-free events encountered by Algorithm 1.  If it happens that all events can be mapped within the M rows of B, the algorithm ends.  However if a particular member of Sk, say event e, cannot be mapped within the M rows of B, the algorithm backs up and searches for a previously mapped conflicting event and attempts to move it to another row of B before proceeding forward again. If e can now be mapped the algorithm moves on to map the next event; otherwise it backs up to find an even earlier event in conflict with e before proceeding forward again. By successively iterating to every previously mapped event, every possible configuration of free events in S can, in principle, be tested.

We say in principle because the number of possible mappings of events in S to B may be so large that it is impractical to consider every one of them.  For example, a rental property with 15 units (M=15) and 44 reservations (N=44, with 11 of them locked) sprinkled over 40 days (T=41) had 1.6 x 1022 possible mappings.  With other data sets spanning a year and having hundreds of reservations spread over 60 units, this number can be greater than 10300.

Real-world tests show that our implementation of Algorithm 2 performs remarkably well.  For example, in one trial where Algorithm 1 failed, Algorithm 2 found a successful mapping after only 2094 attempts out of a possible 7.7 x 10152.  A detailed exploration into the remarkable efficiency of Algorithm 2 will be the subject of a separate paper.