Security Screening: Bottleneck Analysis

Earlier Dawen wrote an article about her recent experience in security screening at Gatwick Airport. I thought this was an opportunity to demonstrate a simple process analysis tool which could be considered a part of Operations Research: Bottleneck Analysis.

At the airport, servers in the two-step security check process were un-pooled and thus dedicated to one another. By this, I mean that a security system with four staff checking boarding passes (step 1) and six teams at x-ray machines (step 2) were actually functioning as four separate units rather than as a team. Each unit had a boarding pass checker, two of the units had a single x-ray machine and the other two units had two x-ray machines. The consequence of this was that the one-to-one units overwhelmed their x-ray teams, forcing them to stop checking boarding passes and remaining idle. The one-to-two units were starved of passengers as the boarding pass checking could not keep up, resulting in idle x-ray machines.

We know that this configuration is costing them capacity. A very interesting question is: How much?

A Bottleneck Analysis is a simple tool for determining a system's maximum potential throughput. It says nothing about total processing time or the amount of passengers waiting in the system, but it does determine the rate at which screenings can be completed. Think of it as emptying a wine bottle upside down. Whether it's a half full bottle of molasses or a full bottle of wine, the maximum rate of flow is determined by the width of the neck (the bottleneck!). The maximum throughput rate of a system is equal to the throughput rate of its bottleneck.

The throughput of the current system is the limited by the bottleneck in each unit, each sub-system. In the case of the one-to-one units we know this is the x-ray machine, as they are unable to keep up with supply from upstream and are thus limiting throughput. In the case of the one-to-two units we know it is the boarding pass checker as the x-ray machines are waiting idly for new passengers and are thus limited. It follows that the maximum throughput for the combined system is two times the throughput of a single boarding pass checker plus two times the throughput of a single x-ray machine.

The natural reconfiguration that Dawen alludes to her in her article is one where the resources are pooled and the queues are merged. Rather than having two x-ray machines dedicated to a single boarding pass checker, passengers completing step 1 are directed to the x-ray machine with the shortest queue. In this way an x-ray machine is only idle if all four boarding pass checkers are incapable of supplying it a passenger and a boarding pass checker is only idle if all six x-ray machines are overwhelmed.

What is the throughput of this reconfigured system? The throughput is equal to the bottleneck of the system. This is either the four boarding pass checkers as a team if they are incapable of keeping the x-rays busy or the x-ray machines as a group because they are unable to keep up with the checkers. The bottleneck and thus maximum throughput is either equal to four times the throughput of a boarding pass checker (step 1) or six times the throughput of an x-ray machine (step 2), whichever is smaller.

Returning to the exam question, how much capacity is this miss-configuration costing them? At this point we need must resort to some mathematical notation or else words will get the better of us.

Readers uninterested in the mathematics may want to skip to the conclusion.

Let x be the throughput rate of an x-ray machine.
Let b be the throughput rate of a boarding pass checker.

The maximum throughput of the as-is system is thus 2x + 2b (see earlier).
If step 1 is the bottleneck in the reconfigured system then the max throughput is 4b.
If step 2 is the bottleneck of the reconfigured system then the max throughput is 6x.

If 4b <> 6x then step 2 is the bottleneck.

If we were managers working for the British Airport Authority (BAA) at Gatwick Airport our work would essentially be done. We could simply drop in our known values for b and x and reach our conclusion. For this article, though, we don't have the luxury of access to that information.

Returning to the exam question again, how can we determine what the cost of this miss-configuration is without knowing b or x?

We will employ a typical academic strategy:
Let b = αx or equivalently b/x = α.

If 4b <> 1.5 then the throughput of the new system is 6x.

The throughput of the as-is system is 2b + 2x = 2 α x + 2x.

The fraction of realized potential capacity in the as-is system is the throughput of the as-is system divided by the potential throughput of the reconfigured system.

If α < x =" 1/2"> 1.5 then it is (2 α x + 2 x) / 6x = 1/3 + α/3

What are the possible values of α? We know α is at least 1 because otherwise the x-ray machines in the one-to-one systems would not be overwhelmed by a more productive boarding pass checker. We know α is less than 2 or else the x-ray machines in the one-to-two systems would not have been idle.

We know have a mathematical expression for the efficiency of the current system:

f(α) = 1/2 + 1/(2 α) where 1 <= α <= 1.5 f(α) = 1/3 + α /3 where 1.5 <= α <= 2 But what does this look like?

Depending on the relative effectiveness of boarding pass checking and the x-ray machines, the current efficiency is as follows:

If α is 1 or 2, then the as-is system is at peak efficiency. If α is 1.5 we are at our worst case scenario and efficiency is 83.3% of optimal.

Conclusion

Based on the graph above, depending on the relative effectiveness of the boarding pass screeners and the x-ray machines (unknown), the system is running at between 83.3% and 100% efficiency. The most likely values is somewhere in the middle, so there is a very good chance that the configuration of the security system is costing them 10% of possible capacity. To rephrase that, a reconfiguration could increase capacity by as much as 20%, but probably around 11%. In the worst case a reconfiguration could allow for the reallocation of an entire x-ray team yielding significant savings.

As stated previously, a bottleneck analysis will determine the maximum throughput rate, but it says nothing about the time to process a passenger or the number of passengers in the system at any one time. We now know that this miss-configuration is costing them about 10% capacity, but there are other costs currently hidden to us. What is the customer experience currently like and how could it improve? Is the current system causing unnecessary long waiting times for some unlucky customers? Definitely. More advanced methods like Queuing Theory and Simulation will be necessary to answer that question, both tools firmly in the toolbox of Operations Research practitioners.

Related articles:
OR not at work: Gatwick Airport security screening (an observation and process map of the inefficiency)
Security Screening: Discrete Event Simulation with Arena (a quantification of the inefficiency through simulation)

OR not at work: Gatwick Airport security screening

I fly through London Gatwick airport quite a bit, whose operation is managed by BAA (British Airport Authority). Usually, I'm quite pleased with my experience through the security screening. However, for my last flight on April 1st from Gatwick to Milano, I was quite intrigued by how poorly it was run. I didn't think it was an April Fool's joke. :) So, after I went through the lines, I sat down, observed, and took some notes.

This was how it was set up (click to enlarge).

To start with, Queue1a & Queue1b were quite long and slow moving. Basic queueing theory and resource pooling principles tell us that 1 queue for multiple servers is almost always better than separate queues for individual servers. Therefore, I was surprised to see 2 queues. Roughly 100+ people were waiting in these 2 queues combined. I waited for at least 15-20 minutes to get to the CheckBoardingPass server.

I wasn't bored though, because the second thing that surprised me was that within the same queue, one CheckBoardingPass server was processing passengers, while the other had to halt from time to time. It was because Queue2a was backed up to the server, while Queue2b&c were almost empty. After I saw how the x-rays were setup, it was easy to see that the unbalanced system was due to the 6 x-rays not being pooled together.

The effect was a long wait for all to start with in Queue1a&b, then some waited nothing at all (i.e. me) in Queue2b/c/d/e, while others waited in a lineup of 5-15 people in Queue2a/f. For the 4 CheckBoardingPass ladies, 2 of them were busier than the others, but all could feel the pressure and frustration from the passengers in Queue1a&b. For the staff manning the x-rays, this meant some were very busy processing passengers, while others were waiting for people to show up.

Also worth mentioning was that each x-ray was staffed by 5 persons: 1 before it to move the baskets and luggage towards the x-ray, 1 at it to operate the x-ray, 1 after it to move the luggage and baskets away from the x-ray, and 2 (1 male and 1 female) to search the passengers going through the gate, if they trigger the bleep. Seems very labour intensive. If they studied the arrival pattern of passengers needing to be searched, I wonder if it'd save some personnel here by pooling at least the searchers for a couple x-rays (if unions permit!).

We've had this type of problem cracked for some time now and it is surprising to see major problems still. Gatwick Airport / BAA was obviously doing quite well all the other times I've gone through. How easy it is for a good organisation to perform poorly just by ignoring a few simple queue setup rules. For example, in 2001, my master's program run by the Centre for Operations Excellence out in the University of British Columbia, in the lovely Vancouver, Canada, did a very good project with the local Vancouver International Airport (YVR) on just that. The project used simulation to come up with easy-to-follow shift rules for the security line-ups so that 90% of the passengers would wait for less than 10 minutes to go through. In fact, the project even caught the attention of the media, and was broadcasted on the Discovery Channel (how cool is that, and how fitting for OR work). Watch it here. Now come on, BAA, you can do better than this.

Related articles:

Security Screening: Bottleneck Analysis (a mathematical quantification of the inefficiency)

Security Screening: Discrete Event Simulation with Arena (a quantification of the inefficiency through simulation)

Update (9 Oct 2010):

in this article, we erroneously stated that the airport operator was BAA (British Airports Authority). In fact, BAA was forced to sell Gatwick to please regulators seeking to break a monopoly on UK's airports. Our apologies to BAA. The current owners are Global Infrastructure Partners, who also owns 75% of the London City Airport.

Hollywood stock exchange to become reality?

A year and a half ago, we wrote an article, Forecasting Hollywood movie box office revenue with HSX trading history, based on a talk by Natasha Foutz at the 2008 INFORMS Conference in Washington, DC.

Today I see in the news (Movie futures market approved) that trading of futures related to movies' box office success is about to become a reality. There may be some legal and political obstacles left to surmount, but there may yet be more data to work with in this line of research.

Curiously the article focuses on financial aspects of the new financial instruments rather than the consequences for Operations Research. Market liquidity and hedging by large and independent film financiers is a laudable goal, but think of the statistics!

I would be interested to know what sort of use movie theatres/cinemas could make of these predictions when making operational and strategic decisions regarding film selection and scheduling.

The 5 acts of the financial crisis - review of The Power of Yes

Ever wanted answers to some of the many questions in your head on the current financial crisis? Want to know how the story started? David Hare's play, The Power of Yes, at the National Theatre in London kept me on the edge of my seat feverishly taking notes in the dark, and hanging onto every word said in the 1hr45min stage play. If you have the chance, see it. For someone like me, who's not had much to do with finance but would like to understand, this is investment 101, with interesting, non-monotone lecturers. (Actually, I did take Investment 101 in an MBA module during my master of management in operations research program at the Sauder School of Business in Vancouver, Canada, and the prof was quite fun.)



The story informatively reveals to the audience the complexity of the crisis' origin, however, mainly pointing fingers at the bankers, the governments and the mathematical models which claim to predict the future. Altogether they upset the balance of greed and fear, which the financial market and capitalism survive on. The story tells of the current (2007-present) financial crisis in 5 acts: SLUMP.

1. Sub-prime
   
2. Liquidation
3. Unravelling
4. Meltdown
5. Pumping

1. Sub-prime loans (this is the longest part as much history is involved)
Hare starts the storytelling with a mathematical formula (which perked me up right away) - the Black-Scholes formula for option pricing. Wikipedia says, "Trillions of dollars of options trades are executed each year using this model and derivations thereof". That's why Hare went straight to it, and throughout the play referred to the model and its derivations as to "claim to predict the future". Also mentioned was the Monte-Carlo model of the probability of defaulting.

Perhaps I'm biased, as this is operations research in finance, but I would disagree with Hare's statement about the models claiming to predict the future. All models are an approximation to the real world, but aren't the real world, so they always have inherent flaws and limitations. Understanding the limitations is the key to applying the results from the models in the real world, otherwise it is foolish and risky. If you read through the Wikipedia article on the Black-Scholes formula, you will see that it also tries to make this point across to the readers. Assumptions such as a 'rational market and behaviour' and 'normality' goes out of the window when in a financial crisis like the stock market crash, and the model becomes defunct.

Having set the theoretical stage and outlined one 'villain', Hare goes on to illustrating the roles of the second 'villain' - the governments, in particular, the British and the US governments. In 1997, the British government made the Bank of England an independent entity, and gave the regulatory and monetary policy setting responsibility of the financial system to a new body, FSA (Financial Services Authority), so that the banks could concentrate on running the bank business and managing its products. However, Hare argues that this division of responsibility meant no one was responsible for the overall financial system. The FSA was more of a neighbourhood watchdog than a police of the system. Also, the financial sector grew to 9% of UK's economy paying the government 27% of the taxes it collected. It was a big cash cow, and no government wanted to limit its growth. In fact, the Bush administration wanted every American to own his/her home, which only encourages borrowing.

Then the third 'villain' is revealed, the banker. The banker is greedy, and is driven to be so by targets and "regular incremental growth". The banker encouraged the people to buy homes when they couldn't afford it, and pressured the credit rating agencies to give good credits so the people can get loans. The division of responsibility meant no one was ensuring the credit ratings were reliable when the banks pushed to make more money by lending it out to every living and breathing person, but who can't actually afford it. Sub-prime loans.

2. Liquidation
("The conversion of assets into cash. Just as a company may liquidate an entire subsidiary by selling it to another firm, so too may an investor liquidate by selling a particular type of security.")

Why were the bankers pushing for more loans? Because homes = assets, and assets = more leverage to lend out for the banks. In fact, The Royal Bank of Scotland (RBS) was lending out at 30-to-1 leverage ratio (i.e. you lend out £30 based on £1 of asset).

The game of slicing and dicing of assets into packages and then trading it with other financial institutions (i.e. selling / liquidating debts) meant that soon enough no one knew what was in those packages, but some of them were sub-prime loans, which was toxic debt. The concept of toxic debt is well explained here: "The easiest way to describe toxic debt is to see it as two separate issues. One, large amounts of loans were improperly given higher credit ratings (implying lower risk of default). The second is that the value of the homes securing these loans has dropped".

3. Unravelling
Credit = Trust. Toxic loans ==> bad credit ==> no trust.

On August 9, 2008, banks lost trust, and stopped lending money. One quote from the play says, "Banks don't go bankrupt for any other reason... but that they ran out of money". This brought the financial system to a halt. Capitalism was having a cardiac arrest. Let's just say the media didn't help and drove fear steady into the mass.

4. Meltdown
Subsequently, the cardiac arrest brought down Lehman Brothers in the US first, and in the UK, Northern Rock went down as the nation's first casualty. The fall of Lehman Brothers triggered a world-wide panic and collapse of 'trust' in the financial system. People in the UK were queueing for their money from the banks. The Brits love to queue for things: a quote from the play, "When the Brits see a queue, they join it". In the US, the big financial institutions went one after the other into troubles.

5. Pumping
The US government had to bail them out by spending hundreds of billions of dollars. And if they didn't do so, the other sectors would be dragged down by the fall of the financial sector as well. Then other governments followed suit as this is a global financial crisis, and now governments are wasting and pumping money into the economy to try to rescue it.


This wraps up the 1hr45min play with no intermission. I think the title, the power of yes, is referring to the 3 'villains' of the story saying yes to lending recklessly, and therefore creating debt-laden societies. What's your interpretation? I hope I've done the play justice. I thoroughly enjoyed it, and learned lots from it that is helping me shape my understanding of the financial crisis. I wonder why my alma mater didn't include any financial applications of operations research in the programme. Is it because it is so easily misunderstood by newcomers? Then wouldn't that be a reason for teaching it more broadly?

American Doctors Thoughts on Obama's Health Transformation

Came across this article on Capgemini's Health Transformation blog: Doctors thoughts about Obamacare. It is too funny not to share. Also note, it is most likely written by an American, or someone connected to the American healthcare system, due to the word usage of "Anesthesiologists" and "Pediatricians", because in the UK, people would say "Anaesthetists" and "Paediatricians", while in Canada, it would be "Anaesthesiologists" and "Paediatricians" - much like the word choice of "trash", "rubbish", and "garbage". :)

Members of the medical community has weighed in on the new health care plan being developed by the Obama Team:

The Allergists thought that it should be scratched,
and the Dermatologists advised not to make any rash moves.

The Gastroenterologists had a bad gut feeling about it,
while the Neurologists thought the Administration had a lot of nerve.

The Obstetricians felt Obama is laboring under a misconception.

Ophthalmologists considered the idea shortsighted.

Pathologists yelled, "Over my dead body!"
while the Pediatricians said, 'Oh, Grow up!'

The Psychiatrists thought the whole idea was madness,
while the Radiologists could see right through it.

Surgeons decided to wash their hands of the whole thing.

The Internists thought it was a bitter pill to swallow,
and the Plastic Surgeons said, "This puts a whole new face on the matter."

The Podiatrists thought it was a step forward,
but the Urologists were pissed off at the whole idea.

The Anesthesiologists thought the idea was a gas,
and the Cardiologists didn't have the heart to say no.

In the end, the Proctologists won out,
leaving the entire decision up to the a**holes in Washington!

Surveys, statistics and statistically significant economic tremors

Once in a while, an article would pop up in the news and make me go, "oh great, here comes another guy who is talking about statistics, but knows nothing about it". This article on the BBC made me feel just like that, but luckily only in the first half: How one woman can cause economic boom or bust. However, having finished reading it, I came to appreciate his point. He is portraying how the world, especially when in crisis like these days, is reacting to 0.1% changes in unemployment rate or deviation from economic forecasts, without fully understanding the data source the conclusions are drawn from, or the statistical significance level it can be trusted to.

The author goes quite the distance to move his reader's emotions, and raise my suspicion:

She (the lady in the fictitious story who just lost her job and by chance was surveyed by the Labour Force Survey) is just one of those surveyed. But Eve, unknowingly, is about to move mountains. She will make economies tremble with a 30-minute interview and a cross in a box on a laptop questionnaire.

Vast sums of money will lurch round the world's financial system. Politicians will reel and businesses be broken.

But then he comes back across the line and is in my good books again:

Check the ONS (Office for National Statistics - UK) and it states clearly that the figure is accurate only to 0.2 per cent, most of the time. This means that a rise of 0.1 per cent in the unemployment rate could be consistent with an actual fall in unemployment across the whole economy of 0.1 per cent.

I like his final point the best, suggesting how people should treat survey results - more like clues, not knee jerk reactions to trigger panics:

... feverish times make attention twitchy. Every piece of evidence about the state of the economy is interpreted, explanations offered, forecasts recalculated, and much is made out of little, perhaps too much.

The difference between a rise and a fall is judged with solemn faces when the truth is the change we observe may not even be there. Economic data is never a set of facts; it is a set of clues, some of which are the red herrings of unavoidable measurement error.

Happy Birthday to ThinkOR.ORG - 2 years old

Happy Birthday to ThinkOR!

We are 2 years old. :)

Feb 10, 2008 was when I first registered and started the blog to promote Operations Research (also because I was looking for any reason not to study for exams). As a newcomer to OR, it bothered me that people did not know what OR was/is. It still bothers me, but a bit less now, knowing that I'm doing something (albeit very little), to try to change that, an article at a time.

I've since got a few more contributors to ThinkOR.ORG (thank you guys!), have met a few fellow OR bloggers (hi! *wave*), and have a small group of regular readers. Every month, hundreds of people all around the world (130 countries to be exact) visit the blog. How can you not love technology?

In return, I am always on the look out for interesting topics to write about to share with you all. Now I'm going to pack my backpack in the most optimal way with the objective of minimising space and weight for my trip to India tonight. I have a hunch that I'm going to have a few interesting posts coming up in the next little while. ;)

Happy blogging!

Bachelor Efficiency.

It seems to be a known fact that confirmed bachelors are at times amazing inventors of time and labor saving methods, gizmos, and procedures. Here is another one.

Recently I was visiting my bachelor friend John at his house and when I was rummaging in his drawers, searching in vain for a spoon, he has proudly shown me his latest labor saving device, (which also explained the lack of spoons in the drawers). He didn’t claim the idea as his own, on contrary; he said it is becoming a trend among their bachelor brethren, but I have seen it for the first time.

He has purchased himself two dishwashers, installed them side by side and is using them alternatively. Filling the one with dirty dishes and taking the clean dishes out of the other. He owns just enough dishes to fill one dishwasher up. This way, when he runs out of dishes, he switches the one full of dirty dishes on and reverses the process. He reports with an extreme satisfaction that he never needs to unload the dishwasher and file the dishes back into the drawers and cupboards. I think there is a lesson here for OR in it.

I’ll call it “The Bipolar Dishwashers Method”.

Healthcare system improvement project management: making a big team work

It's tough chairing meetings, tougher chairing a big meeting (10-15 people), and tougher yet chairing a big meeting that's supposed to last an 8-hour day, one day a week for 6 months. A lot of planning goes into making such a day work with team members varying from the analytical kind to the "feeling" kind, from the surgical kind to the managerial kind. I'm slowly to get a hang of it having done it for a couple months now. The following is a lot of common sense, but if one doesn't have the chance to go through this kind of work with big teams, one may not think it so obvious as an approach. Thought I'd share for whatever it's worth.

• Make sure everyone is doing something - feeling of usefulness in the group, or else people will feel disengaged.



• Assuming natural progress of project is from problem discovery, to analysis, to design and implement, and assuming that everyone in a team needs to participate in all phases, then keep telling self that as soon as we get through to design, things will become more exciting. Analysis phase is not everyone's cup of tea, even though geeks like me find it most interesting.



• Spend the time and create a big poster out of rolling parchment paper. It becomes a live document of all work done on the project to remind team in every meeting of key aims and work accomplished so far. It is a pat on the shoulder for work well done, as well as always showing the direction for the team. Sometimes, one can't see the forest for the trees.



• Big team, big scope - recipe for getting lost or losing sight easily; remind team of aims frequently; relate how current tasks contribute to the aims.



• Identify one lead for each main task to be done in the implementation phase. Give team members enough time to develop own plans on how to implement, and write the document themselves to instill ownership from the start (do not use admin resources to do this). Sometimes it takes 2-3 days just to write and re-write the implementation plans, but the time is worth while, not because we need to have a perfect plan as that is unrealistic, but because it forces people to think of all nitty gritties of how get things done and how they would get around specific change management problems. Provide a good example from a colleague of theirs (real examples from real people = trust), but encourage and give them room to be creative. Then everyone on the team should peer review each other's plan with specific review criteria.



• Once you have all of the above done, engagement level should be pretty high by now, as a healthy amount of sweat and tears will have gone into the implementation plans. I bet anything that you won't be able to hold people back on actioning out those implementation plans.
  

There you have a much happier and motivated team. There is no sure recipe. This isn't one by any means, but it is working for me so far.

CORU Clinical Operational Research Unit - London health care OR team

CORU - Clinical Operational Research Unit, based in UCL (University College of London), is a London health care OR team - the first I've come across working in OR specialising in health care, since I moved across the pond last year from Canada.

Needless to say, I was very happy to meet up with Martin Utley, Director of CORU, last week. Thanks for a great chat, Martin. I'm genuinely excited to link up with the CORU group, as I have not yet met any OR bodies in health in UK yet. Reading up on some publications that Martin sent over - I do miss the academic side of Operational Research.

It was said that OR used to exist quite healthily in UK's health sector before (very close to the Canadian system). After some reform / re-org within the National Health Services (NHS), most of the OR groups within the NHS disappeared (more or less). What a pity.