Airplane boarding, disk scheduling and space-time geometry

Eitan Bachma; Daniel Berend; Luba Sapir; Steven Skiena

Airplane boarding, disk scheduling and space-time geometry

Eitan Bachma
, Daniel Berend
, Luba Sapir
, Steven Skiena

Computer Science

Ben-Gurion University of the Negev
Ben-Gujion University

Research output: Contribution to journal › Conference article › peer-review

8 Scopus citations

Abstract

We show how the process of passengers boarding an airplane and the process of optimal I/O scheduling to a disk drive with a linear seek function can be asymptotically modeled by 2-dimensional space-time geometry. We relate the space-time geometry of the models to important quantities such as total boarding time and total service time. We show that the efficiency of a boarding policy depends crucially on a parameter k which depends on the interior design of the airplane. Policies which are good for small values of k are bad for large values of k and vice versa.

Original language	English
Pages (from-to)	192-202
Number of pages	11
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3521
State	Published - 2005
Event	First International Conference on Algorithmic Applications in Management, AAIM 2005 - Xian, China Duration: Jun 22 2005 → Jun 25 2005

Cite this

@article{5b1ead4e0bc24d8fafc61a00f429bf2f,

title = "Airplane boarding, disk scheduling and space-time geometry",

abstract = "We show how the process of passengers boarding an airplane and the process of optimal I/O scheduling to a disk drive with a linear seek function can be asymptotically modeled by 2-dimensional space-time geometry. We relate the space-time geometry of the models to important quantities such as total boarding time and total service time. We show that the efficiency of a boarding policy depends crucially on a parameter k which depends on the interior design of the airplane. Policies which are good for small values of k are bad for large values of k and vice versa.",

author = "Eitan Bachma and Daniel Berend and Luba Sapir and Steven Skiena",

year = "2005",

language = "English",

volume = "3521",

pages = "192--202",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "First International Conference on Algorithmic Applications in Management, AAIM 2005 ; Conference date: 22-06-2005 Through 25-06-2005",

}

TY - JOUR

T1 - Airplane boarding, disk scheduling and space-time geometry

AU - Bachma, Eitan

AU - Berend, Daniel

AU - Sapir, Luba

AU - Skiena, Steven

PY - 2005

Y1 - 2005

N2 - We show how the process of passengers boarding an airplane and the process of optimal I/O scheduling to a disk drive with a linear seek function can be asymptotically modeled by 2-dimensional space-time geometry. We relate the space-time geometry of the models to important quantities such as total boarding time and total service time. We show that the efficiency of a boarding policy depends crucially on a parameter k which depends on the interior design of the airplane. Policies which are good for small values of k are bad for large values of k and vice versa.

AB - We show how the process of passengers boarding an airplane and the process of optimal I/O scheduling to a disk drive with a linear seek function can be asymptotically modeled by 2-dimensional space-time geometry. We relate the space-time geometry of the models to important quantities such as total boarding time and total service time. We show that the efficiency of a boarding policy depends crucially on a parameter k which depends on the interior design of the airplane. Policies which are good for small values of k are bad for large values of k and vice versa.

UR - https://www.scopus.com/pages/publications/25144499028

M3 - Conference article

AN - SCOPUS:25144499028

SN - 0302-9743

VL - 3521

SP - 192

EP - 202

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - First International Conference on Algorithmic Applications in Management, AAIM 2005

Y2 - 22 June 2005 through 25 June 2005

ER -

Airplane boarding, disk scheduling and space-time geometry

Abstract

Other files and links

Fingerprint

Cite this