THE TAPEBOARD PROBLEM AND A NEW SCHEDULING ALGORITHM
by: Rick Martinelli & Neil Rhoads, Haiku Laboratories

Large property management companies typically handle hundreds of rental units and thousands of bookings, sometimes spanning several years.  The tapeboard problem was brought to our attention by the IT manager of one such company.  Suppose a rental property has scheduled a large set of reservations, or bookings, into various of its rental units, each booking being defined by its start and end days relative to today, and where some of the guests have indicated they want specific units.  The general problem presented by the IT manager was:

a) Can a new booking be assigned to the property in a conflict-free way, without adjusting any pre-specified or occupied units?

b) If so, how can this be done?

A traditional approach to this problem has been to create a grid of squares called a tapeboard, whose rows correspond to rental units and whose columns represent today and future days.  A single square represents an available day-unit.  Bookings are then represented by strips of “tape” labeled with pertinent information that may be placed over adjacent squares in a row to signify the day-units that are assigned to the booking.  A conflict exists if one piece of tape overlaps any other piece of tape, i.e. if a day-unit is required by more than one booking.

 Day 0 Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Unit 1 1 1 1 1 8 8 8 Unit 2 3 3 7 Unit 3 2 2 2 2 2 Unit 4 4 6 6 6 6 6 6 Unit 5 5 5 5

Tapeboard 1. An 8-day tapeboard for a 5-unit property with 8 bookings scheduled.

Tapeboard 1 shows a spreadsheet version of a tapeboard, where cells represent day-units and booking numbers replace the tape.  Here a 5-unit property has scheduled 8 bookings (numbered 1 through 8) over 8 days.  Before a new booking is taken, the tapeboard is checked to see if there is an opening that matches the new booking.  If no opening is found, attempts are made to re-arrange existing bookings to accommodate the new booking.  For example, a new, 2-day booking starting on Day 1 will not ‘fit’ in the tapeboard as it is.  However a simple swap of bookings 6 and 7 allows the new booking to be scheduled in Unit 5.  This new configuration is shown in Tapeboard 2.

 Day 0 Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Unit 1 1 1 1 1 8 8 8 Unit 2 3 3 6 6 6 6 6 6 Unit 3 2 2 2 2 2 Unit 4 4 5 5 5 Unit 5 9 9 7

Tapeboard 2. A rearrangement of Tapeboard 1 to accommodate booking 9 in unit 5.

Another configuration, obtained from a more complicated rearrangement, puts booking 9 in Unit 4.  Others are easily seen.

 Day 0 Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Unit 1 1 1 1 1 8 8 8 Unit 2 3 3 6 6 6 6 6 6 Unit 3 5 5 5 Unit 4 4 9 9 7 Unit 5 2 2 2 2 2

Tapeboard 3.  Another rearrangement of Tapeboard 1 to accommodate booking 9 in unit 4.

Suppose now that another new, 2-day booking starting on Day 1 or 2 is requested.  It is clear from looking at Tapeboards 2 and 3, that no amount of swapping can accommodate such a booking.  This is the first way in which scheduling can fail.

Swapping to produce Tapeboards 2 and 3 is allowed because the guests associated with the swapped bookings have not yet arrived.  Note that bookings 1, 3 and 4 were not be swapped because they contain Day 0 (today) and are already occupied.  A further complication arises when some of the guests with future bookings indicate they want specific units.  These pre-assigned bookings are said to be locked in place or simply “locked”; all others are called free bookings.  Suppose, for example, that booking 7 in Tapeboard 1 insists on occupying unit 2, i.e., is locked in unit 2.  Then the new, 2-day booking starting on Day 1 will not fit within the 5 units in the tapeboard (recall that bookings 1, 3 and 4 cannot be swapped).   This is the second, more subtle, way in which scheduling can fail.

 Day 0 Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Unit 1 1 1 1 1 8 8 8 Unit 2 3 3 7 Unit 3 2 2 2 2 2 Unit 4 4 6 6 6 6 6 6 Unit 5 5 5 5 9 9

Tapeboard 4.  Booking 9 cannot be assigned to a Unit if booking 7 is locked in unit 2.

These simple examples demonstrate some of the problems associated with scheduling concurrent events.  When the number of bookings and units is large, manually swapping bookings becomes prohibitive and a computer algorithm is needed.

The scheduling algorithm developed by Haiku Laboratories to solve this problem has been described in the article Scheduling Algorithms For Concurrent Events.  Briefly, each booking is assigned a Degree-Of-Difficulty (DOD), depending on how many other bookings it overlaps.  Then bookings are placed in the tapeboard one at a time in decreasing DOD order, so that the booking with the highest DOD is placed first.  If all bookings can be placed in the tapeboard this way, the algorithm ends.  This is how Tapeboard 1 above was made.  After booking 9 was added, however, the algorithm had to swap bookings 6 and 7 to produce the arrangement in Tapeboard 2.  When booking 7 was locked in unit 2, the algorithm had to try all possible arrangements for the 5 remaining free bookings (2,5,6,8 and 9).  When no arrangement was found within the tapeboard’s 5 units, booking 9 was placed in non-existent unit 6. In practice, booking 9 would be moved to a different time-frame or property, or cancelled.

The algorithm is designed so that, in principle, all possible arrangements of free bookings can be tested for fit within the available units. We say in principle because the number of possible arrangements may be so large that it is impractical to consider every one of them.

For example, the arrangement in tapeboard 3 is one of a possible 1.5 x 1010.   A rental property with 15 units and 44 bookings had 1.6 x 1022 possible arrangements.  With other tapeboards spanning a year and having hundreds of bookings spread over 60 units, this number can be greater than 10300, more than that number of atoms in the known universe.  Fortunately, the algorithm appears to be remarkably efficient.  For example, in one test, only 2094 attempts out of a possible 7.7 x 10152  were needed.  Others typically require about 5000 of the 10300.

The algorithm has been implemented in a database system to accommodate multiple properties.  It is available from Haiku Laboratories for Windows systems.  On reasonably modern systems, the algorithm can try 5000 arrangements in just a few seconds.