Tuesday, 7 October 2014

Barrier functions

If you have searched for "Barrier functions" and are interested in one way of optimising a nonlinear function subject to constraints, look away now.  This blog entry is not about that topic, but I could not resist the joke.

Exeter is built on the River Exe - hence its name.  The river is prone to flooding, and just over fifty years ago, there were some disastrous floods which damaged a great deal of property.  As a consequence, flood relief channels were dug parallel to the river, to divert some water - in effect to make the river wider when the river flow peaked.  The Exe is a fairly short river (about 60 miles) and its flow reacts to rainfall quickly, so that a storm in its headwaters leads to flooding at Exeter within 12 to 24 hours.   After more floods in the last few winters, there are plans to deepen the flood relief channels, and work on one site is under way.

That is quite close to our house, and Tina and I have a convenient walk, from our home, down to the river across one bridge, along the footpath that is bordered by the flood channel, across a second bridge and back home.  If we don't stop, it takes 45 minutes, but we often do stop, to look at birds or to talk to friends we meet.  (We call it the "Sunday morning walk" because we used it to give us exercise when we were both working, and we could do it before going to church on Sunday.  When we went trekking in Nepal, we prepared for that journey by repeating the circuit as often as we could.)

The construction site is a large one, and the contractors have had to fence the area to keep out dogs and stray children.  But it must not be impenetrable in case any of these do manage to cross it.  There are no dangerous materials on the site, as they and the equipment are kept in a secure compound a short way away.  The fence acts as a deterrent, and is about 3500 feet long.  So, how would you design a fence at minimal cost for such a site? 

Off the shelf solutions:
  •  Rentable fencing panels;  idea rejected due to cost, aesthetic appeal (nil) and being more than is needed.
  •  Posts and plastic mesh fence; idea rejected due to being insufficient deterrent and lack of aesthetic appeal.
  •  Barbed wire fence; rejected because the footpath is well used by walkers and cyclists and the fence woul be too close to them.
  •  Post and rail fence; insufficient barrier and very expensive

So, the site workers have erected a fence with posts and wire mesh, topped with three strands of strong wire.  The wire mesh reaches from the ground to a height of about 800-900mm, and the parallel strands of wire are about 50mm, 150mm and 250mm above the top of the mesh.  The barrier is almost impenetrable for dogs and children, but an adult could cross - with a little difficulty - if it were necessary to retrieve a dog, a child, etc

I suspect the components are disposable in spite of the waste of material.  The wire mesh is probably a standard size, but someone has had to decide on the design, which is where Operational Research could be of value.  The design has these decision variables:
  • (a) mesh size (from manufacturer's range)
  • (b) mesh shape
  • (c) width of the mesh
  • (d) number of wire strands
  • (e) position of each wire strand
  • (f) separation of posts on straight runs

All of these were probably decided by rules of thumb (aka heuristics) but the sight of the site and its fence made our most recent walk more interesting as we thought about the decisions.

Wednesday, 17 September 2014

I hate mathematics (or, I am proud to be innumerate)

For some reason, many men and women are unashamed when they do not understand mathematics, and cannot cope with day to day mathematics.  As Operational Research is a discipline which uses mathematics as an everyday skill, it can be galling to meet such people.  I came across a book review which eloquently challenged adults with such an attitude to what should be an everyday skill.

For those who persist in blathering that "maths is not my thing", it is high time that they put away such philistine nonsense and allowed the fine and elegant art that exists at the mathematical end of the spectrum of knowledge to entertain and illuminate in ways that complement and give proper balance to the poetry, painting, theatre and theology at the other.

(This comes from a review of the book "Alex through the looking glass: How life reflects numbers and numbers reflect life" by Alex Bellos, reviewed in Third Way magazine by Kester Brewin (vol 37, no 7, p38))

Personally, I would argue against mathematics being at an end of the spectrum of knowledge (which is a bit of a cliché)

Monday, 25 August 2014

Scheduling people and machines - similarities and differences

It is an old adage in O.R. that it is easier to deal with machines than people.  Machines are considered to be more predictable than people.

About ten years ago,  we had a project with a major car manufacturer in the U.K..  It was concerned with scheduling preventive maintenance (PM) on the production line.  Some items had to be maintained every week, others at intervals of two, three, four or more weeks.  Weekly maintenance was easy.  But the other items were more difficult.  If you needed one person-day to maintain items A (2 weeks), B (3 weeks) and C (4 weeks), then in successive weeks you would need:

WeekWork-load (person-days)

However, we were given many more items than three (A, B and C), and the problem of unequal work-load was much more severe.  Our project was concerned with finding ways of changing some of the intervals within a permitted range.  So changing C from 4 weeks to 3 weeks after week 8, and then back to 4 weeks would smooth the work-load. 

But, things were not so simple.  Every so often, an item broke down, and needed repair.  The opportunity might be taken to perform maintenance on other systems while the repair was in progress.  After that, it was put back into service, and its schedule of PM started afresh.  We developed a tool for rescheduling all the PM work when there had been such a repair.  It smoothed out the work-load for the teams doing PM in the factory.  It was a case study that was never published; because the interface used by the PM manager was a spreadsheet, the optimisation used a commercial genetic algorithm, whose details were a trade secret.  So, little could have been written up to describe the process.  And the car company did not want publicity for the interface.

There are circumstances where people need regular hospital appointments, just like the machines needing PM.  Medical check-ups for some conditions need to be scheduled at fixed intervals.  So, one might suppose that the same approach could be used to schedule their visits to the hospital or doctor.  But it isn't as simple.  People are not machines; they have lives besides their need for a check-up.  So, they might be available on Thursday at 2 pm one week, but the following week they have an appointment for lunch and cannot have a check-up before 3pm.  And another week they may be on holiday.  Machines don't have lunch dates, nor go on holiday!  Patients with similar needs, medically, may have different social conditions.  Exeter's hospital draw people from a wide area.  Some of them rely on public transport to come and go, so depend on the local schedule for their part of Devon.   That means that there is an inbuilt priority for those whose transport needs are more limited.  Within reason, the scheduled PM work for any one day does not prioritise jobs and so they could be carried out in any order.

So ... scheduling people in this situation has more complications than for arranging regular work on machines, even though there is an underlying need to smooth the workload in the hospital.  So, in these circumstances, a manual approach sems to work reasonably well.  But - maybe - there is a system which can do some of the work automatically, without degrading the dignity those being scheduled.

I have dental check-ups every nine months, and give blood every three.  The two systems for scheduling the next appointment differ.  At the dentist, the book for future appointments extends for at least a year, and so I can normally find a date and time which is convenient, because very few other people are competing for a visit so far in advance.  So, most of my check-ups are on the same day of the week, starting at the same time in the morning.  Obviously, there is some slack in the dentist's timetable to allow for emergency visits, so the book is never quite filled.  Here a manual system works extremely well.  In contrast, the blood donor sessions do not hold a book open very far in advance.  There  are fewer opportunities to give blood (the dentist is open five days each week, donor sessions are monthly).  Because people are not machines (see above), if a donor can't come to the next session, they book for the earliest one they can after that.  And many (perhaps most) donors prefer an early appointment, because, inevitably, delays in the queues build up and later arrivals spend more time waiting than the earlier ones.  So, one often finds that the early slots at successive sessions have been taken when it comes to booking a three-month visit.  Here is a manual scheduling system with very little slack, and consequently, frustration (which machines do not feel).  Maybe it could be mechanised, but would it be worth it?

And that is the bottom line.  As O.R. people, we can look at problems involving human beings, recognise that there are similarities with problems concerned with "Things", but need to account for and remember that people are not things!

Friday, 22 August 2014

Maintaining a network of roads and paths

How do you manage conflicting objectives?

When I went to Lancaster University to study for my Master's degree in O.R., there was  a cohort of 28 students.  Some of them have made their career in O.R., others used the subject as a stepping stone into management.  Early in the course, we sat a "Jumbo" exam for the first time.  This was a Lancaster speciality; a fabricated case-study, prepared by the staff, and for which we were in the exam room for seven hours with food and drink supplied during the day.  There wasn't much risk of collaboration - partly because we were all striving to tackle the problem as individuals, but also because by the time we broke for lunch together, we had all started to analyse the data and problem and it would be too late to change our planned analysis.  Later on, the exam was extended to eight hours, with the first hour devoted to reading, and not writing or calculating - this was to help those who had come from a non-UK culture, and staff could be asked to clarify any cultural questions.

We were, I believe, the first cohort to sit a "Jumbo" during our first month on the course.  We were part of an experiment to see how we progressed during the year on the course, so our marks did not count, but were used to demonstrate the benefit of the degree programme.  What I remember of that first case-study was that most of us made an incorrect assumption about presenting the results.  Most of us reached the end of the case-study, which concerned water treatment, and tried either to find the best water quality (measured by pollution level) irrespective of cost, or find the least cost treatment which barely satisfied the water quality requirements.  What we should have done, we discovered later, was to help the decision-makers by tabulating several options, of quality versus cost, and then leaving the choice to management.   So we ended up with something like this:

During the following twelve months, we became familiar with such a set of results, either as a table or in a graph, one of the classic forms of showing the Pareto frontier. There is a conflict of objectives - reduce the pollution, and increase the cost.  The Pareto frontier allows one to eliminate dominated solutions.

A few years later, when we needed a mortgage for a house, the advisor asked me to describe what I did in O.R., and I talked about conflicting objectives with such enthusiasm that he complemented me and happily granted us the maximum mortgage that we needed.  (I wish all my hearers had been so enthusiastic!)

There is a research paper in September's issue of the Journal of the Operational Research Society (the UK's leading O.R. journal!) which describes a project with conflicting objectives.  In their paper, "A decision support tool for Public Rights of Way officers based on the Analytic Hierarchy Process", the authors (David John Parsons, Andrew Angus, Martyn Brawn and Joe Morris) describe a widespread problem for local government in the United Kingdom.  How should one look after the network of roads, tracks and paths which are "Rights of Way" - i.e., available for anyone to use.   Some tracks and paths are well used, by riders, dog-walkers, hikers, or simply because they go where people want to go.  Others are very seldom used, possibly because there have been changes in the road layout or because their original purpose no longer exists.  But, legally, the local government has to ensure that Public Rights of Way (PROWs) are maintained, within the budget.

The whole paper makes good reading, especially as I often use Devon's PROWs, and not always the well-used ones.  So I will single out one table as it is concerned with the conflicts involved.

Conceptual framework for the PROW decision tool: attributes influence user preferences, and use generates social and economic outcomes
AttributesUser groupsSocial and economic outcomes
physical characteristicswalkers (travel)community cohesion
structurescyclists (travel)community safety
signagecasual walkersculture and leisure
facilitiesserious walkersenvironmental quality
marketing and promotionsleisure cyclistshealth and social well-being
local relevancehorse riderstransport and access
strategic relevanceusers with impaired mobilityeconomic well-being
social priority groups

The table sums up the range of conflicts involved with maintaining the roads and paths.  As the rest of the paper demonstrates, the simple process of developing a framework is an important first step in helping make decisions.  An old description of O.R. is that it provides "Tools for thinking with" and a summary that started with the table above gave Officers in the local authority some extremely useful tools to think with.

The many outcomes and objectives conflict - if more money is spent on signs for a track used by leisure cyclists, less is available for marketing tracks for serious walkers.   And how do you measure some things on a common scale?  But the tools are there! 

I wish that the decision support tools could be used in other parts of the U.K.!

A decision support tool for Public Rights of Way officers based on the Analytic Hierarchy Process

David John Parsons, Andrew Angus, Martyn Brawn & Joe Morris

Journal of the Operational Research Society (2014) 65, 1387–1395 doi:10.1057/jors.2013.94

Local Government Authorities (LGA) in England and Wales have statutory responsibility for the maintenance of Public Rights of Way (PROW), such as pathways and byways open to non-motorised traffic. The departments responsible have to compete for budgets and justify their expenditure in terms of councils’ priorities, such as well-being and environment. A need was identified for a simple decision support tool to provide a consistent and transparent framework for assessing the range of possible social and economic benefits from expenditure on PROW. The tool uses the Analytic Hierarchy Process to elicit weights forming the links from path attributes to users and usage to benefits, with a final stage to combine the benefits according to LGA priorities. It was successfully tested through case studies, where improving signage was generally found to be the most cost effective option, giving moderate benefits at low cost, whereas improving the physical conditions of the surface gave greater benefits at relatively high cost.

Thursday, 14 August 2014

Hire or buy at a tourist site?

Today Tina and I visited Stonehenge.  The prehistoric stone monument on Salisbury Plain is one of those places which one tends to visit rarely.  We drive past it several times each year, but haven't stopped to visit it for years.  Visits with parents when young - yes - because it is the thing to do - but it is not a place which benefits from frequent return visits from the majority of people who go there.  Still, as one of the leading attractions in the UK outside London and major cities, it managed over 1,200,000 visitors last year.  A new exhibition centre opened last December, and that will be an extra attraction.  We went to meet my brother and wife, to return his two daughters who have been holidaying with us; Stonehenge is midway between our home and theirs.  School holidays meant that we visited Stonehenge on a busy day in August; like most sites, there is seasonal variation in visitor numbers per day.

We enjoyed it; the site is being "re-landscaped" because the main road which ran close to the stones has been closed and is being grassed over so that traffic does not pass quite so close as it used to.  There were crowds of people, and it rained.  But we got in free.

However, in the management of so many visitors, there is scope for some decisions to be aided by O.R..  The visitor centre is 30 minutes walk from the stones, so one either walks, or takes a shuttle.  There were three types of shuttle on site today.  Land trains of three coaches with the Stonehenge logo on the side pulled by a 4x4 vehicle (and presumably, these could run with only two coaches).  Minibuses also with the Stonehenge logo on the side.  And minibuses belonging to local companies.  The first two were obviously dedicated (owned or on lease) to Stonehenge, the third type was hired in.

So here is the problem.  What is the best mix of vehicles to have dedicated to the site?  In peak periods, all will be in use, at some times of the year, some of the fleet will be idle.  And how do you plan the number of local coaches to hire?

So here is an O.R. model waiting  to be built.  There will be a long term plan, to determine the fleet size (and whether to lease or own), and short term strategy depending on the time of year and the weather forecast about how many to hire.

And, for the local sources of minibuses, there will be a further modelling problem.  How many vehicles do they have in their fleets to meet requests from the Stonehenge management?

There are numerous other potential areas of decision-making where O.R. could help at the site.  For instance, how to schedule the tourist coaches?  They need parking space, they need shuttle vehicle space, and their occupants will make bulk arrivals at the cafeteria and shop.   Limiting the time slots for coaches will help smooth the demand.

Friday, 1 August 2014

Why are there so few O.R. case-studies in the literature?

From time to time, when people discovered that I taught a branch of mathematics, they would ask: "Was it pure maths, or applied maths?", no doubt thinking back to school maths lessons when these were the two prominent divisions of maths.  Over the years, my replies to such questions were along the lines of: "Neither, I was teaching applicable maths."  And then I had to explain a little more.  Sometimes, I would add, a little mischievously, that I dealt with interesting maths.  Now, I do not want to run down the applications of pure maths, nor of applied maths, but the applications of the maths of O.R. are often easy to explain, along with my interesting work with industry.  And, part of the interest came from going on site visits to see people in industry or commerce who had problems to which O.R. could contribute.

On one such site visit, my student and I were taken on a walk down the production line.  All was explained to us, and part way along, we were shown one machine.  Our guide proudly told us that it had been invented in the factory, though it had some similarities to machines that can be found in many homes, only it had a capacity 20-30 times more.  Naively, I asked if the company had a patent on it.  The firm answer was that they didn't.  To publish a patent would give away the ideas to a rival, and they needed to keep their developments of equipment confidential.

A few years later, I worked with an international company who had sponsored a postgraduate student.  The company had an internal supervisor for the student, who spent a good deal of time in the head office.  At the end of the project, the thesis was prepared.  The company supervisor asked that the thesis be embargoed from being made public, once again for reasons of commercial confidentiality.  I discussed it within the university, where such matters were well-known, though not very common.  The university guidelines allowed for an embargo to last up to five years.  The company were happy with that.  For, they argued, after five years, the developments in this thesis will be part of our history - we will have moved on, so publication will allow our rivals to see where had been. 

I never saw that project written up in the literature.  First, because it would have been out-of-date when it went into the literature, and second, because there was so much in the work which was particular to the industry, that it would have lacked interest for non-specialists in that industry. 

So that was one case-study which never appeared in the literature, and those were the reasons why.  Maybe the student and I should have tried to find one part of the thesis which could be published without threatening the confidentiality.  In these days of publish-or-perish in academic life, the luxury of supervising such a thesis is less likely to occur. 

And, over the years, talking to practitioners, commercial concerns have often been cited as reasons for not publishing case-studies.

And there are other reasons; time is one - O.R. staff in industry are not paid to write for the literature; promotion is another - an industrial O.R. person will not gain promotion because they have published case-studies on the literature. 

But it would still be nice to see more O.R. case-study material in print.

Wednesday, 23 July 2014

A nation of tea-drinkers

For years, the United Kingdom has been known as a nation of tea-drinkers.  Selling tea and tea-bags is a big business, estimated at half a billion pounds per year.  Until the invention of teabags, tea was made with leaves in a pot.  Teapots were to be found in every household, in all shapes and sizes, and associated with the serving of tea came tea-caddies, tea strainers, tea-cups and so on.  Tea-bags changed some of these habits.  With a tea-bag, a cup of tea can be mad by pouring boiling water onto the bag in a cup or mug, so dispensing with the need for a teapot.  For the company making tea, tea-bags mean that finer leaves can be used.  In our household, we use both leaf tea and tea-bags, but almost always use one of our teapots.  (We have four teapots: one holds enough for two cups, the next holds enough for four or five, the third is slightly larger, and my heirloom Victorian one holds ten or so cups.)

Today several newspapers have reported a story about measurement of tea made with tea-bags, to settle a dispute about "What is better?"  And of course, OR is all about "What is better?"  The story can be read here.  It all followed from an advertisement which included this picture:

(c) Daily Mail
The tea on the left is made with a pyramid-shaped tea-bag, that on the right with a round bag.  The claim is that pyramids are better.  A leading manufacturer of round tea-bags claimed that this was a misleading claim in an advert, so there have been laboratory tests whose results are supporting the claims for the pyramids.  Ultimately, it will be up to the consumer, who will apply an OR technique, cost-benefit analysis.  Is it worth buying more expensive tea-bags or not?  But it is nice to see that in the nation of tea-drinkers, people are prepared to study whether one "cuppa" is better than another.