2018_EJRNL_PP_EITAN_BACHMAT_1.pdf
Terbatas Erlin Marliana Effendi
» ITB
Terbatas Erlin Marliana Effendi
» ITB
Airlines have been implementing several policies which partition passengers into groups of fast
and slow passengers and placing them in different queue/row combinations. For example, the
policy which provides boarding precedence to passengers needing assistance and families traveling
with small children, or a policy which provides precedence to passengers with no overhead bin
luggage. The idea of separating customers into groups with different service times also appears
in the very different setting of express line queues, for example, in the supermarket or in server
farms. Such queues have been extensively explored in the last 20 years in the queueing theoretic
literature.
We show that the two systems, airplane boarding with slow and fast passenger groups and
express line queues are intimately related in the asymptotic regime where the ratio between the
slowest and fastest customer becomes large. We produce good algorithms for placing different
groups of passengers in the airplane boarding setting with competitive guarantees compared to
optimal placements. We then show how we can analyze the airplane boarding setting using results
from the express line setting. This relation provides a novel bridge between the theory of project
management and the critical path method to which airplane boarding belongs and queueing theory
to which express line queues belong.
The analysis uses very basic notions and arguments from geometry, but in the setting of
space-time (Lorentzian) geometry, a geometry which was invented to study relativity theory.