Introduction

The general rostering problem is how to assign working days and rest days to employees so that the predicted workload is met, taking into account the constraints deriving from the type of work and the preferences of workers. This is a long-standing problem, and one that has many variants. In smaller firms rostering problems can be solved overall by formulating a mixed integer model. However, when the planning period is long and the number of workers are more, the optimization problem may have a great many constraints and may become too big. As indicated by Eveborn and Rönnqvist (2004), in these cases the integer problems are considered as NP-complete, and in general are very hard to solve.

Many industrial and public service firms work a great many hours per day 7 days a week all year round. In such cases work is typically split into morning, evening and night shifts and working days are allocated week by week on a rotating basis. To that end, an ordered set of weekly patterns is designed that includes rest days, which are assigned to workers consecutively. In other words, what is known as a 'rotating schedule' must be drawn up. How work is organized varies greatly depending on the activity and philosophy of each firm. In particular, it depends on whether the workload varies from one day to another during the week, or on a seasonal basis, on whether the workforce is fixed or casual employees can be hired, for example to cover vacations, and on whether all employees are on a rotary schedule or some are assigned permanently to certain shifts or rest days, etc.

Shift work is always uncomfortable and a nuisance. It can prove stressful and may affect the social and family lives of workers (Scott, 1991). In some organizations shift work is one of the basic causes of discontentment and complaints among workers. A well-designed system of alternating shifts and spacing out free weekends to ensure that work is distributed fairly (a hard problem to solve) therefore often becomes a central issue in the negotiation of collective agreements. As Laporte (1999) indicates, this makes designing good schedules more of an art than a science.

A wide variety of rotating schedules exists. Esclapés (2000) provides an overview and an extensive bibliography on rostering problems. Laporte (1999) centres on rotating schedules. The paper by Ernst et al (2004) presents a review of staff schedulling and rostering. However, although basic principles and some rules exist to govern the design of these schedules, in practice each situation has its own specific problems that must be solved. See for instance Azmat et al (2004), Beaumont (1997), Caprara et al (1997), Caprara et al (1998), Caprara et al (1999), Ernst et al (2000), Isken (2004), Muslija et al (2002), Randhawa and Sitompul (1993), Tharmmaphornphilas and Norman (2004) and Townsend (1988). Laporte and Pesant (2004) give a classification of the main constraints governing the design of multishift rotating schedules and develop a new algorithm that can cover a wide variety of constraints. Their extensive bibliography lists articles featuring case studies that involve the different types of constraint.

In this article, we present an applied study commissioned by Metro Bilbao with a view to improving the rotating allocation of work to drivers and making it more egalitarian. The procedure outlined here is now being applied by the firm to the rest of its shift-workers. The authors are currently conducting a similar study using the same methods and analogous constraints for implementation at the passenger rail company Eusko Tren.

The problem posed by Metro Bilbao is the annual assignation of working days and rest days to its drivers. Drivers have no hierarchical structure: they all do the same job. Drivers' work is divided into morning, evening and night shifts of similar duration, and varies according to the days of the week and the time of the year. Weekends (Saturdays and Sundays) are not treated as different from the rest of the days of the week. The number of drivers employed is calculated to cover all working days, rest days, vacations and reserve days throughout the year. Each driver has certain days that we call 'reserve days' assigned along with working days. These days are intended to cover absenteeism or to allow for special tasks and additional duties originating from major sports events, concerts, fairs, the Aste Nagusia Festival Week, etc. The workforce is fixed in number, and we are not seeking to determine the minimum number of drivers required to cover the workload under given conditions.

Working conditions are agreed between the firm and the representatives of the workers, and are covered in the constraints described below. Work must of course be distributed equitably so that at the end of the year all drivers have worked approximately the same number of morning, evening and night shifts and had the same number of weekends off. Working days must be assigned to drivers on a semi-rotating basis. On the one hand we assign drivers' reserve days, which are grouped by weeks (maximization problem 1). These should preferably be attached to vacations, which are set at the start of the year in different weeks for each driver. The work scheduled is then allocated on a rotating basis to those drivers not on reserve duty or vacation. To do this we must construct a rotating schedule for each period of the year. The length of each rotating schedule should match the number of drivers with work scheduled. Owing to the scale of the problem, we divide this process into two parts: first we select the patterns to cover the full workload for 1 week (maximization problem 2), and secondly we order them so that the same driver can work them consecutively (ordering problem 3). Finally, in the annual assignation of weekly patterns to drivers (problem 4) we use the breaks in rotation due to reserve weeks and vacations to try to ensure that all drivers work the same number of days, morning, evening and night shifts and weekends.

The resulting problems are solved using commercial software, for example the LINGO package by Lindo Systems Inc. (2003). The solution obtained is quasi-optimal in the sense that all drivers work practically the same number of days and are assigned a similar number of morning, evening and night shifts and working weekends. This is an applied study, so there are many different constraints arising from agreements between the firm and its employees, including restraints from all the main families described by Laporte and Pesant (2004). The main contribution of this paper is its method for combining semi-rotating allocation with a planning time frame divided into five periods of three different types with a workload distributed in a nonuniform fashion over the days of the week, and with constraints agreed with employees to obtain an egalitarian solution.

Problem posed

Metro Bilbao drivers are grouped into four different 'residences'. Working days at each are allocated independently of the others. The criteria applied must of course be the same in all four cases. For the sake of simplicity in this article we will deal only with 'Residence A', the largest of these 'residences' at 64 drivers.

Working days are assigned according to the general principles described in the introduction. The following assignation conditions must also be met:

1. Drivers may only do one working day per calendar day.
2. Drivers must have two or three rest days per calendar week.
3. Drivers may not work more than seven consecutive days.
4. Except when on vacation, drivers may not have more than five consecutive rest days.
5. Drivers may not work or rest for single days.
6. Attempts will be made to ensure that no driver works more than two consecutive weekends, with a 'weekend off' being understood to mean resting on Saturday and Sunday or Sunday and Monday.
7. On two consecutive working days a driver may switch from morning shift to evening or night shift, and from evening shift to night shift, but not from evening shift to morning shift or from night shift to morning shift or evening shift, as drivers must have at least twelve hours' rest between two working days.
8. Shift changes on consecutive working days will take place in such a way that no driver works one single morning shift or evening shift.
9. Night shift periods must be separated by four or five weeks in which no nights are worked.
10. Each driver should insofar as possible work the same number of days per year and the same number of morning, evening and night shifts. Each driver must also alternate between mornings and evenings.
11. Drivers' vacations are set on a rotating basis at the start of the year in different weeks for each driver. Each driver has 8 weeks' vacation: 3 consecutive weeks in summer and 5 consecutive weeks in winter. See Table 1.
12. Reserve days are grouped in whole weeks, which must insofar as possible be the weeks preceding or immediately following vacations.

Table 1 - Vacations.

Full table

The year is divided into five periods of three types—winter, summer and August—in which demand and therefore services differ considerably. The number of working days for Group A in each period is shown in Tables 2, 3 and 4.

Table 2 - Working days in winter.

Full table

Table 3 - Working days in summer.

Full table

Table 4 - Working days in August.

Full table

Since the year is divided into different periods and vacations and reserve days are allocated by calendar weeks, we organize rostering also by calendar weeks.

General notation. Parameters and subscripts

The number of weeks in the planning time horizon is denoted by b. Weeks are denoted by l, where lB={1, 2, ..., b}. The year is divided into five periods of three types: Winter-1, Summer-1, August, Summer-2 and Winter-2. The sets of weeks in each period are denoted by B_WF, B_SF, B_A, B_SL and B_WL, respectively. The cardinals of these sets are denoted by b_WF, b_SF, b_A, b_SL and b_WL. Winter weeks are B_W=B_WFB_WL and summer weeks are B_S=B_SFB_SL.

The number of drivers is a. Drivers are indexed by I={1, 2, ..., a}. Since the workload varies according to the time of year, so does the number of drivers scheduled to work. In winter the number is a_W, in summer a_S and in August a_A. These parameters define the sets of indices I_W={1, 2, ..., a_W}, I_S={1, 2, ..., a_S} and I_A={1, 2, ..., a_A}. The total number of drivers, the number of drivers scheduled to work in each period of the year and the number of weeks' vacation per driver determine the number f or f+1 of weeks of reserve duty per driver. In the case of Metro Bilbao we have: b=52, B_WF={1, ..., 26}, B_SF={27, ..., 30}, B_A={31, ..., 34}, B_SL={35, 36}, B_WL={37, ..., 52}, a=64, a_W=47, a_S=43, a_A=30 and f=7.

Vacations are arranged before working days are assigned, in different weeks for each driver (see Table 1). They are given by the values h_i,l, iI and lB, so that h_i,l=1 if driver i is on vacation in week l, and h_i,l=0 if that driver is not on vacation.

Assignment of reserve duty weeks (maximization problem 1)

Variables

x_i,l, iI and lB, (binary) is 1 if the worker is on reserve duty in week l, and 0 otherwise.

Constraints

Remember that h_i,l, iI and lB, (binary) are preset by the drivers' vacation schedule.

Constraint (1) expresses that if a driver is on vacation he/she cannot be on reserve duty. Constraints (2), (3) and (4) express that the number of drivers on reserve duty per week in each period of the year is the total number of drivers minus those scheduled for work and those on vacation. Constraint (5) implies that the number of weeks of reserve duty per driver is f or f+1. Constraint (6) implies that no driver can have more than three consecutive weeks of reserve duty. Constraints (7) and (8) imply that except for the first week, no driver can have a single week of reserve duty between 2 weeks in which he/she is not on vacation. Constraints (9) and (10) imply that for each driver all stretches of scheduled work must contain at least 3 weeks. Constraint (11) expresses that all drivers must have reserve duty weeks immediately preceding or following vacations at least twice.

The objective function:
Insofar as is possible, reserve weeks must immediately precede or follow vacations. The objective function is

In this expression the first terms correspond to the weeks preceding vacations (h_i,l+2=0; h_i,l+3=1) and the second ones to those following them (h_i,l=1; h_i,l+1=0).

Patterns covering workload (maximization problem 2)

We shall design our rotating schedules in two steps. In step one we shall draw up a set of as many weekly patterns as there are drivers scheduled to work, so that a week's workload is covered. We shall do this using a catalogue of patterns considered as acceptable by the company management and the workers. In step two, we shall order these patterns so that the same driver can perform them consecutively. The number of rotating schedules to be designed will be the same as the number of periods in the year. For the sake of clarity we shall look only at winter time here.

Parameters: catalogue of multishift patterns, workload

The days of the week are denoted by j with jJ={1, 2, ..., 7}. We select a catalogue of weekly patterns. These patterns are denoted by P_m, where mM={1, 2, ..., }. The catalogue of patterns is defined by giving c_m,j, mM and jJ, where c_m,j is 0, 1, 2 or 3 depending on whether day j of pattern P_m is a rest day, morning shift, evening shift or night shift. In selecting the weekly patterns we must bear in mind the conditions of the problem posed. In our case we select a catalogue of 39 multishift patterns with two or three rest days that meets conditions 2, 5, 7 and 8.

Workload is understood to mean the number of morning, evening and night shifts that must be worked on each day of the week. The workloads for winter, summer and August are shown in Tables 2, 3 and 4, respectively. Let us concentrate on winter. The workload is stored using the integer numbers e_j,k, jJ and kK={1, 2, 3}, where e_j,k is the number of shifts of type k, with kK={1, 2, 3} (morning, evening or night) to be worked on weekday j.

Variables

y_m, mM, (integer number) where y_m is the number of times that pattern P_m from the catalogue is taken.

Constraints

Constraint (13) implies that each driver scheduled to work must have a weekly pattern assigned to him/her. Constraint (14) implies that the patterns taken must cover the full workload. Constraint (15) limits the number of patterns of the same type. This constraint is not essential: it was introduced at the suggestion of Metro Bilbao to minimize or limit the number of certain inconvenient patterns. In our case we take =5.

The objective function

From all the possible combinations we seek to select those with the most attractive patterns. To that end each pattern P_m is assigned a weight q_m, according to the preferences of drivers.

The objective function is

In the case of Metro Bilbao the solution is y_m=0, except y₂=5, y₈=5, y₁₆=3, y₁₉=1, y₂₁=3, y₂₃=4, y₂₄=5, y₂₈=5, y₃₀=4, y₃₁=5, y₃₂=1, y₃₃=3, y₃₅=3.

Rotating schedule (ordering problem 3)

Now let us order the set of multishift patterns obtained as the solution to problem 2.

Parameters

Owing to conditions 3–12 of the problem posed, after a driver has worked pattern P_m he/she may or may not work P_n. This is shown by d_m,n, m, nM, which is assigned a value of 1 if a driver can work pattern P_n after working pattern P_m, and 0 otherwise.

We denote by g_m the number of morning shifts of pattern P_m and by t the total number of morning shifts in a week (in winter).

Variables

z_r,m, r=1, 2, ..., a_W+1 and mM, (binary) is 1 if pattern P_m occupies position r, and 0 otherwise.

Constraints

Constraint (17) makes the rotating schedule cyclical. After the last pattern we revert to the first. Constraints (18) and (19) imply that only one pattern can be placed in each position, and that all the patterns obtained in the previous problem must be present. Constraint (20) implies that a pattern can only be followed by one of those permitted under the conditions of the problem. P_m patterns with Sunday as a working day are characterized by c_m,70. Equation (21) says that for 4 consecutive weeks there will be one or two patterns with Sunday workdays. Patterns with night shifts are characterized by having c_m,5=3 or c_m,6=3. Constraint (22) implies that for 5 consecutive weeks there will be a single working night. Constraint (23) sets lower bounds on the number of morning shift days over 5 consecutive weeks.

Annual assignment of work patterns (assignment problem 4)

Once the reserve duty weeks are assigned, we move on to assign weekly work rosters with the rotating schedules we have designed. Here we describe only the assignation for weeks b_WF in the Winter-1 period. To that end we construct a matrix with dimensions a b_WF in which the rows are drivers and the columns are weeks. In each column there will be a-a_W weeks with the vacations and reserve duty assigned. We use the break in rotation caused by the weeks of reserve duty or vacations to limit the number of repeated patterns per driver.

Let us denote by F_s, sI_W, the multi-shift patterns of the rotating schedule.

Variables

u_i,l,s, iI, lB_WF, sI_W, (binary) is 1 if pattern F_s is assigned to driver i in week l, and 0 otherwise.

Constraints

Recall that h_i,l, iI and lB, (binary) are fixed (they are vacations) and that x_i,l, iI and lB, (binary) are not variables (they are the reserve weeks obtained in problem 1).

At the end of Winter-1 we move on to Summer-1, which begins in week b_WF+1 of the year. We start by assigning this first week in a way compatible with the last week in Winter-1. Then we continue with the rest of Summer-1, following the same procedure described for Winter-1. The problem to solve is: find u_i,l,s, iI, lB_SF, sI_S, (binary) so that restrictions (25), (26), (27), (28) and (29) are met, replacing B_WF by B_SF, I_W by I_S and a_W by a_S, and

This constraint implies that a pattern of the last week in Winter-1 can only be followed by one of those permitted under the conditions of the problem. Once Summer-1 is assigned, we move on to August, then to Summer-2 and finally to Winter-2.

Constraint (24) assigns the first week from top to bottom maintaining the order of the rotating schedule, starting with pattern F₁. Constraint (25) implies that patterns must be assigned only when drivers are not on reserve duty or vacation. Constraints (26) and (27) imply that each driver can be assigned only one pattern in each week, and that a pattern can be assigned only to one driver in each week. Constraint (28) implies that assignment is carried out in increasing order towards the right. Constraint (29) implies that after the last pattern the first must be assigned.

Finally, we introduce the constraints required for the work assigned to each driver to be similar, that is for each driver to work a similar number of days and morning, evening and night shifts.

Denoted by _W,s the number of days of work, by _W,s^m the number of morning shifts, and by _W,sⁿ the number of night shifts, all in pattern F_s in winter. Likewise, denote by _S,s, _S,s^m, _S,sⁿ, _A,s, _A,s^m, _A,sⁿ the numbers of working days, morning shifts and night shifts for the summer and August patterns. These numbers are easy to define, as all the patterns belong to the same catalogue. Each reserve week is valued at 5 working days.

The constraints that imply equality in work for the full year are

Conclusions

The main goal of this study is to develop a practical model for the annual assignation of shifts and rest days to drivers at Metro Bilbao. We have done this by setting up a specific, semi-rotating model comprising four types of integer programming problem. The model is semi-rotating because there are two types of work: reserve duty and scheduled work. Reserve days are grouped into weeks that, insofar as is possible, must be attached to vacation periods. Scheduled work is assigned via multishift rotating schedules. These schedules are long, which makes them difficult to construct. We have broken them down into two phases: first we obtain the necessary multishift patterns and then we order them. Finally, the number of repeated patterns per driver is limited in the assignation of weekly patterns.

All four types of problem for the case of Metro Bilbao are solved using Lingo commercial software on a PC with a Pentium IV processor running at 2.26 MHz. In maximization problem 1 there are 2880 binary variables, 12 479 constraints and 49 878 nonzero elements. The CPU time required to solve it is 200 s. The objective function value is 412, so there are only 52 reserve weeks not attached to vacation periods. Maximization problem 2 is smaller and simpler to solve. The most complicated ordering problem 3 proved to be that for the summer. It has 2111 binary variables, 2004 constraints and 46 571 nonzero elements. The CPU time required to solve it is 50 s. Assignment problem 4 has 86 000 binary variables, 88 206 restrictions and 12 08 156 nonzero elements. The CPU time required to resolve it is 6 min. It must be pointed out that the whole process of annual assignation up to the presentation of results in user-friendly form takes around 12 min in real time.

With a view to practical implementation, numerous trials were conducted, with special emphasis on the upper and lower extremes of constraints (31), (32) and (33) until an acceptable balance of equality was achieved between the number of working days, the number of morning, evening and night shifts and the number of weekends worked per driver. Thus, the solution presented is quasi-optimal under the equity criteria and is accepted by both the firm and the representatives of its employees. Reserve days are not assigned to morning or evening shifts, so they can be used a posteriori to increase equality in shift types. Since the number of weekends worked by each driver is similar—between 13 and 17—no restriction analogous to (31), (32) and (33) is included for weekends worked.

As a reference, it should be pointed out that if the problem is solved without constraints (32) and (33) on morning and night shifts, we can be stricter in constraint (31), replacing 203 by 204 and 207 by 206. This gives a solution in which the number of days worked by each driver is between 204 and 206 (the average is 205.25). In this solution there are between 71 and 85 morning days per driver and between 2 and 8 night shift days. Of course, requiring a little less equality in the number of days improves equality in then number of mornings, evenings and nights worked. It must be stressed that to obtain this similarity in work it is essential to seek a balance of weekly patterns as done in problem 3.

In conclusion the results, the adaptability to new requirements and the figures for computation time obtained are all fully satisfactory to the company. The workers wanted first and foremost to be involved in the process. The procedure has been agreed with them and the results accepted, since this system is much fairer and better distributed than the previous system at Metro Bilbao. Metro Bilbao has therefore decided to implement this system as an operational model, and extend it to other groups of shift-workers. The authors are currently conducting a similar study using the same procedure and similar constraints with a view to its implementation at the passenger rail company Eusko Tren.

References

1. Azmat CS, Hürlimann T and Widmer M (2004). Mixed integer programming to schedule a single-shift workforce under annualized hours. Ann Opns Res 128: 199–215. | Article |
2. Beaumont N (1997). Using mixed integer programming to design employee rosters. J Opl Res Soc 48: 585–590. | Article |
3. Caprara A et al (1997). Algorithms for railway crew management. Math Program 79: 125–141. | Article |
4. Caprara A, Toth P, Vigo D and Fischetti M (1998). Modeling and solving the crew rostering problem. Opns Res 46: 820–830.
5. Caprara A et al (1999). Solution of Large-scale Railway Crew Planning Problems: The Italian Experience. Lecture Notes in Economics and Mathematical Systems, Vol. 471. Springer-Verlag: Berlin.
6. Ernst A et al (2000). Rail crew scheduling and rostering: Optimisation algorithms. In: Voss S and Daduna JR (eds). Computer Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems. Vol. 505. Springer-Verlag, Berlin, pp 53–72.
7. Ernst A, Jiang H, Krishnamoorthy M and Sier D (2004). Staff scheduling and rostering: A review of applications, methods and models. Eur J Opl Res 153: 3–27. | Article |
8. Esclapés C (2000). Asignación de conductores a jornadas de trabajo en empresas de transporte colectivo. PhD thesis, Universitat Politécnica de Catalunya, Spain.
9. Eveborn P and Rönnqvist M (2004). Scheduler—A system for staff planning. Ann Opns Res 128: 21–45. | Article |
10. Isken MW (2004). An implicit tour scheduling model with applications in healthcare. Ann Opns Res 128: 91–109. | Article |
11. Laporte G (1999). The art and science of designing rotating schedules. J Opl Res Soc 50: 1011–1017.
12. Laporte G and Pesant G (2004). A general multi-shift scheduling system. J Opl Res Soc 55: 1208–1217. | Article |
13. Lindo Systems Inc (2003). Lingo User's Guide. Chicago.
14. Muslija N, Gärtner J and Slany W (2002). Efficient generation of rotating workforce schedules. Disc Appl Math 118: 85–98. | Article |
15. Randhawa SU and Sitompul D (1993). A heuristic-based computerized nurse scheduling system. Comput Opns Res 20: 837–844. | Article |
16. Scott AJ (ed) (1991). Shiftwork: Occupational Medicine State of the Art Reviews, 5. Hanley and Belfus Inc.: Philadelphia.
17. Tharmmaphornphilas W and Norman BA (2004). A quantitative method for determining proper job rotation intervals. Ann Opns Res 128: 251–266. | Article |
18. Townsend W (1988). An approach to bus-crew roster design in London regional transport. J Opl Res Soc 6: 543–550.

Acknowledgements

We thank José Miguel Ortega for suggesting this problem to us and Juan Carlos Mendoza and Fernando Quintanilla, all of Metro Bilbao, for their help in resolving it. We also thank the anonymous referees for their useful comments, which have greatly improved the paper. This study was carried out with the cooperation of Fundación Euskoiker.