**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 generic 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. Thus

*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” (e.g., today). Two events *e*_{1} and *e*_{2} overlap,
or are said to be *in-conflict,* whenever their intersection is
non-empty. Conversely, a set of N events

S = { *e*_{1}, *e*_{2}, …,
*e*_{N} }

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

** Definition**: the

That is,
find disjoint, conflict-free subsets of S, S_{1}, S_{2},…, S_{M}, such that their union is all of S,

S = S_{1} U S_{2} U … U S_{M}

and
M, the number of subsets, has the smallest possible value. This is called
*scheduling* S, and the collection of
sets S_{k} is called a *partition* of
S. To calculate M, let

S = { *e*_{n}_{
}| n=1,…, N }

be a set of events where

*e*_{n} = { p_{n}, p_{n}+1,
…, q_{n} }

for each n. Letting

T = max_{n} (q_{n})

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. The mapping function is

A(n,t) = 1 if p_{n}
≤ t ≤ q _{n }

=
0 otherwise

for
each *e*_{n} in S. Since A(n,t) is 1 if and only if event *e*_{n}
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**: M

M_{t} = M_{t}(S) = Σ_{n}A(n,t),

where the sum is over all events, and

** Definition**: M is the largest of the M

M = M(S) = Max_{t }{ M_{t}(S) }.

For each t, these definitions imply

M_{t}(S) ≤ M(S)

and, if W Ì S then

M_{t}(W) ≤ M_{t}(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 M_{t}(S)
increases by one.

** Lemma 1**: If S

M_{t}(S_{1} U S_{2}) = M_{t}(S_{1})
+ M_{t}(S_{2})

** Proof**: Let A

M_{t}(S_{1}) + M_{t}(S_{2})
= Σ_{n} A_{1}(n,t) + Σ_{n} A_{2}(n,t)

where the first sum is over all *e*_{n}
in S_{1} and the second is over all *e*_{n} in S_{2.}
But

Σ_{n} A_{1}(n,t) + Σ_{n} A_{2}(n,t) = Σ_{n} A_{3}(n,t)

where the third sum is over all *e*_{n} in S_{1} U S_{2}. Recognizing

Σ_{n} A_{3}(n,t) = M_{t}(S_{1} U S_{2})

completes the proof. ■

The same reasoning allows Lemma 1 to be extended to:

** Lemma 2**: If S

S = S_{1} U S_{2} U … U S_{L}

is a partition of S, then

M_{t}(S) = M_{t}(S_{1})
+ M_{t}(S_{2}) + …+ M_{t}(S_{L}).

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

S_{t} = { *e*_{n}
in S | p_{n} = t }

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

M_{t}(S) = M_{t}(S_{0})
+ M_{t}(S_{1}) + … + M_{t}(S_{T})

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

M_{t}(S_{0} U S_{1} U
… U S_{k}) ≤ M

for
all k ≤ T and all t in [0, T]. Hence, if events in S_{0}
are first mapped to matrix B, followed by those in S_{1}, then S_{2},
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 S_{k}. This
proves the first part of the theorem, and we have:

** Algorithm
1**: Partition
S into subsets S

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 M_{t }(S)
that there is a t for which

M_{t}(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 M_{t }(S_{j} U … U S_{m}) £ M for arbitrary unions of the S_{t} so
matrix B may be mapped using any order of the S_{t}, not just left to
right. However, in most applications, e.g., assigning guests to hotel
rooms, S_{0} plays a special role because it represents guests who are
continuing a reservation already under way. Hence the members of S_{0}
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 S_{0} are
said to be *locked* in place and must be mapped first to avoid
conflicts.

Because
Algorithm 1 maps events in S_{0} 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 M_{t}:

** Definition**: F

F_{t} = F_{t}(S) = Σ_{n}A_{F}(n,t),

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

A_{F}(n,t) = 1
if p_{n} ≤ t ≤ q_{n} and e_{n}
is free

= 0 otherwise.

** Definition**: L

L_{t} = L_{t}(S) = Σ_{n}A_{L}(n,t),

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

_{L}_{n} ≤ t ≤ q_{n }and e_{n}
is locked

= 0 otherwise.

Clearly,
M_{t} = F_{t} + L_{t} for each t. For each event
e_{n} in S define two numbers

D_{F}(n) = Σ_{t }F_{t} and D_{L}(n) = Σ_{t }L_{t },

where
each sum is taken over event times from p_{n }to q_{n},
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

D(n) = D_{F}(n) + α D_{L}(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**: S

S_{k} = { *e*_{n}
in S | D(n) = k }.

(Again,
some of the S_{k} may be empty.)

**Algorithm
2** maps events in
S in decreasing order of their DOD, so events in S_{k}
are mapped prior to those in S_{k-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 S_{k}, 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 10^{22} possible
mappings. With other data sets spanning a year and having hundreds of
reservations spread over 60 units, this number can be
greater than 10^{300}.

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 10^{152}.
A detailed exploration into the remarkable efficiency of Algorithm 2 will be
the subject of a separate paper.