Deconstructing Pop Culture

Deconstructing Pop Culture header image

PSA’s Queuing Algorithm

December 12th, 2006 by David Kronemyer · No Comments

An article in today’s Wall Street Journal reports on the perils of air travel on routes where the airplane congenitally runs late, or is delayed, McCartney, S., “Dodging Holiday ‘Loser Flights,’” Wall St. Journal (Dec. 12, 2006). Mr. McCartney cites several examples derived from FlightStats, a firm that tracks real-time airline flight data. Advises Mr. McCartney:

“To be sure, knowing the history doesn’t mean you can escape delays since bad fortune and bad weather have a huge impact on your travel. But you can hedge your bets by looking at flight history, and at least prepare yourself for the possibility. Ticketed on a chronically late flight, for example, you might want to pack extra snacks, arm yourself with schedules of later flights or other airlines and, if you have to make a connection, avoid checking luggage and maybe even book yourself a hotel room at the connecting hub city that you can cancel if you happen to be on schedule.”

The tales of woe related by Mr. McCartney reminded me of a long-defunct carrier based in Southern California, which was Pacific Southwest Airlines (“PSA”). PSA was one of the first “discount” airlines in the U.S., and, in retrospect, can be considered as a kind of precursor to today’s Southwest Airlines. PSA was known for its ad campaigns; it billed itself as “The World’s Friendliest Airline,” and its trademark was a smile painted on each plane’s nose. Its flight attendants wore a classic ‘60s uniform – a brightly-colored (and extremely short), “mod”-style dress.

Over the space of a decade, I took a countless number of PSA flights all over California. In fact, I still find PSA ticket jackets in books I must have been reading at the time, depicting those uniforms – an amusing reminder of days gone by. Then again, I nearly was on PSA Flight 182, which crashed on September 25, 1978, killing all aboard – the worst air accident in California history.

The best part about PSA was its queuing algorithm. A “queue” is a waiting line. PSA’s philosophy was, if a plane ran late, or a flight was canceled, it’s best to piss off a few customers a lot, rather than a lot of customers, a little. Therefore, it would do everything it could to keep all subsequent flights on schedule, totally abandoning the passengers (actually, would-be passengers) of the ill-fated earlier flight. Sure, it might try to place those customers on subsequent flights, but it definitely would not push later flights back, in order to accommodate the inconvenienced passengers of the earlier, canceled flight. The effects of this principle were exacerbated by the fact the most-demanded flights were in the early morning and late afternoon to early evening, which is when intra-state business travelers were going to and coming from their respective destinations.

In this respect, PSA was an early-adopter of Operations Research, a kind of quasi-mathematical hocus-pocus deploying statistical methods to address the coordination and execution of operations within a firm, presumably to derive a “best-practices result.”

The basic insight behind queuing theory is, congestion within a closed-loop system causes “service delays.” The “types” of delay elements affecting the system can be classified into different categories. These include: “processing delay” (the delay between the time of an element’s receipt into the system, and the time it is put into the queue); “queuing delay” (the delay between the time the element enters the queue, to the time when it actually is dispatched); “transmission delay” (how long it takes to send or transmit the element); “propagation delay” (how long it takes the last element sent or transmitted to reach its destination); and “retransmission delay”) (which results when an element is lost and has to be re-sent).

The type of delay most relevant to PSA is queuing delay. There was little processing delay; they’d check you in, as fast as they could. Barring adverse weather conditions, there wasn’t transmission delay. Propagation delay isn’t an issue, as the passengers in the back of the airplane arrive only a very short time after the passengers in the front of the airplane. And, there wasn’t retransmission delay, unless they lost your baggage (which was known to happen; then as now, the best policy was to travel as light as possible!).

It transpires there even is an algebraic theorem to explain this process, which is: the average number of elements the system can process (N) is the average customer arrival rate (λ) multiplied by the average per-customer service time (T), or, N = λT.

For example, let’s say PSA cancels one of its early morning flights. The number of elements (i.e., passengers) awaiting transmission (i.e., the next flight to the same destination) thereupon doubles (assuming each plane was full, and they usually were). If the average service time remains constant (i.e., no further airplanes were put into service), then the average number of elements the system must process (i.e., passenger waiting time) also will double.

The only circumstance under which it wouldn’t double is if waiting time was cut in half, i.e., another plane promptly was was deployed. PSA, however, (a) never would deploy any additional aircraft, because it would be expensive to do so (and besides, they probably didn’t have any spares, as all of them were en route to somewhere or other); and (b) would preserve the timeliness of all further flights, by departing them on schedule. In this way, the equation remained completely balanced, because it simply excluded the delayed passengers. This of course just is an example, there are a number of other factors affecting the outcome, but you get the picture.

Based on this type of analysis, PSA could dynamically analyze the elements of its system, including various probability densities determining the “arrival process” (how many elements arrive in the system for processing, i.e., passengers waiting for flights); the “service process” (which determines the average service time per element, i.e., how long a passenger has to wait to get on an airplane); and, the “number of servers” (i.e., airplanes) required in order to accommodate demand, on a timely basis.

While I don’t want to get too theoretical, PSA adopted what is called a “Markov” probability distribution, in which certain data elements (i.e., passengers) were weighted more heavily than others. The favored data elements were the regularly-scheduled passengers on subsequent flights; the disfavored data elements were the passengers of the canceled flight. This is opposed to what is called a “deterministic” probability density, where all data elements have the same value (i.e., all passengers treated equally). This resulted in a “first in, last out”-type of system – a highly inequitable result for the delayed passengers, but a harmonious one for everybody else.

Maybe that’s why they went out of business?