MISTA 2013
Scheduling teams for aircraft ground maintenance
Giuseppe Lancia · Paolo Serafini
1 Introduction
This talk deals with a real application concerning the scheduling of the maintenance staff of an airport and the described procedures are currently being implemented in a large Italian airport.
The time between the arrival and the departure of an aircraft is usually devoted to some maintenance operations carried out by the airport staff. The operations are requested by the aircraft crew just before the arrival and they are not known in advance.
The operations require different skills and hence the airport staff must have enough workers available with the proper skills to cope with the requests.
The airport staff is organized according to a duty table. On each day each worker may work in the morning shift (M) or in the afternoon shift (A) or in the night shift (N) or he may rest (R). The duty table has rows corresponding to 10 weeks and columns corresponding to the seven days of the week. Each entry in the table is one of the four symbols (M,A,N,R). The table is fixed and cannot be changed. On a given week, each worker has to follow a particular row of the duty table, then he moves to the next row in the next week and so on in a cyclic way, i.e., going to row 1 after completing the last row. The only difference between workers is their starting rows in the duty table.
The decision variables are the starting rows in the duty table for each worker.
Clearly deciding the starting rows greatly affects the availability of workers in a par- ticular shift. The time table of arrivals and departures is known much in advance, and this enables to consider a time horizon for scheduling the staff of six months, but the actual requests are known only at the last minute. Therefore the possible requests must be estimated on a statistical basis.
Giuseppe Lancia University of Udine
E-mail: giuseppe.lancia@uniud.it
Paolo Serafini University of Udine
E-mail: paolo.serafini@uniud.it
We have split the problem into the following three steps: evaluation of the requests;
evaluation of the work force during a shift; decision of the best starting rows.
2 Evaluation of the requests
Each maintenance task requires workers who possess a particular skill and a specific level for that skill. For each skill there are three levels: level 0 (the lowest), corresponds to no particular competence and is possessed by every worker; level 2 (medium), corre- sponds to a good specialization in the specific skill and level 1 (the highest), corresponds to very advanced competence.
For each skill, the request coming from the aircraft crew is one of the following {}, {0}, {1}, {2}, {01}, {02}, {12}, {22}
denoting respectively no request at all (for that skill), one worker of level 0 (hence not associated to any particular skill), one worker of level 1, one worker of level 2, a pair of workers with levels 0 and 2 etc. For each flight and each skill the probabilities of the previous eight outcomes are known. From these probabilities it is not difficult (via generating functions which are just polynomials in this case [2]) to compute the distribution functions
dkhr= Prn
Yhk≤ ro
where Yhk is a random variable which counts how many workers with skill k and level h will be requested during a particular shift. The values dkhrassign the confidence level such that Yhk will have value not larger than r. These values form a discrete set but we interpolate them linearly in order to have a continuous distribution. Therefore at the end of this phase we have available, for each skill and each level, a real value r such that dkhr= 0.95 (having assigned a confidence level of 95%).
3 Evaluation of the work force during a shift
Given a certain set of available workers (each one with his own skill and level) in a specific shift, we want to evaluate if the set meets in a satisfactory way the maintenance requests for that shifts. The requests are summarized by the previous r values that we may label as rj, with j ranging on the pairs skill-level, plus an entry for the 0 level.
We may model the problem with a bipartite graph G = (W, R, E), where W is the set of available workers in the shift and R is the set of requests. The edge set E consists of the pairs (i, j) where the worker i has the skill-level j. To each j ∈ R a real value rj
is associated and to each i ∈ W a real value w is associated (the same for all i ∈ W ).
The value w has to be regarded as the working capacity of a single worker. Normally it should be w = 1. However, it is safe to take into account possible absences from work for various reasons and reduce the value to w = 0.7.
Although the problem deals with integer quantities, like workers and tasks, nonethe- less, due to the uncertainty connected to the task requirement and also to the worker presence, we may disregard the integrality constraints and think of fractional assign- ments of workers to tasks. By-and-large these tasks will not be requested all at the same time and it is conceivable that a worker may devote part of his time to one task and another part to some other task.
Hence we want to find an assignment xij, (i, j) ∈ E, such that X
j∈R
xij≤ w, i ∈ W
and some measure δ(x) of deviation from the values rj, j ∈ R, of x(j) := X
i∈W
xij
is as small as possible. We have chosen the following measure δ(x) := max
j∈Rmax
rj− x(j) ; α (x(j) − rj)
where the surplus is weighted by α. We find the assignment minimizing δ(x) by carrying out a double binary search solving each time a max flow problem ([1]). The optimal value δ∗ is a performance measure of the workers team allocated to a particular shift.
The total number of shifts in the duty table is rather high and therefore we need a fast algorithm to evaluate all shifts for a particular set of starting rows of the workers.
4 Deciding the workers’ starting rows in the duty table
Now we want to find the best starting rows for all workers so that in each shift the possible requests can be met. It is not immediate to understand how moving the starting row of a single worker from one row to another one affects the whole schedule. Hence we may opt for a local search procedure in which a simple move, i.e., moving a single worker to another row, is performed randomly and this new schedule is immediately evaluated according to the previous steps.
5 Conclusions
In the actual implementation the management has available a set of parameters to in- teract with the procedure and to ‘drive’ the solution toward a good value. The essential point is that the core routines must be fast and robust to produce a reliable schedule.
The management seems satisfied with the software.
References
1. R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows. Theory, algorithms and appli- cations, Prentice Hall, New Jersey, 1993.
2. Graham, R.L., D.E. Knuth, O. Patashnik, Concrete mathematics: a foundation for com- puter science, 2 ed., Addison Wesley, Reading, MA, USA, 1994.
