Thursday, 22 December 2011

O.R. and searching the internet

One of my recent blogs was discovered by someone searching the internet with Google.  I can't say that I am proud that their key words included "sex" and "Devon", when I was actually writing about correlation.
It reminds me that the Pagerank algorithm used by Google has some links to graph theory.  Some of the details are public, but there are numerous refinements which are commercial secrets.  But in the context of O.R., there are multiple objectives for any search tool.  The software engineers want the search to be reliable and appropriate, so that users continue to use their tool.  Advertisers want to be highly ranked, and this may not be what the user needs.  Users want speed, so the algorithm may not be quite as thorough as the theoreticians would like.  So there are compromises.  Sometimes the search does not work properly, because there are exceptions to the rules that were assumed. 
Sometimes we find that there are exceptions to our assumptions in O.R.!  Hopefully, we learn from them.

Tuesday, 20 December 2011

Extraordinary scheduling

When I was editing the International Abstracts in O.R., there were numerous research papers dealing with scheduling problems, and I sometimes wondered if some of the more theoretical ones deserved to be published;  in fact one of my colleagues commented that many academic papers about scheduling a job shop were written by authors who had never seen a job shop!  Certainly, I came across many that made assumptions which were most unlikely to occur in practice.  However, the research on theoretical models for scheduling has helped the development of various O.R. techniques, so the work is not in vain.
One of the great pieces of scheduling in engineering history was the conversion of rail  track from broad gauge to standard gauge. In Britain the Great Western Railway (GWR) designed by Brunel, pioneered broad gauge from 1838 with a gauge of 7 ft 0 14 in (2,140 mm), and retained this gauge until 1892.  In one weekend, the majority of the network was converted to standard gauge 4ft 8 1/2in (1435 mm)  Brunel had believed that the broad gauge would give faster, more stable trains.  (Incidentally, on Exeter Quay, there is still a short length of dual gauge track, with three rails, allowing both Brunel's broad gauge and standard gauge trucks to use the quay.  Also, as a matter of trivia, standard gauge is supposed to be the average separation of wheels on carts measured by George Stephenson -- a distance that depends on the need for two horses to be harnessed to the cart.  This is close to the distance between ruts in Roman towns and forts, from 2000 years ago.)
Just imagine the effort needed to co-ordinate the manpower, tools and equipment over hundreds of miles of railway track!  In 21st century Britain, railway engineering is carefully scheduled but there are no feats to compare with what happened that weekend in 1892.

I was reminded of this feat of engineering scheduling when I read about another Brunel-related railway.  He was involved with the engineering of the line from Plymouth to Tavistock.  On that line, there was a spectacular viaduct, the Walkham viaduct.  It was built with stone piers and wooden cantilevers, and was 367 yards long and 132 feet high.  In due course, in 1910 the wooden structure was replaced with iron/steel girders, and according to "The Industrial Archaeology  of Dartmoor" by Helen Harris, it was a proud local boast that the changeover was done so skilfully by the workmen that no trains had to be stopped and the normal service could run all the time.  As I read this, I mused about such scheduling.  It would be very impressive -- there was no theoretical model or research paper about it!  There's no evidence to support that story of careful scheduling that I can find using Google, and I wonder whether the local story is a myth bringing together the conversion to standard gauge and the reconstruction of the viaduct.  The viaduct was demolished in 1965.  A new bridge has been built this year to carry a cycle track that follows the route of the railway line.

Nonetheless, it is a reminder that engineers do scheduling all the time, and their scheduling is authentic. 

Monday, 19 December 2011

The time element in Operational Research (2)

In part 1 of this item, I reflected on problems where there are repetitive decisions at comparatively short time intervals; replacing vehicles is something which happens quite frequently for fleet managers, and production lines need to have regular maintenance.
What happens, though, where there are much longer time gaps between the need to do something?  O.R. can help suggest the frequency of action, but I suspect that the problem is implementation, rather than of the O.R. approach.
At one time, I lectured on the methodology of O.R. to undergraduates, and on conflicting objectives.  The example that I used was one that I had picked up from Devon County Council.  How often should a farmer trim the hedges between their fields and minor roads?  The hedges grow steadily all year round.  You can't cut the hedges at the time when birds are nesting (constraint).  Each cut costs money, so the farmer doesn't want to cut too often.  Equally, if you cut very rarely, then the hedge gets out of control, and needs more attention than simply cutting with a mechanical tool.  There are environmental reasons for not cutting every year.  So there are objectives of cost, aesthetics, environment to consider.  So the decision comes down to a decision of annual cuts, every second year cuts, every third/fourth year cuts.  And it doesn't really matter whether you do it precisely at intervals of 365 days.  The county council's advice is every third year, with some hedges on busier roads being trimmed annually.
That was a decision that could be implemented reasonably easily.
Not so easy to implement was a problem which affects many councils, organisations and individuals.  How often should you give a fresh treatment of wood preservative to items of exterior woodwork?   In my visits to several churches around the county, I found that hardwood gates and some other woodwork were drying out through lack of treatment.  As we have walked on some popular footpaths, Tina and I have noted that seats and benches beside the path are prone to decay through lack of attention.  From our experience with the old gate of our garden, and the wooden furniture on the patio, we know that these items need treatment from time to time -- but because they are in the vicinity of the house, it is easy to monitor them and decide when to do the work, usually every two to four years.  We also have some wooden trellis, supporting climbing plants, which we have decided is not worth treating again, because its cost is small compared with the time it will take to move the plants away from the wall.  Maybe the owners of the gates, seats, benches have decided the same?  And if they have decided to give treatment how does the policy get implemented?  Somebody has to inspect the items, and then arrange the repair and treatment into a worker's schedule.  Because this is a "one-off" item, it disrupts that person's schedule.  So, as it is hard to plan the inspection and treatment, the job doesn't get done, because of the implementation problem.  It requires record keeping, and a job description which lists the whole set of items that need maintenance.
And what prompted my thoughts about this topic at the moment?  A matter of industrial archaeology!  I have been reading about the medieval tin-miners on Dartmoor.  Apparently, it was the practice to smelt the ore in stone buildings on the moor, with stone chimneys and thatched roofs.  These days, it is suggested that thatched roofs be rethatched every 20 years or so.  Owners of thatched houses budget for this.  But on the moor, the weather was so hostile, and the thatching of the buildings was "rough and ready".  So the thatch was burnt when it had worn out, by which time the building needed repairs to the walls as well.  This was a rather drastic form of maintenance, and would seldom be adopted these days.  However, there was a further purpose in the burning of the thatch, as it allowed tin ore to be retrieved from the thatch.  Hence the maintenance cycle was:
Build - about twenty years of decay - burn thatch and rebuild - about twenty years of decay - burn thatch and rebuild -etc
Now the interesting aspect of this is how people learnt the process of reclaiming the ore from the burnt thatch.  It could only happen a few times in the lifetime of any miner or mine manager.  Perhaps rival managers were prepared to share their expertise?
And is this the longest maintenance cycle around?

Thursday, 15 December 2011

The time element in Operational Research (1)

Recently, I have been reflecting on the fact that many O.R. problems are concerned with time, either in the form of "When" or "How long between" questions.  Yet it is easy to minimise this facet of O.R. when we teach it.  Obviously, forecasting models are taught, and so is the methodology of dynamic programming, but many other techniques ignore the effects of time.  (Yes, that is a gross over-simplification.) Simulation models clearly represent time and the passing of time.
I suspect that one factor which contributes to the limited discussion of problems involving time is that we know that things change over time, so we cannot assume the constancy of parameters that so many models are based on.  We teach simple inventory models in terms of "quantity ordered" rather than "Time between orders".  We build linear and integer programming models and assume that the parameters remain constant for a long time.  And if we acknowledge that things change with time, then we are indicating that the models we use are not perfect. And, imperfect models do not make for good academic papers, either.

Some years ago, we worked with an industry which used a number of heavy vehicles.  In those days, each one cost about £100,000, and their fleet size was in the low hundreds.  The normal replacement plan was for each to be replaced after four years , so they were discounted in the company accounts at this rate.  They had negligible value at the end.  The fleet size changed slowly over time, so every year, just about one quarter of the vehicles were replaced.  However, in one year, there had been government tax incentives for buying new plant.  Call that year 1.  As a result, in year 1, nearly half the fleet was replaced.  Some of the vehicles which were in good condition towards the end of year 0, the previous year, had their lives stretched, and some of the vehicles which were due for replacement in year 2 were replaced early.  So there was a blip in the number of vehicles replaced, as seen in the lines below.
Year 0 - 15% of fleet
Year 1 - 45% of fleet
Year 2 -15% of fleet
Year 3 - 25% of fleet

Now what will happen in years 4 to 7?  As the pattern has been to replace every four years, the pattern should repeat for ever.  But what is the effect on the company's profits in those years?  And would that be an acceptable solution?  We sat in with the O.R. team as they considered ways to quickly smooth the blip in the replacements "down-up-down-level" and the blip in profits "up-down a lot-up-level".  The solution was obvious, but needed to be quantified.  It was to retire some vehicles a little early, retire some a little late, but built into that recommendation was the need to inspect more carefully so as to select the vehicles whose lifetimes were not four years.  There were still blips, but they were not so substantial, and after a couple of cycles, would be negligible.

At the time, I was teaching a course which included models of replacement, which assumed that the parameters of the items being replaced, and their number, did not change with time, and so this real-life problem was useful in showing the need to question assumptions, and to think of the wider system being modelled.

More recently, we were involved with an automobile company, whose production line had over 100 workstations.  The equipment at each of these needed to be maintained in a cycle of preventive maintenance. 
We were looking at two problems.  The first, assuming that the production line would continue working at its constant rate for ages and ages, was to smooth the preventive maintenance cycle.  If machine 1 needed to be maintained every 3 weeks, machine 2 every 4 weeks, and machine 3 every 6 weeks, then every 12 weeks, machines 1, 2 and 3 would all need to be maintained at the same time.  And at other moments in time, none of these machines needed maintenance.  (But of course, there were another hundred or so workstations with independent maintenance cycles to consider.)  And sometimes there were situations where the amount of maintenance exceeded the capacity of the maintenance gangs and their equipment.  As the cycles for each machine's maintenance were not as strictly fixed as appears at first, we devised a spreadsheet model which modified some of these cycles so as to smooth the demand on the maintenance people and their equipment.  (For the record, it was a genetic algorithm based heuristic used within the spreadsheet to vary the parameters to make a smooth(ish) schedule.)  One of the complications in the model was the conflict between smoothing different resources, because there were several different types of maintenance equipment whose use had to be smoothed. 
The second problem we looked at responded to a reality that the first one ignored.  In two words, machine breakdown.  The workstations did not always perform without failure.  So if machine 1 broke down after 2 weeks, it would be repaired, and its next preventive maintenance would be due after a further 3 weeks.  The nice, smooth pattern would be disrupted.  So, either a new schedule for the whole line would be needed, or, and this was the solution we advised, when "breakdown maintenance" was needed, then other preventive maintenance should be done while the breakdown was being dealt with, according to rules which followed from the operation of the spreadsheet.  So the second problem gave rise to a model which recognised the time element in O.R. and was able to handle it. 

Tuesday, 13 December 2011

Supermarket O.R. (3) Delivery of orders.

It is that time of year again.  The run up to Christmas, when we are urged to spend, spend, spend.  Monthly sales figures give educators plenty of examples of seasonal variation in time series, and I don't just mean the sales of Christmas trees and decorations.  In the U.K. sales of men's socks peak in the last quarter of the year.
So, naturally, newspapers feature the way that retailers cope with the seasonal demand.  Online shopping is still a mystery to many, so naturally feature writers try to explain what happens in simple terms.  So, the Independent (9 December 2011) wrote about one warehouse as follows:
"But it is at the Ocado warehouse where things get really innovative.  The website allows customers to chose from across the board: virtually every brand imaginable, as well as some of its own and Waitrose's Home brands, are available.  Without the local stores to accommodate a picking system, Ocado's warehouse has taken on an almost cult-like status among customers.
At 30,000 square feet, i is the size of ten film lots and processes the equivalent of 30 supermarket's worth of sales.  There are 15 miles of conveyor belts within the building, which carry the so called delivery "totes" from one station to the next, their paths determined by an intricate series of computers.  The secret is the company's IT system, worked on by some 150 programmers.
At each station, items are picked manually or mechanically; either way, the computers have programmed the bag's journey around the conveyor belts so that, when packed, fragile items will be protected."
Credit where credit is due; yes, there are programmers who write the routines and implement the programs, but behind them are people like O.R. specialists who have devised the rules and logic for optimal routing and packing.  The IT function is not, definitely not, solely where programmers work. 
The article was meant to convey the writer's sense of awe at the building and what is produced there.  But look a little behind, and stand in awe at the O.R. people and systems analysts who devised the logic and rules for the in-house computers.  They will never get recognition outside the company, because what they do and have done, has such commercial value.  Today, I salute you!

Supermarket O.R. (2) Just in time

Every week, BBC Radio 4 broadcasts a programme about the food industry in one guise or another; it is called, without much originality, "The Food Programme".  The most recent broadcast was concerned with the price of food, and why it is increasing.  The interviewees talked about the way that some governments are starting to stockpile food for their citizens (the story of Joseph in Genesis!) and how others are buying land in allied countries to ensure a safe future supply of food, particularly the staples of rice and grain.
One section of the programme was devoted to the U.K. supermarket industry, which the commentators described as the most sophisticated in the world.  In the course of the discussion, an interesting point was made, using the expression "Just in time", which encouraged me to concentrate on what was said, as "Just in time" has emerged from the Management Science/Operational Research/Industrial Engineering stable of work. 
The point was made that the big four supermarkets now run their businesses on the "Just in time" philosophy.  Most supermarket buildings have very little storage space -- the building is largely devoted to sales area.  Therefore, the deliveries are carefully scheduled so that goods can be moved quickly from truck to shelves.  (If you have ever cursed the staff moving large cages of goods around the aisles when you want to shop, it is because this is part of the "Just in time" principle.)  In consequence, each supermarket is extremely dependent on a reliable supply via trucks.  When there are interruptions, then the stock of goods at the supermarket suffers and shelves are empty, customers go elsewhere.  This has been noted in the past, when there have been strikes by delivery drivers.
It is a very good model for operations, but the implication of the programme was that it has a downside.  Operational Research has optimised the system for management, assuming that "Just in time" is the way to run the shops.  But, the time may be coming, when this no longer applies.  And then some -- or all -- of those companies may find that their whole management paradigm must shift, shift to a different way of managing the supply chain and having more space for stocks, which may mean expensive changes to the buildings.  I am afraid that O.R. is not very strong on encouraging such major paradigm shifts, as we generally work within the constraints of the system as it is, not as  it might be.

Supermarket O.R. (1) Changing the service time

I have written elsewhere (http://iaoreditor.blogspot.com/2008/05/introducing-myself-and-or.html) about the example of everyday Operational Research that I use to explain a little about what the subject is about, and where people encounter the "Hidden Science" in day-to-day life.
Supermarket queues -- like all kinds of queues -- demonstrate the interaction of science and mathematics with the psychology of human behaviour, and are therefore a useful reminder that O.R. needs to be put into practice, and that needs psychology.  As some of the best writers about the subject have pointed out, psychology enters in two places; (1) understanding the behaviour of the people in the "system" and (2) understanding the psychology of the managers and people who may implement the O.R. solution.  (The latter gives rise to the maxim: "A manager would rather live with a problem he/she cannot solve than accept a solution he/she does not understand.
David Kendall has given his name to the notation for describing queues succinctly, with later additions, principally by Alec Lee -- hence the Kendall-Lee notation.  Kendall's simpler notation describes a queue according to three aspects, the way that customers arrive, the way in which they are served, and the number of servers.  Write down M/D/2 and any queue modeller will know what is meant (Poisson arrival process, constant service time, 2 servers).  And then, anyone who is trying to implement changes to a queue will know that to reduce congestion, you need to increase the time between arrivals or reduce the variability of the time between arrivals, or reduce the service time, or increase the number of servers.
In the big four supermarkets, the check-outs area designed so that the goods accumulate in a trough where they are packed and the packing and payment must be complete before the next customer can be served.  So service time depends on the time taken to cost the shopping basket and the time for the customer to pack their purchases.  Some will offer "Do you want help with your packing", not out of politeness, but to reduce the service time and hence the congestion.
But in the budget supermarkets, another policy is used.  Customers are deterred from packing at the checkout point.  There is no room for an accumulation of goods.  Instead, there is a dedicated packing shelf away from the checkouts and tills.  Goods are swept from the conveyor belt past the checkout and laser scanner as rapidly and the customer places them into the trolley (urged on by the cashier, or the cashier's behaviour!)  That reduces the service time and hence reduces congestion, or perhaps more subtly, reduces the number of cashiers needed!

Thursday, 8 December 2011

A transportation problem

One of the hard lessons of Operational Research is the definition of the system that is being studied.  If you are taught the subject well, then you learn that there are times when optimising a part of the system degrades the whole of the system.  This may be illustrated with a simple, and silly example.  Optimising the storage cost of an inventory will mean that the amount in stock is minimal; but the economic order quantity formula balances this cost with the cost of supply and procurement, so that a larger stock will be held with consequent reduction in the frequency of placing orders.

On a larger scale, the limits of the system being studied are often too difficult to completely include.  But one needs to be aware of them.

Not so long ago, we drove north and east up the motorway form Exeter and then took a main road to a nearby town that we have rarely visited.  (Up means in the direction of London, at least if you live in Devon.) About 400 metres from the motorway junction, there was a lay-by, filled nose-to-tail with cars, all empty.  When we returned, in the early evening, some of the cars had left.  As we watched, cars stopped in the lay-by, one or more passengers got out, and collected cars which had been parked in the lay-by.  Quite clearly, the lay-by was being used as a transport hub by people who shared cars for commuting.  And, one suspects, it was not designed as such.  We have observed similar use of lay-bys, and patches of waste ground, near other junctions of major roads and motorways.  It is a regular phenomenon at park-and-ride car-parks on the outskirts of UK cities, where a large car-park is provided with a bus service into the centre -- and the car park is also used by those sharing a car.  In some countries, but rarely in Britain, road junctions are actually designed to have provision of parking for car-sharing.   Actually, in Britain, there are some service areas for refreshments and fuel at junctions, and these actually deter long-term parking of this nature. 

Now, an O.R. problem would be to determine the optimum size of such a car-park.  The trouble is, at present, the users pay nothing.  Therefore, in terms of revenue to the provider, there is no incentive to provide the space at all.  But if you are thinking of the larger system, and actually encouraging car-sharing, because it is good for the environment and reduces congestion, then you need the space.  And you hope that someone recognises that it is a good use of public money to offer such space.  Once the system is recognised as being "provide enough space for the people who want to car-share from this hub" you can start to assess the size of the provision, using observation of demand, forecasts of traffic, and perhaps surveys of users and potential users.  Of the three lay-bys that I have observed, all are full during the working day, so must be too small.  And so I wonder where any extra cars are parked if a driver arrives too late to find space in the convenient lay-by?.

O.R., blood and the Olympics

The 2012 Olympic Games will be held in London next summer. Operational Research has played a significant part in the planning, and one company is promoting itself in adverts as the "Logistics provider" for these Games.

Another facet of the Games crossed my desk this week. The magazine distributed to regular blood donors had a two-page article about "how to keep blood supplies running smoothly during the Games". I confess that I had not thought that there might be any connection, but the article identified several aspects of the "supply chain" which might be important. There will be traffic and transport delays around the areas where the Games are taking place, as spectators and competitors add to the congestion (transportation problem). Some supply points (or blood donor centres) will not be usable as a result, so alternative sites have been selected (location problem). The demand will change, so inventories of blood will need to be recalculated, including provision for emergencies (inventory problem). The advertising for donors will be changed during summer 2012 to take account of the normal drop of supplies during the summer, and to encourage donations during the period of the games (allocation of finance problem, selection of advertising media problem).

We mustn't forget that behind all these will be some forecasting models!

Once again, O.R. is the hidden science.