Dynamic scheduling in the face of uncertainty

Dealing with operational uncertainty is one of the biggest challenges facing many businesses today. The most well thought out plans and schedules rarely survive contact with the real world, and the consequences are often a loss of productivity and overall efficiency. Businesses should be endeavouring to make the best decision at any point in time given the current circumstances and the best information available to them. Operational scheduling, when done right, can allow businesses to make quality, timely decisions, maximising their productivity in the face of uncertainty.

The best laid plans of mice and men often go awry

– Robert Burns

This post will use a bulk cargo railway operation as a running example, but hopefully it will be clear that many of the ideas could equally be applied to other problems and other industries. Bulk cargo railway operations are charged with the efficient movement of bulk cargo (e.g. coal, grain, oil) between locations (often mines and ports) on trains which are sometimes up to 3km long. The problem is made difficult by limited resources, considerable operating uncertainty and complex interacting subsystems. Train drivers, locomotives and rail cars are all expensive to procure and maintain; as a result their numbers are minimized as much as possible.

More significantly in a rail environment, the track itself is often a bottleneck with many networks only having a single track for long distances with passing sidings set up at regular intervals. The domain is also fraught with uncertainty, with activities often having highly variable durations. For example, the loading of lump coal or iron ore into 200+ cars can take from 3 hours to 6 hours on any given day and network operators have limited ability to predict how long a particular load might take. Even excluding the potential for breakdowns and the need for strict safety standards which frequently result in delays to trains while checks are made, the variation in driving styles means there can be significant variation in travel times. Finally, the presence of several interacting, complex systems, including the mining operation and the stockpiling and ship loading at the port (which are all inextricably linked to the rail operation), mean it is difficult to reason over the entire system at once.

Operations like these require massive amounts of planning and scheduling to ensure smooth operations and efficient use of resources. Strategic planning years and decades in advance will consider long term demands and the need for upgrading infrastructure while tactical planning might deal with contracts with customers. Operational scheduling, which is the focus of this article, deals with the day to day running of the network – putting drivers on trains, matching locomotives with car sets, and scheduling services around the network. While being different to the implementation of the schedule (through the setting of train signals for example) an operational schedule is low level and contains sufficient detail to be implemented by train controllers. These operational schedules are crucial to any large scale operation, and the quality of the schedule will have significant impact on operating efficiency.

Traditional Operations Research (OR) addresses operational scheduling in a similar way to strategic and tactical scheduling. A largely static schedule is produced in advance that aims to optimize certain characteristics (in this case throughput). The constantly changing, uncertain environment is handled by building buffers into the schedule as robustness measures so that it remains valid under some expected level of delay and variation. The variable loading time described above, would be dealt with by allocating all services a 6 hour window (or more to allow for an additional buffer) and worst case cross times would be used to ensure they could always be met. The fundamental issue with these static schedules is that they have guaranteed inefficiencies built into them and give no incentive for the organisation to outperform the given schedule. If a particular service is loaded in 3 hours rather than 6, the train will have to wait 3 hours until its scheduled departure time, leaving no net gain. Another issue is the degradation of the schedule when there are variations beyond that catered for in the robustness. If a train is not ready to depart the port at its scheduled time, it is often canceled rather than risking disrupting the entire schedule. This obviously has significant impact, and often means there is a large gap between the theoretical optimality described by the schedule and the actual results achieved.

The fundamental issue with these static schedules is that they have guaranteed inefficiencies built into them

Rather than persisting with a static schedule in the face of new information and changing circumstances, organisations need to be able to respond quickly and appropriately when things don’t go to plan, and maximise efficiency when things do. This responsibility is often given to those implementing the schedule – train controllers in a ‘run when ready’ railway will make decisions around track usage or locomotive assignment based on which train arrives at a crossing first or which locomotive is available. These local decisions can often be short-sighted and cause issues later on and the efficiency of the system is highly dependant on the quality and experience of the decision maker. To support this, significant investment is made in situational awareness systems which provide a wealth of information on the state of operations which can be leveraged by scheduling tools. There is demand for an approach which combines this dynamic, but myopic scheduling with foresight of the implications on longer term efficiency. Dynamic operational scheduling tools can support a ‘best of both worlds’ approach through fast, dynamic schedule production which responds to the changing circumstances while focusing on system wide efficiency.

Dynamic operational scheduling tools can support a ‘best of both worlds’ approach

In the bulk freight railway domain, Biarri has developed tools for dynamically scheduling services to maximize throughput while meeting the strategic and tactical goals of the system. While there is still much uncertainty in the system, the tool is able to respond appropriately to unfavourable circumstances and proactively look for ways to exploit favourable ones. Because the system is able to respond so well to changes, it is able to build less robustness into the schedule as the consequences of not meeting the schedule are much less severe. Rather than assuming a 6 hour load time in the example above, the system can be more optimistic and plan services closer together. If a particular service takes longer than anticipated, the system will reschedule without cancelling services and still achieve quality results. Importantly, if the loading is done within 3 hours, the system will take advantage of this, allowing the train to depart much earlier giving greater throughput.

… the tool is able to respond appropriately to unfavourable circumstances and proactively look for ways to exploit favourable ones

Developing dynamic scheduling tools requires a move away from standard OR techniques such as mixed-integer linear programming (MILP) which can guarantee optimal solutions but take hours to solve. Artificial Intelligence planning techniques excel in domains characterised by frequently changing information, lots of data sources and a short time frame for decision making. Multi-agent planning systems are one such approach which have had much success in supply chain management, military applications and transportation domains. Multi-agent systems are composed of many interacting intelligent software agents which work together to achieve high level goals. The paradigm allows for fast and effective decision making in domains that are difficult or impossible to solve with monolithic approaches. Biarri has applied this approach to different domains with much success, often in cases where traditional approaches had been tried and failed.

 … fast and effective decision making in domains that are difficult or impossible to solve with monolithic approaches

It is worth acknowledging that dynamic operational scheduling is not suited to all organisations or to all types of schedules. For some businesses, providing predictability and certainty is more important than overall efficiency, and using a static schedule can help achieve this. Further, it is not always practical or within the control of the business to change some elements of a schedule at short notice. Passenger train services, for example, have customers who are depending on them to run services as timetabled and would not appreciate trains departing early to improve efficiency! (As an interesting counter-argument London runs one of the best performing bus networks in the world by running most services without timetables).

Dynamic operational scheduling is emerging as an exciting, innovative approach to ensuring businesses maximize their efficiency in chaotic, uncertain environments. Biarri is helping to lead the way by bringing state-of-the-art mathematical approaches to bear in a way that is accessible yet powerful. Start the conversation today!