Plane sailing: Modelling can solve bottlenecks in complex work rosters – and cut costs  

A maintenance company whose staff provide day and night coverage for airlines on a complex flight schedule needs to keep its labour costs down without alienating unions yet remain flexible enough to cover for the unexpected. Time to call in an algorithm.

Maintenance companies whose role is to ensure aircraft at busy international hubs are kept in top condition face a logistical task as complex as the arrival and departure board. They must guarantee quality oversight that puts passenger safety first while ensuring they have enough skilled engineers on hand to do the job day and night. It can be a costly exercise because maintenance staff are paid well for their know-how - yet shift patterns negotiated with unions may not be optimizing the workforce and keeping costs down.

Computer modelling developed for a key provider at Brussels Airport aimed to provide feasible – and flexible – maintenance cover that took in the concerns of managers about industrial relations while reducing the company’s labour costs.

This project, explained in the paper “Improving Workforce Scheduling of Aircraft Line Maintenance at Sabena Technics”, demonstrates the potential for optimization programming taking in diverse demand and supply variables to solve complex scheduling problems.

Rostering: A costly conundrum

Skilled labour is among the most significant costs for companies in highly developed countries, and having idle staff on hand is wasteful and expensive. State-of-the-art optimization modelling employing algorithms to identify potential scheduling solutions can be used to address this problem. The research team developed software to search for a work roster that saved money at Sabena Technics, an aircraft maintenance provider operating at six sites in Europe.

Sabena Technics provides a range of services, from pre-flight inspections, transit, daily and weekly checks and on-call assistance to cabin maintenance, engine changes and refurbishment.

The research team got to grips with Sabena Technics’ operations at Brussels Airport where its highly qualified employees service more than 300 flights arriving and departing on a busy weekly schedule.

Staff are organized in teams working a cyclical pattern, and rostering decisions typically require the need to solve complex workforce scheduling problems as each aircraft must be maintained within a given window of opportunity between arrival and departure.

The researchers approached the problem by aiming to introduce “buffers” in staff coverage that  protect against uncertainties that can plague maintenance cover caused, for example, by flight delays, illness or variation in the time it takes to service a particular flight. They developed a model for the winter season in 2008 that identified every promising combination of team sizes and weeks in the roster cycle then took in the concerns of managers in order to tailor the eventual scheduling decisions. 

In those combinations the number of workers was not too large and, hence, costly; not too small to provide adequate cover; and also satisfied strict limitations on weekend working.

Shifts: Cycles and constraints

Every week, Sabena Technics staff maintain the same set of flights at the Brussels hub and, in order to match staff levels to demand, rosters are also organized in weekly cycles. There are four shift types – morning, day, evening and night – that can start and end at different times between cycles.

Demand is not rigidly fixed and Sabena Technics has some flexibility in deciding the exact timing of the maintenance for each flight, albeit within agreed time slots determined by arrivals and departures. Sabena Technics therefore estimates the demand in man-hours, and then constraints built into their practices aim to ensure that the capacity provided by staff on hand exceeds that to make certain there is full coverage while catering for eventualities.

The company’s priority is to match capacity and demand better, and hence minimize labour costs which reflect the number of workers, the lengths of their shifts, the shift types, and whether they are on cheaper day shifts or more expensive later shifts.

The problem of building new rosters is more than just one of pure scheduling and is further complicated by a number of restrictions.

The roster must satisfy agreements with unions on shifts that define starting times, maximum duration, minimum breaks, limits on hours and the number of weekends worked, and minimal rest periods between shifts etc. Moreover, at least half of the weekends must be completely free of shifts - the so-called “weekend bottleneck” that imposes a significant limitation given that demand is highest at the weekend.

To simplify rostering, Sabena Technics prefers to use a limited number of shift definitions determined by their starting and finishing time and, within a cycle, all shifts of a given type must start and finish at the same time. This simplifies the job of the manager drawing up the rosters, who assigns specific flights to teams of workers. In order to avoid paying expensive overtime, this scheduler must be aware of which team is working which shift each day.

Rostering must also accommodate limitations posed by “blocks” - a sequence of shifts without a day off. Shifts within a block need to be of the same type (eg all morning or evening shifts) and staff prefer to work no less than five and no more than eight shifts in a row.

Programme: Algorithmic approach

The researchers proceeded on the basis that an acceptable solution taking in most of these constraints could be found while leaving the scheduler some leeway. They adopted a mixed-integer programming (MIP) approach that enabled them to expand the scope of useful solutions in order to yield a number of cost-efficient potential schedules.

In a first phase, the management team selected a number of these based on their cost and visualization patterns that depicted them on screen against demand. The scheduler then fine-tuned the selected rosters by addressing limitations such as those relating to blocks of shifts.

The algorithm explored a restricted set of combinations of cycles, staff sizes, and team sizes and, to save computation time, was adjusted to account for the weekend bottleneck and to offer the scheduler some leeway.

It returned over 50 feasible options, all within 5% of the best possible solution in theory, and managers analyzed the least-cost choices then put these to staff before changes were taken in.

The model was flexible enough to incorporate a number of concerns:

• Capacity “buffer”: to ensure that Sabena Technics could avoid potential disruption to the roster caused by an unexpected change, such as worker illness, the model built in surplus capacity to guarantee maintenance demands were exceeded by at least 15% at all times.
  
  
• Time “buffer”: as maintenance was often planned immediately after a flight’s arrival meaning that, in the event of a delay, it could not be performed and could cause knock-on disruption to schedules, this was changed to start a fixed time after arrival and the rosters were organized to ensure at least one team was on standby to cater for disrupted flights.
  
  
• Hidden maintenance: maintenance must be avoided immediately before a flight’s departure because passengers waiting at the gate don’t like to see this being done, and so the model was adapted to take this into account.
  
  
• Shift transition and work transfer: teams that finish their shift need to transfer work in hand to incoming teams, losing the first and the last quarter-hour of each shift. The model was adjusted to accommodate these unproductive periods, which were also used as an extra time buffer to protect against the late arrival of staff.
  
  
• Service contracts: key Sabena Technics clients had negotiated contracts in which at least two maintenance employees had to be present, and so the model was adapted to take this into account. As the model demonstrated how this pushed up costs, it prompted the company to take another look at these contracts.
  
  
• Work pressure and shift successions: some of the cheapest proposed rosters that would have increased the staff’s workload dramatically were not accepted by managers because they foresaw problems with the unions. Yet other rosters proposed less desirable shift patterns that, for example, did not ensure a day off between different shift types. If employees are dissatisfied, the quality of their work can suffer and this poses a potential safety issue for an aircraft maintenance company. An effort to adapt the model in order to address this by ensuring that, within a roster, the number of shifts of each shift type was constant on each day of the week proved too expensive.
  
  
• Average number of work hours: some of the rosters generated by the model included a cycle in which the employees were scheduled to work for less than 20 hours in a 38-hour working week. In principle, they could have been transferred for the remainder of their week to other departments but there is sometimes a lack of demand elsewhere and it is often difficult to divide up remaining hours into eight- or nine-hour shifts for this purpose. Managers resolved this by setting a minimum of 36 hours for the number of working hours wherever this occurred, using the remaining two hours for training.
  
  
• Night cycle: the model was adapted to ensure a better balance for workers between blocks of day and night shifts.
  
  
• Weekend constraint: different scenarios for weekend working – with the proviso that one out of two weekends must be free of any shift - were examined in an effort to cut their cost. To address high demand at weekends, introducing an extra weekend cycle was proposed in which staff worked fewer hours and benefited from a longer block of free days before their next cycle. These rosters would have been cheaper than those without a weekend cycle, but were rejected after negotiations with the unions.

Implications: Balancing cost and quality

The Sabena Technics exercise illustrates how an optimization program of this kind can help generate different rostering scenarios and then adapt them rapidly enough to form the basis of a rolling negotiation process between managers and labour representatives.

It demonstrates how software using an algorithm can be employed successfully in conjunction with an adaptive consultation to quantify the trade-offs between cost and quality.

The first results returned rosters that offered labour cost savings of an impressive 40 per cent, but after feedback from staff these were not accepted by managers. The model was subsequently adapted seven times to take in nine major concerns that were raised - and the working schedule that was finally agreed reduced costs by 6 per cent.

Related academic article