Sunday, 23 November 2014

Hidden statistics and parameters of a harvest

My parents owned a large garden, and with it came several old trees from an orchard.  Among them was a large walnut tree, and my childhood memories include collecting the nuts in September and October, and then leaving them in wooden trays to dry.  Then, over Christmas, my parents, my brother and I would take it in turns with the nut-crackers, breaking the shells and extracting the edible nuts.  I don't know whether Christmas was the optimum time as far as the quality of the nuts was concerned; it was clearly a good time for keeping children quiet!  With hindsight, my father must have selected this time by trial and error.  Like so many decision variables, it is one dimensional - too short a time and the nuts will not be dry, too long and they will have lost their flavour.  A second variable, which wasn't changed, was the ambient temperature of the room where they were stored. 

Commercial nut growers face similar decisions, but on a much larger scale.  The crop will not be uniform in moisture content, so the time from harvest to marketing the edible nuts will depend on the weather at harvest time.  But they will have sophisticated instruments for monitoring the crops; my father only had his eyes and the sense of touch, coupled with the possibility of testing samples at intervals.

All this came to mind as I was dealing with some harvest from my own garden.  We grow climbing French beans, of a variety which is no longer available commercially.  The seeds were given to me by a heritage grower, and the beans they produce are delicious, and freeze well.  So, to maintain a crop, we must keep seed from one year's crop for the next.  At the end of the season, we leave a few bean pods on the vines to ripen, and then collect the pods, take them indoors, dry them, and remove the seeds.  Today was the day for extracting the seeds.  Most of the pods had dried out, but not all, and some had started to grow a mould, other had been so wet when they were collected that they had begun to rot - not ideal.  And not all the seeds are viable.  So, I have a box of seeds to plant in 2015.  And I have faced the same decision with them as my father had with the walnuts - how long to allow them to dry out.  For me, it was about one month.  One day, one week, even two weeks, would not have been enough.  Two months would probably have been too much - the rot could have affected them all.  (One year I made the mistake of leaving the pods to dry near the central heating boiler, and the seeds dried out and were cooked.  Fortunately, I had kept some seed from the previous year.) 

Seed merchants have this problem too - though many plants for seed are grown in warmer, dryer climates than my back garden.  And different plants have different characteristics; just ask a biologist.

So, next time you buy a packet of seeds, stop and think of the statistical and biological research that has meant that your seeds will be viable.  All of that research, hidden behind a colourful picture on the seed packet.

That walnut tree no longer stands.  A few years after we came to Exeter, there was a phone call from my father; "We are all right", he said, "but the walnut tree blew down in the night, and we have no electricity because the tree fell on the cable".  Power was restored after a day or two, and my parents had the tree cut up.  As a reminder, we have a wooden bowl, made by a wood turner using part of the trunk.

Harvesting the nuts led me into trouble at school.  The outer casing of walnuts is a soft green shell, which turns black and oozes a liquid which stains.  As a youngster, I would often collect the nuts, give my hands a cursory wash, and catch the bus to school.  I would arrive with my hands marked with a yellowish stain; since nobody in the family smoked, I didn't know about nicotine stains, but people at school did, and accused me of being a secret smoker.  As collecting walnuts is not in many schoolchldren's experience, nor that of many schoolteachers, my explanations were regarded as a way of disguising my misdemeanours.  The stain did wash away, but walnut skins are still used to produce natural dyes. 

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)
10
21
31
42
50
62
70
82
91
101
110
123

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:
CostQuality
1127
1418
1912
268

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.!

Reference:
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

Abstract
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.