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.