|
Article Excerpt
1. Introduction
Staff scheduling problems arise in several application fields, such as public services, hospitals, call centers, and industry in general, and typically fall into three classes: days off scheduling, shift scheduling, and tour scheduling.
Days off scheduling comprises the problem of assigning work and nonwork days for employees over a weekly or longer planning horizon. The pattern of the nonwork days (days off) in the working period is highly related to staff satisfaction; typically, days off on Saturdays or Sundays are preferred; consecutive days off are also preferred. Another important requirement in the solution of this class of problems is the balancedness of the assignment of days off among all staff members. The number of days off per week and their position is defined by the specific work agreement under consideration; most frequent is the case where the number of days off in a week is constrained to be equal to two. Instances of such problems have been studied, among others, by Brownell and Lowerre (1976), Bartholdi III et al. (1980), and Brusco and Jacobs (1993). Other cases are characterized by a larger number of days off to be matched over a period longer than one week, or by softer constraints.
The second class, shift scheduling, covers problems where the work shifts over a working day must be defined and selected. Here variables such as shift starting and ending times, duration and number of breaks, and constraints on the minimum staff requirements for a working day are considered. One of the first papers on this class of problems is Dantzig (1954). Since then, such problems have been extensively addressed, using two different types of formulations: set covering formulations with variables representing feasible shifts, where a solution is a subset of shifts covering the requirements in each basic period of the day (see Aykin 1996); and formulations with variables representing each basic part of a shift, where the complete shifts are found by considering a composition that covers the staff requirements for the whole day (also referred as implicit models; see Segal 1974, Bechtold and Jacobs 1990, and Thompson 1995). Other works considering both modeling approaches are Baker (1976), and Bechtold and Jacobs (1996).
The third class of problems, tour scheduling, is a generalization of the previous ones over a weekly or longer planning horizon. The general case considers different work shifts and days off and has been studied in different works. Mabert and Watts (1981), Bechtold et al. (1991), Easton and Rossin (1991), Bechtold and Brusco (1994), and Brusco and Jacobs (1998) propose some heuristics.
Staff scheduling problems are usually difficult to solve; for example, see Bartholdi III (1981) for a proof of NP-completeness of the cyclic staff scheduling problem. Integer programming (IP) formulations solved by standard optimization tools have been adopted in early works, where they have proved successful only for small problems (Miller et al. 1976, Bartholdi III et al. 1980). For large problems, it becomes nearly impossible to explicitly represent all the assignments of staff to shifts with binary variables, and therefore column generation approaches have been proposed (e.g., Jaumard et al. 1998).
In this paper we address a staff scheduling problem that belongs to the third class, where work shifts in a given set are to be assigned to cover the daily demand for each shift in the set, and a fixed number (two) of days off per week must be assigned to each worker. The interest toward this type of staff scheduling problems originated in a joint project with the Alitalia Operations Research Department; in this project, we formalized and solved the company's ground staff management problems using the techniques described in this paper. The company then implemented such techniques in an operational software tool.
As is the case for most large-scale staff scheduling problems in large organizations, the number of days off per week is rigidly constrained, and the balancedness in the workload and in the assignment of days off is a key factor in the process of negotiating work agreements with trade unions. For this reason, the proposed model maximizes an objective function that, in accordance with staff requirements and with trade unions' suggestions, expresses staff satisfaction by means of weights assigned to pairs of shifts in consecutive days. The balancedness in the workload is dealt by a roster design, detailed in the next section. We refer to the addressed problem as the staff rostering problem (SRP). Balakrishnan and Wong (1990), Beaumont (1997), and Jaumard et al. (1998) describe problems with similar characteristics. The staff satisfaction principle is also considered with a different representation by Warner (1976) and by Millar and Kiragu (1998). We consider different types of constraints that may characterize staff scheduling problems, ranging from the more general ones, constraining the number of days off in each period and guaranteeing the covering of the staff requirements, to more specific ones, derived from the work agreement and regulating the number of days off in weekends and the number of consecutive work shifts. The result is a very difficult IP problem, where state-of-the-art commercial solvers fail to determine good solutions within reasonable time bounds. We tackle this problem by studying the associated polyhedron and deriving strong valid inequalities that very effectively reduce the gap.
Even in the presence of a small gap it is difficult to find the optimal solution with standard branching, due to the presence of strong symmetries in the solution space. To overcome this difficulty we have designed special branching rules to break such symmetries. Combining the proposed inequalities with these special branching rules it is possible to determine the optimal solution for problems of relevant sizes with a limited computational effort.
This paper is organized as follows. In [section]2 we provide a description of the problem, while in [section]3 we discuss the related IP formulation. Section 4 presents three classes of valid inequalities and related polyhedral properties. In [section]5 we discuss a particular class of valid inequalities that are derived from the solution of certain subproblems of SRP. Section 6 describes two special branching rules that significantly reduce the enumeration effort. Other inequalities are discussed in [section]7. In [section]8 we present computational results, and in [section]9 we draw some conclusions.
2. Problem Description
Most work agreements use the week as a temporal reference, and, thus, the number of working days or hours and the demand for services are defined with respect to this time unit. For this reason, in accordance with the related literature and with the application cases that we will describe at the end of this paper, we consider the following scheduling problem over the week:
Given a set of staff members P, a set of shifts S, and a minimum demand of each shift for the seven days of the week, one has to determine an assignment of the staff members that satisfies the daily minimum demand and the constraints derived from the work agreement, maximizing a measure of the staff satisfaction.
A shift is a work duty characterized by a starting time and a duration. The set of shifts S is an input of the problem. It contains also a particular shift, called rest shift, representing days off. The shifts in S cover different parts of the day and may be disjoint in time, or overlapping. A staff member can work any shift in S and can be assigned only one shift per day.
We represent the solution to this problem by a roster design that can be visualized by a table (called roster table) with a row for each staff member and seven columns indexed by the days of the week (see Table 1). We assume that a week starts on Monday and ends on Sunday. Each position in the roster table is called a cell and corresponds to a pair (employee, day); one shift must be assigned to each cell, if any (it will be the shift assigned to the employee for the corresponding day). The set of cells C is given by all the pairs of employees p [member of] P and days d [member of] D. Each row of the table represents a sequence of shifts to be covered during a week (shifts are identified by their starting time). The number of occurrences of a shift s in a day (i.e., over a column of the roster table) must satisfy the minimum demand for s on that day of the week.
At every new week, each member is assigned to the next row of the table, while the one in the last row is assigned to the first one. This circular assignment guarantees that, after |P| weeks, the workload is equally distributed among all staff members. The work agreement can impose different constraints on how to fill the cells of the roster table. One of the most relevant constraints is related to the number of days off per week. Other constraints are related to the number of consecutive working days and the number of rest shifts on weekend days. The objective of the problem is to find a roster table fulfilling all the constraints and maximizing staff satisfaction, which depends on consecutive rest shifts and on similar work shifts on consecutive days.
3. Integer Programming Formulation
We present an IP model for the class of staff scheduling problems described above. First, a very general formulation is given, where only the constraints that require exactly two rest shifts per week are considered; second, we add other constraints on the maximum number of consecutive working days and on the number of rest shifts on weekends.
We denote by P the set of staff members, by C the set of cells of the roster table, and by S the set of shifts, given by the work shifts plus the rest shift. We associate with...
|
