The Airplane Seating Problem

Background:

Airlines are free to seat passengers waiting to board an aircraft in any order whatsoever. It has become customary to seat passengers with special needs first, followed by first-class passengers (who sit at the front of the plane). Then coach and business-class passengers are seated by groups of rows, beginning with the row at the back of the plane and proceeding forward.

Apart from consideration of the passengers' wait time, from the airline's point of view, time is money, and boarding time is best minimized. The plane makes money for the airline only when it is in motion, and long boarding times limit the number of trips that a plane can make in a day.

The development of larger planes, such as the Airbus A380 (800 passengers), accentuate the problem of minimizing boarding (and deboarding) time.

Devise and compare procedures for boarding and deboarding planes with varying numbers of passengers: small (85-210), midsize (210-330), and large (450-800).