Problem description

This paper is concerned with the employee scheduling problem faced by the Kuwait National Petroleum Company (KNPC) in managing their gas stations. The problem is essentially concerned with the assignment and scheduling of different classes of employees at gas stations owned by KNPC. For the sake of ease in presentation, the term 'station' will be used to refer to 'gas station' and the term 'scheduler' will be used to refer to the firm that is presently hired by KNPC to perform the assignment and scheduling of employees at these stations. There are about 86 stations owned by KNPC located all over Kuwait (Table 1 provides some relevant statistics about the stations.) There are three working shifts for employees given as follows: 6:00 a.m.–2:00 p.m. (Shift 1), 2:00 p.m.–10:00 p.m. (Shift 2), and 10:00 p.m.–6:00 a.m. (Shift 3).

Table 1 - Statistics relevant to stations.

Full table

There are three categories of employees: supervisors, cashiers, and service workers. A full-service station requires a supervisor and a number of service workers, while a self-service station requires a supervisor (only during certain shifts as specified by KNPC), a cashier, and a number of service workers. A full-service station cannot operate without a supervisor, and a self-service station cannot operate without a cashier. The unavailability of a supervisor in a full-service station or a cashier in a self-service station during any operating shift leads to a closing down of the station, and the scheduler is fined by KNPC about $3000–$10,000, depending on the size and location of the station. Since the number of self-service stations is substantially higher than the number of full-service stations and, recently, most of the full-service stations are being converted into self-service stations, we only consider self-service stations in our model formulation. Also, the supply and scheduling of service workers is subcontracted by the scheduler to another company that undertakes this task based on specified agreements, and hence, the scheduling of service workers is not treated in our developed model. Therefore, the term 'employee' will henceforth refer to a 'supervisor' or a 'cashier', without distinction.

Each employee is entitled to two off-days per week and may be assigned to at most one shift per on-day. An employee is not allowed to work for six consecutive days or during consecutive shifts over two consecutive days (ie, the 10:00 p.m.–6:00 a.m. shift on one day and the 6:00 a.m.–2:00 p.m. shift on the next day). The scheduler aims to assign employees to stations as needed during each operating shift while complying with the employees' expressed preferences for stations, shifts, and on-/off-days, to the extent possible.

Presently, the scheduler adopts an ad hoc manual scheduling method that often leaves employees unhappy with their shift and station assignments. This affords a strong motivation for the present study. As far as implementation is concerned, whereas our approach adopts the real structure of the existing problem, because of the unavailability of some data that our model requires, we have randomly generated such data in a realistic manner in order to test our developed models. We aim to incorporate the proposed approach into a decision-support system that will be present to KNPC for implementation, based on our established proof-of-concept.

Related literature

The problem described above can be classified as a multiple-shift, multiple-work-centre, and multiple objective employee (tour) scheduling problem (refer to Ernst et al, 2004 for comprehensive classification schemes on employee scheduling problems). Tour scheduling problems combine both selecting off-days for the employees and allocating shifts for each of the on-days over the scheduling horizon. The objectives we aim to achieve in our problem are (a) to select the least number of employees while satisfying demand requirements, (b) to minimize the overall dissatisfaction of employees, and (c) to minimize discrepancies between employees' dissatisfaction levels. In the remainder of this section, we present literature related to recent work on tour scheduling problems.

Bechtold (1988) investigated an off-day scheduling problem and presented integer programming and heuristic solution strategies. Abdennadher and Schlenker (1999) proposed a constraint logic programming approach for a nurse scheduling problem that involves three shifts per day. The solution methodology is based on dividing the scheduling into two phases, one is concerned with the off-days and the other handles shift scheduling. Valouxis and Housos (2000) described a hybrid system that utilizes integer programming to construct feasible rosters for a nursing personal assignment problem, which are then improved using tabu search, local search, and two-opt heuristics. Brusco and Jacobs (2001) conducted an experimental study for analyzing policies of selecting shifts staring times for a specific tour scheduling problem. In this case, a feasible tour is uniquely determined by the daily shift staring time and the working days during the week. An integer programming model was presented for solving the resulting problem to minimize the total workforce size in order to meet variable demands. Carter and Lapierre (2001) formulated an integer programming model for generating schedules for emergency room physicians in six different hospitals.

Bard et al (2003) presented an integer programming-based approach for generating weekly schedules for workers at mail processing facilities. The problem involves finding on-days, shift lengths and start times, and breaks, for both part-time and full-time employees. Detailed computational results were presented for a 24 h and 7 days a week US postal processing and distribution centre. Eitzen et al (2004) presented a set covering formulation for the problem of rostering staff with non-hierarchical multiple skills under varying demand at a power station. The authors proposed three column-based solution methodologies: column expansion, column subset, and branch-and-price. Computational results for these methodologies were given for up to 100 employees, nine skill levels and three levels of demand. Topaloglu and Ozkarahan (2004) developed a goal programming model for the tour scheduling problem that implicitly represents scheduling flexibility and also includes information related to the preferred working patterns of employees. For more detailed review on tour scheduling problems, the reader may refer to Ernst et al (2004) and Alfares (2004).

The KNPC employee scheduling problem described in the foregoing section was examined in Al-Yakoob and Sherali (2006), where an exact mathematical formulation was developed for the problem. However, due to the overwhelming problem size, obtaining solutions for this formulation based on practical problem instances was found to be out-of-reach. Consequently, a two-stage reformulation of the problem was proposed. In Stage I, the sets of employees and stations were partitioned into mutually exclusive subsets, where each subset of employees was associated with only one subset of stations, and vice versa. This partitioning was based on employees' preferences for specific stations and for (the unattractive) Shift 3 for the 24-h stations. Accordingly, Stage I partitioned the problem into smaller subproblems, each of which involved a subset of the stations and a subset of the employees. Stage II was then concerned with assigning employees to shifts for the pertinent stations, as determined by the Stage I solution, and deciding upon off-days for such employees.

The partitioning scheme of Stage I attempts to match subsets of 42 employees to subsets of stations, each of which is composed of one of the following combinations: (a) ten 24-h stations, (b) eight 24-h stations and three 16-h stations, (c) six 24-h stations and six 16-h stations, (d) four 24-h stations and nine 16-h stations, (e) two 24-h stations and twelve 16-h stations, and (f) fifteen 16-h stations. Note that for a given week, each of the above combinations of stations involve 210 shifts, and hence, any of these valid combinations of stations may be staffed with 42 employees, given that each employee works exactly five shifts during any week.

An integer programming model for the Stage I problem was developed by Al-Yakoob and Sherali (2006). The aim of this model was to partition stations and employees into the same number of mutually exclusive subsets based on employees' preferences for stations, and then to match each set of stations with some set of employees. A modified formulation of the developed exact formulation for the overall problem was used to solve the Stage II problem, which involves determining the detailed schedules for employees separately within each matched group. The Stage I model was solved for test problems that involve at most two employee-to-station partitions, where for three and higher partitions, no meaningful solutions were obtained before encountering out-of-memory problems.

This paper presents an alternative mathematical programming formulation and a column generation approach for the overall KNPC employee scheduling problem without using any stage-wise decomposition. It turns out that the column generation approach of this paper facilitates good quality solutions to large-scale test instances in a reasonable time.

The remainder of this paper is organized as follows. Next, we present certain modelling preliminaries for the KNPC employee scheduling problem, and then, we formulate an integer programming model (ESM1) for this problem. Each column of this model represents a valid employee schedule. However, because there is an immense number of schedules that can be associated with each employee, the solution to even the continuous relaxation (denoted by ) of Model ESM1 is out-of-reach. Accordingly, a column generation method (CGM) to solve Model is presented subsequently, and this is then used to develop an effective heuristic procedure for Model ESM1. Finally, computational results are presented based on a number of test problem instances, and we conclude the paper with a summary of the developed column generation approach.

Modelling preliminaries

In this section, we discuss employees' preferences and present necessary notation and assumptions that will be needed to formulate Model ESM1. Other relevant notation is presented later as needed.

Modelling notation

Let represent the set of days in the planning horizon, and let d=1,...,|| index such days, where || is some integer multiple of seven. Let N (usually four) denote the number of weeks in . We partition the set into the set of weekdays D^WE and the set of weekend-days D^WD. Let E denote the set of employees, indexed by e=1,...,|E|, and let G be the set of stations, which is partitioned into G²⁴ and G¹⁶, where the former consists of the 24-h stations and the latter is composed of the 16-h stations. Hence, g=1,...,|G²⁴| and g=|G²⁴|+1,...,|G| index the 24-h and 16-h stations, respectively. Let t=1,2,3 index the operating shifts for the stations, where t=1 represents the daily 6:00 a.m.–2:00 p.m. shift, t=2 represents the daily 2:00 p.m.–10:00 p.m. shift, and t=3 represents the daily 10:00 p.m.–6:00 a.m. shift. Accordingly, let ³={1,2,3} and ²={1,2} represent the permissible shifts for the 24-h and the 16-h stations, respectively.

Let S_e denote the set of feasible schedules for an employee eE, which are indexed by s=1,...,|S_e|. Recall that a day d is an on-day for employee e based on schedule sS_e if this employee is assigned a shift on this day; otherwise, this day is an off-day for this employee. Accordingly, let D_e,s^on be the set of on-days for employee e if schedule sS_e is selected for this employee, and let D_e,s^off be the set of off-days for employee e if schedule sS_e is selected for this employee.

Preferences of employees

We present below certain guidelines for employees' preferences that are similar to those used in Al-Yakoob and Sherali (2006):

(a) Preferences for work centres: Each employee is instructed to list, in ascending order, m|G| different stations, the first of which represents the highest preference, and the mth of which represents the lowest preference, where m is some positive integer to be determined based on sensitivity analyses. We associate the number '1' with the first choice, '2' with the second choice, and so on. Hence, number '1' represents the highest preference or least penalty and number 'm' represents the lowest preference or most penalty. Based on these preferences, we define c_e,g¹ to assume values in the range {1,...,m} representing the penalty (dissatisfaction) of assigning employee e to work at station g.

(b) Preferences for shifts: Every employee is instructed to submit a permutation of the set {1,2,3} to express the preference with respect to daily shifts. For example, {3,1,2} indicates that Shift 3 (10:00 p.m.–6:00 a.m.) is the first choice of preference, Shift 1 (6:00 a.m.–2:00 p.m.) is the second choice of preference, and Shift 2 (2:00 p.m–10:00 p.m.) is the third choice of preference. Let c_e,t² represent the penalty (dissatisfaction) of assigning employee e to shift t. The coefficient c_e,t² takes one of the values 1, 2, or 3 based on the position of shift t in the submitted preference permutation of shifts.

For any given schedule sS_e of employee eE, define

Hence, for eE and sS_e, the value c_e,g,d,t^(1,2) represents the penalty of assigning employee e to work at station g during shift t if dD_e,s^on.

(c) Preferences for off-days: Every employee establishes a one-to-one matching between the days of the week and the list {1,2,3,4,5,6,7}. A day matched to number '1' indicates that this day is the employee's first off-day preference, and a day matched to number '2' indicates that this day is the employee's second off-day preference, and so on. Hence, we define c_e,d³ to represent the penalty (corresponding matched number) of assigning employee eE an off-day dD_e,s^off, for some sS_e. The coefficient c_e,d³ may assume any value from the set {1,2,3,4,5,6,7} based on the selected off-days preferences.

The overall penalty of employee eE associated with schedule sS_e is therefore given as follows:

A mixed-integer programming model

In this section, we present a mixed-integer programming formulation for the KNPC employee scheduling problem.

Decision variables and related parameters

For eE and sS_e, let

For a given employee eE and schedule sS_e, we define the following parameters that indicate whether an employee eE works at station gG²⁴ during shift t³ of day d, when schedule s is selected for this employee

In a similar manner, we define a parameter for the 16-h stations as follows:

Note that these parameter values are known based on the definition of the particular schedule sS_e for any employee, eE.

Problem constraints

The various problem constraints are presented in turn below:

(a) Satisfying employees' requirements at the stations: For a given 24-h station gG²⁴, the following constraint assures that station g is staffed with an employee during shift t³ of d,

Likewise, the demand for employees at each 16-h station is satisfied via the following constraint:

(b) Selecting schedules for employees: The following constraint ensures that at most one valid schedule may be selected for each employee.

Note that in this constraint, we assume that the number of employees that is needed to staff all stations for a given week is known in advance. This assumption is justified as follows: Suppose that each employee works five shifts per week and the total number of shifts required by all the stations over the time-horizon is divisible by 5N. Letting m^*=|³| |G²⁴| || and n^bull=|²| |G¹⁶| ||, then we can staff all the stations with (m^*+n^*)/5N= employees, for some positive integer number , given that the set partitioning constraints (1.1) and (1.2) admit a feasible solution.

On the other hand, if is not integral, we can add the minimum number of dummy shifts and include these in the generated schedules that would make an integral value. Also, if |E|>, then in lieu of (1.3), we could reserve the option of not selecting some |E|- employees for scheduling. However, for practical reasons, we will assume that |E|= (using dummy shifts, as necessary).

The overall model

The objective function of Model ESM1 is to minimize the overall dissatisfaction of the employees based on the selected schedules, which is given by _{eE sSe} C_e,sx_e,s. Hence, this objective term together with the constraints introduced above yields the following model (ESM1) for the KNPC employee-to-stations scheduling problem.

The continuous relaxation of Model ESM1 is denoted by and is given as follows.

Remark 1

Note that in practice, it is usually desirable to determine schedules that attain a degree of equity among employees with respect to the absolute differences in dissatisfaction levels from some central value (see Al-Yakoob and Sherali (2006), for example). However, such equity considerations have been omitted from Model ESM1 to facilitate the development of the proposed column generation approach, which enables the analytical solution of large-scale problems that would otherwise be untenable. Nevertheless, we propose the incorporation of preference-related equity considerations into the developed column generation heuristic (CGH) for future research. One possible way to accommodate this feature might be to partition the set of employees E into groups based on seniority considerations and then require the objective penalty value incurred by each employee in a particular group to lie within some bounded range. The proposed column generation scheme described below would then need to incorporate the appropriate penalty-range constraint when generating columns for each employee within each group. Sensitivity analysis could be used to ascertain suitable penalty ranges.

Remark 2

To illustrate the potential size of the full ESM1 model, suppose that there are fifty 16-h stations. Then, the total number of feasible schedules of an employee that can be generated for 1 week assuming that this employee is assigned two off-days is given by . The first term represents the selection of two off-days from the week. The second term indicates that for each of the remaining five on-days, this employee has two shift choices and 50 station choices.

Analysis of model ESM1 and a column generation approach

As noted in Remark 2, there is a huge number of feasible schedules associated with any employee. Since each column of Model ESM1 represents a valid schedule of some employee, it turns out that a direct solution of even Model is out-of-reach. To deal with this difficulty, we design in this section, a column generation approach to solve Model based on which we devise in the next section, an iterative procedure to solve the KNPC employee scheduling problem.

The following notation will be used in this section.

v(M)

the optimal objective function value of any model M

the continuous relaxation of any model M

I

the identity matrix

0

a column vector that is composed of entries each of which is 0

0^1,i

a column vector that is composed of entries each of which is 0, except the ith entry, which is 1

0

a zero matrix

1

a column vector that is composed of entries each of which is 1

a column vector that is composed of entries each of which is

V^T

transpose of a column vector V

(V)_i

the ith entry of a vector V

p=_eE |S_e|

 

In the remainder of this section, we formulate a set of constraints whose feasible region characterizes the set of all valid schedules of a given employee.

Examining the column structure of Model and related issues

In this section, we introduce matrix notation that will be used in our analysis of Model .

Given eE and sS_e, let

For gG²⁴, let

For gG¹⁶, let

Let O_e¹ be an |E| |S_e| matrix, where each column of O_e¹ is given by 0_|E|^1,e, and let O¹=[O₁¹,...,O_|E|¹]. Then, Model can be expressed in matrix notation as follows:

Letting

Model can be restated as: Minimize {C^Tx:Ax=b, lbxub}.

Note that each column of the matrix A that corresponds to the section involving the matrices H and M represents a valid schedule for an employee. The corresponding - and -values prescribe the working shifts, off-days, and stations for the particular employee. For any eE, we can define a set of constraints in terms of certain binary decision variables whose feasible region, denoted by FR_e, corresponds to the columns (schedules) of the matrix A that are associated with employee eE. Hence, any column of A that corresponds to this employee represents a feasible point in FR_e, and vice versa.

To this end, for each eE, let

Then, the feasible region, FR_e, defined below, represents all feasible schedules for this employee.

Constraint (2.1) assures that employee e may be assigned at most one shift during any given day of the time-horizon provided that this day is an on-day. Working during shift t=3 of one day and shift t=1 of the next day is not permitted, as enforced by constraint (2.2). Employee e must have five on-days during any given week of the time-horizon, as ascertained by constraint (2.3). Constraint (2.4) ensures that an employee can consecutively work for at most 5 days over the time-horizon. Finally, constraint (2.5) represents the binary logical restrictions. Hence, any feasible point in FR_e corresponds to a schedule for employee e, say sS_e, where _e,s^g,d,t=24_e^g,d,t and _e,s^g,d,t=16_e^g,d,t.

A CGM for solving Model

Next, we present a column generation approach (CGM) that will facilitate reasonable solutions for for problem instances that cannot be solved directly.

Suppose that at some iteration of the revised simplex method for bounded variables as applied to solve , we have a basic feasible solution characterized as follows: A basis matrix given by B and nonbasic variable matrices given by N₁ and N₂, where N₁ corresponds to the columns of the nonbasic variables that are currently at their lower bound of zero, and N₂ corresponds to the columns of the nonbasic variables that are currently at their upper bound of one. Let S^lb and S^ub be the index sets for the nonbasic variables that are currently at their lower and upper bounds, respectively. Furthermore, let the x and C vectors be partitioned as follows:

Let ^T=C_B^TB^-1, Y_lb^T=^TN₁, and Y_ub^T=^TN₂. Note that Y_lb^T-C_N1^T and Y_ub^T-C_N2^T represent the negative reduced cost coefficient vectors that correspond to the vectors of nonbasic variables x_N1 and x_N2, respectively. Let j=1,...,p, where j=1,...,|S₁| indexes the feasible schedules of employee e=1, j=|S₁|+1,...,|S₁|+|S₂| indexes the feasible schedules of employee e=2, and so on. Hence, each j{1,...,p} corresponds to a schedule sS_e of some employee eE. Accordingly, we may replace x_e,s by x_j and C_e,s by C_j where the index j corresponds to (e,s) as discussed above.

Thus, Model can be rewritten as follows, by expressing the basic variables in terms of the nonbasic variables.

Consequently, the current solution is optimal if ((Y_lb^T)_j-(C_N1)j)0 for all jS^lb and ((Y_ub^T)_j)-(C_N2)j0 for all jS^ub. On the other hand, if this solution is not optimal, we shall modify the value of only one nonbasic variable while all other nonbasic variables are fixed at their lower or upper bounds. Assume that the current solution is not optimal and let k index the entering variable. By Dantzig's Rule, we select an entering variable that yields the maximum rate of objective function decline among all other candidate entering variables. Let ₁=max_{jS^lb{(Ylb^T)j-(CN1^T)j}}, ₂=max_{jS^ub{(CN2^T)j-(Yub^T)j}}, and =max{₁,₂}

Since the solution is not optimal, >0, and hence, let kS^lbS^ub be an index for which the above maximum is achieved. Now, if kS^lb, then x_k is increased from zero, and if kS^ub then x_k is decreased from one.

Let be any column of the matrix N₁ or N₂. This column represents a schedule sS_e for some employee eE. Hence, for the sake of ease in reference, we use (e,s) to denote . Accordingly, we can express (e,s) as

where ₁(e,s), ₂(e,s), and ₃(e,s) are, respectively, the parts of (e,s) that correspond to the matrices H, M, and O¹. The entries of ₁(e,s) and ₂(e,s) can be, respectively, derived from the _e,s^g,d,t- and _e,s^g,d,t-values, and ₃(e,s)0_|E|^1,e. Likewise, we partition ^T into (1)^T, (2)^T, and (3)^T. Conformingly, let 1_e^g,d,t denote the entries of (1)^T for gG²⁴, and let 2_e^g,d,t denote the entries of (2)^T for gG¹⁶. Also, let 3_e denote the entries of (3)^T.

Note that exactly one schedule is to be selected for each employee as noted by constraint (1.3). Hence, |S^ub||E|, otherwise constraint (1.3) of Model would be violated. Accordingly, the employees that are associated with the variables in S^ub can be easily determined. Let E^ub be the subset of the employees for which one of the corresponding x-variables is binding at its upper bound.

For , the following (auxiliary) mixed-integer programming model (AP_e^lb) determines whether any of the nonbasic variables associated with this employee, which are currently at their lower bounds of zero, is a candidate to enter the basis:

AP_e^lb

Note that the first three terms of the objective function sum to (^TA_e,s) for some resulting column A_e,s of the matrix A that represents a schedule sS_e, and likewise, the last three terms of the objective function yield C_e,s.

Since |E^ub||E|, and since |E| is relatively small, we can explicitly price the nonbasic variables that are presently at their upper bounds and determine ₂, and hence, identify a candidate for the entering nonbasic variable. Accordingly, let v_e^ub be the reduced cost coefficient for the nonbasic variable that is associated with eE^ub.

Let

Now, consider the following two cases:

1. If 0, then none of the nonbasic variables is a candidate to enter the basis.
2. If >0, then we can derive a candidate entering variable for Model as follows:
   1. if ₁>₂, find the x-variable corresponding to the column associated with employee e^* from the optimal solution obtained for Model AP_e^*lb.
   2. if ₁₂, find the x-variable corresponding to the column associated with employee e^**.

A column generation-based heuristic procedure

In this section, we present a sequential variable-fixing heuristic procedure to construct a feasible solution for the KNPC employee scheduling problem by selecting one valid schedule for each employee. In essence, this procedure selects valid schedules for employees based on solutions of Model obtained via the CGM method outlined in the foregoing section.

Consider a solution to Model obtained using the CGM procedure. Let S_b be the index set for the basic variables. Let S_b¹S_b be the index set of basic variables that are equal to one when this routine terminates, and let S_b^f be the set of fractional basic variables. (Note that if S_b^f=, we have |E| schedules at hand, one for each employee, and we can stop with this solution as optimal to Model ESM1.) Consider the set K=S_b¹S^ub, where S^ub is the index set of nonbasic variables that are currently at their upper bounds of one, as defined in the foregoing section. Recall that each index in the set K corresponds to an employee schedule, where we have _j=1, jK. Also, let _max=max_jSb^f{j} and L={jS_b^f:_j=_max}. Pick L and augment the set K K{}. Recall that each index in the set K corresponds to an employee schedule. Moreover, note that no two indices in this updated set K could correspond to the same employee, because otherwise, constraint (1.3) would be violated. Let E^K{eE: there exists an index in this updated set K that corresponds to employee e}. Let ^K denote the complement of E^K in E.

Note that the employees prescribed by the set K will staff certain shifts of the stations based on their selected schedules. Hence, let us define the set _g,d³ and _g,d² as follows:

and

Let ESM1_^K be a modified version of ESM1 obtained by (a) restricting the set of employees to ^K, and (b) updating constraints (1.1) and (1.2) as delineated by (4.1) and (4.2) below, respectively.

We can now solve Model using the CGM procedure and repeat the above process with this remnant set of employees and unmanned shifts over the stations and the time-horizon. The overall proposed CGH procedure for selecting the employees' schedules is stated below

Procedure CGH

Initialization

• Set K=, ^K=E, _g,d³=³,gG²⁴, d, and _g,d²=²,gG¹⁶, d.

Main Step

• Solve Model using CGM and let denote the resulting solution.
• Determine the index sets S_b¹,S_b^f, and S^ub.
• Update K KS_b¹S_ub.
• If S_b^f=, then stop; the required employees' schedules are collectively described by the set K. Otherwise, proceed to the next step.
• Let _max=max_jSb^f{j} and L={jS_b^f:_j=_max}.
• Pick L and update K K{}.
• If |K|=|E|, then stop; the required employees' schedules are collectively described by the set K. Otherwise, proceed to the next step.
• Update ^K, _g,d³, gG²⁴, d, and _g,d², gG¹⁶, d.
• Repeat the Main Step.

Remark 3

(a) Note that at each iteration of Procedure CGH, the set K is augmented by at least one element. Also, note that at each iteration, the number of elements in K cannot exceed |E|. Consequently, the algorithm terminates whenever |K|=|E|.

(b) At each iteration of Procedure CGH, unmanned shifts are staffed with available employees taking into consideration shift and work load restrictions related to employees. Therefore, Procedure CGH generates a feasible solution to the KNPC employee scheduling problem.

Computational results and related issues

In this section, we present computational results related to solving the employee scheduling problem faced by the KNPC, using the CGH developed in the foregoing section. We use the software package CPLEX-MIP (version 9.0) with its default settings to solve the different subproblems within the routine CGH. All runs were made on a Pentium 4, CPU 1.70 GHz computer having 512 Mb of RAM with coding in Java. Our set of test problems is comprised of 22 test instances as specified in Table 2. This set of problems spans various plausible employee–station partitioning structures. The maximum number of employee–station partitions that was handled in Al-Yakoob and Sherali (2006) was two. In our computational results, we consider up to nine partitions, noting that the first nine test problems in Table 2 are those examined by the authors in Al-Yakoob and Sherali (2006).

Table 2 - Statistics related to 22 test problems.

Full table

The number of employees |E| in each test problem is specified by |E|=(21 |G²⁴|+16 |G¹⁶|)/5, which equals the minimum number of employees needed to staff all the stations for a week, given that each employee works five shifts. The time-horizon considered in each test problem is one week (ie, N=1). The employees' preferences for stations, shifts, and off-days are generated randomly.

Let be the objective function value of the continuous relaxation of Model ESM1 obtained via Procedure CGM and let v_CGH(ESM1) be the objective function value of Model ESM1 obtained using Algorithm CGH. Let denote the percentage optimality generated by v_CGH (ESM1) with respect to the lower bound as given by

Let v_min and v_max denote the minimum and maximum possible total preferences (for 1 week) for a given test problem. Table 3 presents statistics related to solving Model ESM1 along the values of v_min and v_max for each test problem.

Table 3 - Statistics related to solving Model ESM1.

Full table (66K)

Remark 4

(a) The results in Table 3 conservatively guarantee that all problems were solved (at least) to 64–85% of optimality using the proposed heuristic.

(b) It is worth mentioning that a direct solution to the continuous relaxation of Problem ESM1 is out of reach due to the overwhelming number of employees' schedules that can be generated. The CGM, however, enabled us to solve the continuous relaxation of Problem ESM1 easily for all the test problems.

(c) The total CPU time (in seconds) for solving Problem ESM1 using Algorithm CGH is slightly higher than the total CPU time (in seconds) for solving the continuous relaxation of Model ESM1 using Method CGM.

(d) The modelling approach of this paper enabled us to solve test problems involving up to 90 stations and 336 employees, which was not possible using the two-stage approach (TSA) of Al-Yakoob and Sherali (2006).

In order to compare the performance of the approach of this paper with the TSA of Al-Yakoob and Sherali (2006), we attempted to generate weekly schedules for the 22 test problems employing TSA, however, while omitting all issues related to equity considerations. Let v(TSA) denote the objective function value obtained via the TSA, and let

represent the percentage improvement in the objective value produced by CGH with respect to v(TSA). Table 4 presents results on the performance of these two methodologies, where the TSA produced solutions only for the first nine test problems, while for the remaining test problems, we were unable to obtain solutions due to out-of-memory difficulties.

Table 4 - A comparison of Procedure CGH and the TSA.

Full table

The results in Table 4 indicate that the proposed approach consistently provides an improvement of about 6–33% in the objective value over the TSA. Hence, the added robustness and speed of execution of Heuristic CGH renders it greatly superior to the procedure presented in Al-Yakoob and Sherali (2006).

Concluding remarks

This paper presents a column generation approach to solve the employee scheduling problem that is faced by the KNPC. A mixed-integer programming model (ESM1) that composes feasible sets of employee schedules to staff all the stations taking into consideration shifts and load restrictions is developed. This model facilitates the design of a CGM that is used to solve the continuous relaxation of Model ESM1. A CGH based on CGM is then proposed to solve the KNPC employee scheduling problem.

The column generation approach heuristic (CGH) of this paper facilitates solutions for test problem instances similar to the KNPC employee scheduling problem that could not be solved via the TSA developed in Al-Yakoob and Sherali (2006). In particular, via this heuristic, we were able to generate employee schedules for up to 90 stations and 336 employees, whereas the two-stage procedure (TSA) was able to handle at most 29 stations and 84 employees. The TSA, however, takes into consideration the equity objective of minimizing the absolute differences between dissatisfaction levels of employees in terms of assigned off-days, shifts, and work centres. This equity consideration was omitted to maintain a certain column structure of Model ESM1, which promoted the formulation of Problem AP_e^lb, and hence, the design of the proposed CGH. For the sake of comparison, we generated employees' schedules for the 22 test problems using the TSA while omitting all equity-related modelling considerations. For the first nine test problems that we were able to solve using the TSA, Procedure CGH yielded improved objective function values ranging between 6 and 33% over all the test problems.

Future research will explore alternative approaches that incorporate preference-related equity considerations while still being able to handle large-scale instances via column generation, similar to the methodology developed in this paper. provides some guidelines in this direction. Also, we aim to investigate efficient back-up modelling approaches to avoid closedowns of stations to the extent possible, given the severe financial consequences of having to close a station due to inadequate staffing.

References

1. Abdennadher S and Schlenker H (1999). Nurse scheduling using constraint logic programming. In: Proceedings of the 11th Conference on Innovative Applications of Artificial Intelligence. AAAI Press, Menlo Park, CA, pp 838–843.
2. Alfares H (2004). Survey, categorization, and comparison of recent tour scheduling literature. Ann Oper Res 127: 145–175. | Article | ISI |
3. Al-Yakoob SM and Sherali HD (2006). Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations. Ann Oper Res, accepted.
4. Bard J, Binici C and de Silva A (2003). Staff scheduling at the United States Postal Service. Comput Oper Res 30: 745–771. | Article | ISI |
5. Bechtold S (1988). Implicit optimal and heuristic labour staffing in a mutiobjective multilocation environment. Decis Sci 19: 353–373. | Article | ISI |
6. Brusco M and Jacobs L (2001). Starting-time decisions in labor tour scheduling: An experimental analysis and case study. Eur J Oper Res 131: 459–475. | Article | ISI |
7. Carter M and Lapierre S (2001). Scheduling emergency room physicians. Health Care Manage Sci 4: 347–360. | Article | ChemPort |
8. Eitzen G, Panton D and Mills G (2004). Multi-skilled workforce optimisation. Ann Oper Res 127: 359–372. | Article | ISI |
9. Ernst AT, Jiang H, Krishnamoorthy M, Owens B and Sier D (2004). An annotated bibliography of personnel scheduling and rostering. Ann Oper Res 127: 21–144. | Article | ISI |
10. Topaloglu S and Ozkarahan I (2004). An implicit goal programming model for the tour scheduling problem considering the employee work preferences. Ann Oper Res 128: 135–158. | Article | ISI |
11. Valouxis C and Housos E (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artif Intell Med 20: 155–175. | Article | PubMed | ISI | ChemPort |

Acknowledgements

This work was supported by Kuwait University under Research Grant No. [SM06/02] and by the National Science Foundation under Grant No. DMI-0094462. We gratefully acknowledge the assistance of Ms Renju Lekshmi in implementing the developed procedures.