Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Classical Model for Storage System Activity Read chapter Read first chapter

2014 | OriginalPaper | Chapter

3. Airplane Boarding, Disk Scheduling, and Lorentzian Geometry

Author : Eitan Bachmat

Published in: Mathematical Adventures in Performance Analysis

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We provide a detailed analysis of the airplane boarding process and evaluate various boarding policies using Lorentzian geometry. We also analyze several related problems such as I/O disk scheduling. Boarding policies which we analyze include, random, back-to-front, outside-in, no overhead bin luggage first among others. We also show that the motion of the earth around the sun may be viewed as being uniformly random.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Fractal Model for Storage System Activity
next chapter Mirrored Configurations
Literature
1.
2.
Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Am. Math. Soc. (N.S.) 36(4), 413–432 (1999)
7.
Andrews, M., Bender, M.A., Zhang, L.: New algorithms for the disk scheduling problem. In: 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pp. 550–559, IEEE Computer Society Press, Los Alamitos (1996)
11.
Aven, O.I., Coffman, E.G. Jr., Kogan, Ya.A.: Stochastic Analysis of Computer Storage. Mathematics and Its Applications, vol. 38. D. Reidel Publishing Co., Dordrecht (1987)
13.
Bachmat, E., Elhanan, I.: Analysis of the GSTF disk scheduling algorithm. Perform. Eval. Rev. 41(3), 13–15 (2013)CrossRef
14.
Bachmat, E., Elkin, M.: Bounds on the performance of back-to-front airplane boarding policies. Oper. Res. Lett. 36(5), 597–601 (2008)MathSciNetMATHCrossRef
16.
Bachmat, E., Berend, D., Sapir, L., Skiena, S., Stolyarov, N.: Analysis of aeroplane boarding via spacetime geometry and random matrix theory. J. Phys. A 39(29), L453–L459 (2006)MathSciNetMATHCrossRef
19.
Bachmat, E., Khachaturov, V., Kuperman, R.: Optimal back-to-front airplane boarding. Phys. Rev. E 87, 062805 (2013)CrossRef
20.
Baek, Y., Ha, M., Jeong, H.: Impact of sequential disorder on the scaling behavior of airplane boarding time. Phys. Rev. E 87(5), 052803 (2013)
21.
22.
Baik, J., Deift P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119–1178 (1999)MathSciNetMATHCrossRef
27.
Bazargan, M.: A linear programming approach for aircraft boarding strategy. Eur. J. Oper. Res. 183, 394–411 (2007)MATHCrossRef
33.
Bj’́orner, A., Stanley, R.P.: A Combinatorial Miscellany. L’Enseignement mathematique, Geneve (2010)
39.
Bollobás, B., Brightwell, G.: Box-spaces and random partial orders. Trans. Am. Math. Soc. 324(1), 59–72 (1991)MATHCrossRef
40.
Bollobás, B., Winkler, P.: The longest chain among random points in Euclidean space. Proc. Am. Math. Soc. 103(2), 347–353 (1988)MATHCrossRef
41.
42.
Brics, M., Kaupuzs, J., Mahnke, R.: Scaling behavior of an airplane-boarding model. Phys. Rev. E 87, 042117 (2013)CrossRef
44.
Bruss, F.Th., Delbaen, F.: Optimal rules for the sequential selection of monotone subsequences of maximum expected length. Stoch. Process. Appl. 96(2), 313–342 (2001)MathSciNetMATHCrossRef
46.
Cady, F., Zhuang, Y., Harchol-Balter, M.: A stochastic analysis of hard disk drives. Int. J. Stoch. Anal. 2011, 21 (2011) [Article ID 390548]
48.
Capelo, E. Jr., de Castro Silva, J.L., van den Briel, M.H.L., Villalobo, J.R.: Aircraft boarding fine-tuning. In: Proceedings of the 14th International Conference on Industrial Engineering and Operations Management (ICIEOM-2008), Rio de Janeiro, Brazil (2008)
51.
Chen, T.Sh., Yang, W.P., Lee, R.C.T.: Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and N-StepSCAN. BIT 32(4), 546–558 (1992)MathSciNetMATHCrossRef
53.
56.
Coffman, E.G., Klimko, L.A., Ryan, B.: Analysis of scanning policies for disk reducing seek times. SIAM J. Comput. 1(3), 269–279 (1972)MATHCrossRef
59.
Corwin, I.: The kardar-parisi-zhang equation and universality class. Random Matrices: Theory and Applications, 1(1) (2012)
63.
Deift, P.: Universality for mathematical and physical systems. In: International Congress of Mathematicians (Madrid 2006), vol. 1, pp. 125–152. American Mathematical Society, Providence (2007)
64.
Denning, P.J.: Effects of scheduling on file memory operations. In: Proceedings of AFIPS Spring Joint Computer Conference, Atlantic city, New Jersey, pp. 9–21 (1967)
65.
Deuschel, J.-D., Zeitouni, O.: Limiting curves for i.i.d. records. Ann. Probab. 23(2), 852–878 (1995)
77.
Ferrari, P., Nagel, K.: Robustness of efficient passenger boarding in airplanes. Transport. Res. Rec. 1915, 44–54 (2004)CrossRef
78.
Flajolet, P., Grabner, P.J., Kirschenhofer, P., Prodinger, H.: On Ramanujan’s Q-function. J. Comput. Appl. Math. 58, 103–116 (1995)MathSciNetMATHCrossRef
79.
80.
Frank, H.: Analysis and optimization of disk storage devices fortime-sharing systems. J. ACM 16(4), 602–620 (1969)MATHCrossRef
81.
Frette, V., Hemmer, P.C.: Time needed to board an airplane: a power law and the structure behind it. Phys. Rev. E 85, 11130 (2012)CrossRef
85.
Geist, R., Daniel, S.: A continuum of disk scheduling algorithms. ACM Trans. Comput. Syst. 5(1), 77–92 (1987)CrossRef
89.
Gotlieb, C.C., MacEwen, G.H.: Performance of movable-head disk storage devices. J. ACM 20(4), 604–623 (1973)MATHCrossRef
99.
Hofri, M.: Disk scheduling: FCFS vs. SSTF. Commun. ACM 23(11), 645–653 (1980)CrossRef
100.
Hooft, G.’t.: Quantum gravity: a fundamental problem and some radical ideas. In: Levy, M., Deser, S. (eds.) Recent Developments in Gravitation [Proceedings of the 1978 Cargese Summer Institute]. Plenum, New York (1979)
103.
Jacobson, D.M., Wilkes, J.: Disk scheduling algorithms based on rotational position, 1991. Technical Report. Hewlett-Packard, Palo Alto (1991)
105.
107.
Johansson, K.: Transversal fluctuations for increasing subsequences on the plane. Probab. Theor. Relat. Field. 116(4), 445–456 (2000)MathSciNetMATHCrossRef
116.
Kingman, J.F.C.: Subadditive ergodic theory. Ann. Probab. 1, 883–909 (1973) [With discussion by D. L. Burkholder, Daryl Daley, H. Kesten, P. Ney, Frank Spitzer and J. M. Hammersley, and a reply by the author]
118.
Knuth, D.E.: The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)
119.
121.
Konheim, A.G., Weiss, B.: An occupancy discipline and applications. SIAM J. Appl. Math. 14, 1266–1274 (1966)MATHCrossRef
131.
132.
Löwe, M., Merkl, F.: Moderate deviations for longest increasing subsequences: the upper tail. Comm. Pure Appl. Math. 54(12), 1488–1520 (2001)MathSciNetMATHCrossRef
135.
Mallows, C.L.: Problem 62-2 patience sorting. SIAM Rev. 5, 375–376 (1963)
136.
Mallows, C.L.: Patience sorting. Bull. Inst. Math. Appl. 9, 216–224 (1973)
138.
Marelli, S., Mattocks, G., Merry, R.: The role of computer simulation in reducing airplane turn time. Aero Magazine, 1 (1998)
143.
Mehta, M.L.: Random Matrices, Pure and Applied Mathematics (Amsterdam), 3rd edn., vol. 142. Elsevier/Academic, Amsterdam (2004)
144.
Meyer, D.: The dimension of causal sets. Ph.D. thesis, M.I.T. (1988)
151.
Myrheim, J.: Statistical geometry. CERN preprint TH-2538 (1978)
152.
Nyquist, D.C., McFadden, K.L.: A study of the airline boarding problem. J. Air Traffic Manag. 14, 197–204 (2008)CrossRef
155.
157.
Pavlov, Y.: The asymptotic distribution of maximum tree size in a random forest. Theor. Probab. Appl. 22(3), 509–520 (1977)MATHCrossRef
158.
Penrose, R.: Techniques of Differential Topology in Relativity. Society for Industrial and Applied Mathematics, Philadelphia (1972) [Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 7]
162.
164.
Ramanujan, S.: On question 294. J. Indian Math. Soc. 4, 151–152 (1912)
165.
Ramanujan, S.: Question 294. J. Indian Math. Soc. 3, 128 (2014)
176.
Schultz, T., Kunze, M., Fricke, H.: Boarding on the critical path of the turnaround. In: 10th USA/Europe Air Traffic Management Research and Development Seminar (ATM2013), Chicago, Illinois (2013)
177.
Seltzer, M., Chen, P., Ousterhout, J.: Disk scheduling revisited. In: Proceedings of the USENIX Technical Conference, Anaheim, California, pp. 313–324 (1990)
183.
Stanley, R.P.: Increasing and decreasing subsequences and their variants. In: International Congress of Mathematicians (Madrid, 2006), vol. 1, pp. 545–579. American Mathematical Society, Providence (2007)
184.
Steffen, J.: Optimal boarding method for airline passengers. J. Air Transport Manag. 14, 146–150 (2008)CrossRef
185.
Steffen, J.: A statistical mechanics model for free-for-all airplane passenger boarding. Am. J. Phys. 76, 1114 (2008)MathSciNetCrossRef
186.
Steffen, J., Hotchkiss, J.: Experimental test of airplane boarding methods. J. Air Transport Manag. 18(1), 64–67 (2012)CrossRef
188.
Steiner, A., Philipp, M.: Speeding up the airplane boarding process by using pre-boarding areas. In: Proceedings of the 9th Swiss Transport Research Conference (STRC), Monte verita, Switzerland (2009)
190.
Tang, T.Q., Huang, H.J., Shang, H.Y.: A new pedestrian-following model for aircraft boarding and numerical tests. Nonlinear Dynam. 67, 437–443 (2012)CrossRef
191.
Tang, T.Q., Wu, Y.H., Huang, H.J., Caccetta, L.: An aircraft boarding model accounting for passengers’ individual properties. Transport. Res. C Emerg. Tech. 22, 1–16 (2012)CrossRef
194.
Taylor, R., Wiles, A.: Ring-theoretic properties of certain Hecke algebras. Ann. Math. (2) 141(3), 553–572 (1995)
195.
Teorey, T.J., Pinkerton, T.B.: Comparative analysis of disk scheduling policies. Commun. ACM 15, 177–184 (1972)MATHCrossRef
197.
Thomasian, A., Liu, C.: Some new disk scheduling policies and their performance. In: Proceedingsof the ACM SIGMETRICS 02, Marina del ray, California, pp. 266–267 (2002)
198.
Thomasian, A., Liu, C.: Performance evaluation for variations of the satf scheduling policy. In: Proceedings of SPECTS 04, San Jose, California, pp. 431–437 (2004)
203.
Ulam, S.M.: Monte Carlo calculations in problems of mathematical physics. In: Modern Mathematics for the Engineer: Second Series, pp. 261–281. McGraw-Hill, New York (1961)
204.
van den Briel, M.H.L., Villalobos, J.R., Hogg, G.L.: The airfcraft boarding problem. In: Proceedings of the 12th Industrial Engineering Research Conference (IERC-2003), Nr 2153, CD-ROM., Portland, Oregon (2003)
205.
van den Briel, M.H.L., Villalobos, J.R., Hogg, G.L., Lindemann, T., Mule, A.: America west develops efficient boarding strategies. Interfaces 35(3), 191–201 (2005)CrossRef
206.
van Landeghem, H., Beuselinck, A.: Reducing passenger boarding times in airplanes: a simulation based approach. Eur. J. Oper. Res. 142(2), 294–308 (2014)CrossRef
207.
Veršik, A.M., Kerov, S.V.: Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk SSSR 233(6), 1024–1027 (1977)MathSciNet
208.
Viola, A.: Distributional analysis of the parking problem and robin hood linear probing hashing with buckets. Discrete Math. Theor. Comput. Sci. 12(2), 307–332 (2010)MathSciNetMATH
216.
Wilhelm, N.C.: An anomaly in disk scheduling: a comparison of fcfs and sstf seek scheduling using an empirical model for disk accesses. Commun. ACM 19(1), 13–18 (1976)MATHCrossRef
217.
Worthington, B.L., Ganger, G.R., Patt, Y.L.: Scheduling for modern disk drives and non-random workloads, pp. 241–251. In: Proceedings of ACM SIGMETRICS Conference, Nashville, Tennessee (1994)
218.
Wong, C.K.: Algorithmic Studies in Mass Storage Systems. W.H. Freeman & Co., New York (1983)CrossRef
219.
Yeh, T.-H., Kuo, Ch.-M., Lei, Ch.-L., Yen, H.-Ch.: Competitive analysis of on-line disk scheduling. Theory Comput. Syst. 31(5), 491–506 (1998) [Seventh International Symposium on Algorithms and Computation, Osaka, 1996]
220.
Metadata
Title
Airplane Boarding, Disk Scheduling, and Lorentzian Geometry
Author
Eitan Bachmat
Copyright Year
2014
Book
Mathematical Adventures in Performance Analysis

Print ISBN: 978-3-319-09512-7

Electronic ISBN: 978-3-319-09513-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09513-4_3

Premium Partners

    Image Credits