1. Introduction

Workforce staffing and scheduling research comprises a substantial component of the literature base in service capacity management. Areas of application include hospital nursing (Bard and Purnomo, 2005; Wright et al., 2006), telephone operations and call centers (Brusco and Jacobs, 2000; Iravani et al., 2007), postal facilities (Jarrah et al., 1994; Bard, 2004; Bard and Wan, 2005), toll collection booths (Jacobs and Brusco, 1996), fast-food restaurants (Hueter and Swart, 1998) and airport stations (Brusco and Jacobs, 1998; Mason et al., 1998). A significant portion of the academic literature focuses on the development of optimal and heuristic solution procedures for staffing and scheduling problems; however, there are also research streams that emphasize the assessment of staffing and scheduling policies. Many published studies offer both a methodological and policy analysis contribution.

The cross-utilization of workers among different skill classes, departments or work centers is an especially imperative area of study that requires effective solution procedures and analysis of policies. In practice, there are many situations where labor requirements must be subdivided based on departments, work centers or skill categories. For example, requirements for agents in a telephone call center could be partitioned into sales orders and customer inquiries (e.g., Andrews and Cunningham (1995)). Different skill categories also necessitate the specification of multiple sets of requirements in mail processing and distribution centers (Bard, 2004). The demand for hospital nursing labor is often specified by department and/or skill class (registered nurses, licensed practical nurses, nursing assistants, etc.), which offers the potential for both downward substitution among the skill classes as well as "float pools" of nurses who can work in different departments (Warner and Prawda, 1972; Trivedi and Warner, 1976).

The potential for cross-utilization of a workforce is a function of the cross-training of employees. During the past 10 years, there has been a concerted effort to better understand the benefits of cross-training in both manufacturing (Slomp and Molleman, 2002; Bokhorst et al., 2004; Hopp et al., 2004; Hopp and Van Oyen, 2004; Jordan et al., 2004; Iravani et al., 2005) and service environments (Brusco and Johns, 1998; Campbell, 1999; Inman et al., 2005; Iravani et al., 2007). Although our interest in this paper focuses on service operations, many of the relevant issues are portable across both service and manufacturing systems (Iravani et al., 2005).

The hierarchy of workforce planning presented in Abernathy et al. (1973) provides one possible basis for framing recent cross-utilization research pertaining to service operations. The levels of the hierarchy, from top to bottom, are: (i) planning; (ii) scheduling; and (iii) allocation. At the planning phase, which is sometimes referred to as the "staffing" or "budgeting" phase, staffing levels and skill mixes for each department or work center are established for an annual or semi-annual basis. The scheduling phase focuses on the assignment of employees to days-off and daily shift patterns for a period that is typically 1 to 4 weeks. The allocation phase focuses on the day-to-day, within- and between-shift adjustments of labor across departments to more effectively meet changing requirements attributable to demand and capacity variations.

Brusco and Johns (1998) provided an analysis of cross-training policies at the planning phase. They used an integer programming model to determine the number of workers in different skill classes with the objective of minimizing staffing costs subject to constraints that guaranteed satisfaction of labor requirements in all departments (no shortages were permitted). Iravani et al. (2007) focused on a strategic analysis of cross-training structures for inbound call centers. They developed an innovative deterministic rule for evaluating different structures, which was based on average path length in small-world networks.

In contrast, Campbell (1999) and Inman et al. (2005) investigated cross-training policies for hospital nursing at the allocation phase; however, the contexts of their analyses were markedly different. Campbell (1999) proposed a non-linear assignment model for allocating cross-trained workers at the beginning of a shift with the objective of maximizing a utility function. His experimental analysis was based on obtaining heuristic solutions to the resulting optimization model for synthetically constructed test cases, and evaluating cross-training policies based on improvement in the utility function. In contrast, Inman et al. (2005) built a simulation model that was used to investigate the performance of several cross-training policies when randomness with respect to both demand and capacity was present. The performance measure in their study was the number of nursing shifts that had to be met via staff from a supplemental nursing agency. More recently, Batta et al. (2007) presented a mathematical programming model and column generation heuristic for service systems that process multiple types of customers. Their model, which is adaptable for multiple phases of the workforce planning hierarchy, is characterized by an objective function that considers both staffing and switching (reassignment of employees to different customer types) costs.

Our paper revisits the Non-linear Workforce Allocation Problem (NWAP) studied by Campbell (1999). The motivation for this additional investigation is based on several factors. First, the context of Campbell's policy study was one where cross-utilization is apt to be especially constructive because many service environments must operate in the presence of labor shortages. The provision of hospital nursing care, for example, is a noteworthy area of study where cross-utilization is one strategy for coping with shortages of labor (Jack and Powers, 2004; Inman et al., 2005; Wright et al., 2006). For his analyses, Campbell selected an objective function of maximizing utility, which was measured using a quadratic function of shortage costs. Although this is a legitimate and reasonable criterion with an established history in the literature (Warner and Prawda, 1972; Trivedi and Warner, 1976), we outline a couple of alternative criteria that might be appropriate for certain situations.

The second reason for revisiting Campbell's model is to offer an exact solution procedure for the NWAP. Campbell solved the NWAP using a linear assignment heuristic (see Campbell and Diaby (2002)) and demonstrated that this procedure typically yielded a small departure from an upper bound. With respect to the development of exact methods for the NWAP, Campbell and Diaby (2002, p. 20) observed that "... optimal solutions are likely to remain elusive". Nevertheless, we developed a branch-and-bound procedure that provided a confirmed, globally optimal assignment of workers in less than a CPU second for more than 96% of the 4096 cross-utilization problems in our test set. The algorithm, which can be modified easily for alternative objective criteria, facilitates cross-utilization experiments without the need for qualifying results based on the potential for suboptimal solutions.

The third motivating issue for this paper is that Campbell offered an interesting experimental paradigm for evaluating the effectiveness of a cross-training policy within the context of the NWAP. Nevertheless, since the time his study was conducted, several important cross-training issues have been offered in the literature. A particularly salient aspect of cross-training is the structural flexibility provided by chaining skill classes of workers, which was originally proposed by Jordan and Graves (1995) in the context of manufacturing process flexibility. A lack of chaining occurs when departments are partitioned into subgroups (usually pairs of departments) such that there is cross-training within the subgroups but not between the subgroups (see, for example, the discussion of reciprocal pairs presented in Inman et al. (2005)). In contrast, when chaining is present, no such partition exists. Instead, an "overlapping subgroup" perspective is appropriate, where each subgroup shares departments with other subgroups. The beneficial consequences of chaining have received considerable attention (Brusco and Johns, 1998; Graves and Tomlin, 2003; Hopp et al., 2004; Hopp and Van Oyen, 2004; Jordan et al., 2004; Inman et al., 2005; Iravani et al., 2005, 2007). Aside from chaining, the importance of worker absenteeism (Slomp and Molleman, 2002; Inman et al., 2005) and partial cross-training (i.e., having some percentage of the workforce that is cross-trained) are other relevant issues for experimental investigation. Accordingly, we have broadened Campbell's (1999) study to accommodate chaining, partial-cross-training and absenteeism factors. Our results shed some new insights regarding main effects and interactions among experimental factors.

In Section 2, we describe the NWAP, address possible variations of the objective function and present the Campbell-Diaby linear assignment heuristic (Campbell and Diaby, 2002). This is followed in Section 3 by a description of the proposed branch-and-bound algorithm for solving the NWAP. Section 4 compares the performances of the linear assignment heuristic and branch-and-bound algorithm for two test problems: (i) a small example reported by both Campbell (1999) and Campbell and Diaby (2002); and (ii) a larger example based on data from a 600bed Florida hospital (Brusco, 1990). Section 5 describes the design and results of the computational study The paper concludes with a brief summary in Section 6.

2. An allocation problem for a cross-trained workforce

2.1. The NWAP due to Campbell (1999)

Campbell (1999) presented the NWAP for allocating cross-trained workers to departments or work centers with an objective of maximizing overall utility The NWAP allows for a variety of possible utility functions (Warner and Prawda, 1972), fractional worker capabilities (Campbell, 1999) and the inclusion of side constraints. Our description uses the following parameters.

D = the number of departments or work centers, indexed d = 1, 2,..., D;

N = the number of workers requiring assignment to a department, indexed n = 1, 2,..., N;

[a.sub.nd] = the productivity of worker n in department d, where 0 [less than or equal to] [a.sub.nd] [less than or equal to] 1 for 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D;

[S.sub.n] = the set of departments for which worker n has non-negative productivity, [a.sub.nd] > 0 [right arrow] {d} [member of] [S.sub.n], for 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D;

[w.sub.d] = the relative importance weight for department d, for 1 [less than or equal to] d [less than or equal to] D;

[r.sub.d] = the requirement for workers in department d, for 1 [less than or equal to] d [less than or equal to] D.

The decision variables of the model are as follows.

[y.sub.nd] = 1 if worker n is assigned to department d, 0 otherwise, for 1 [less than or equal to] n [less than or equal to] N and d [member of] [S.sub.n];

[P.sub.d] = the total workforce productivity assigned to department d, for 1 [less than or equal to] d [less than or equal to] D.

Using these definitions, the NWAP is represented as follows.

max [Z.sub.1] = [D.summation over (d=1)]g([p.sub.d]), (1)

subject to

[summation over (d[member of][S.sub.n])][y.sub.nd] = 1 for 1 [less than or equal to] n [less than or equal to] N, (2)

[N.summation over (n=1)][a.sub.nd][y.sub.nd] = [p.sub.d] for 1 [less than or equal to] d [less than or equal to] D, (3)

[y.sub.nd] [member of] {0, 1} for 1 [less than or equal to] n [less than or equal to] N, d [member of] [S.sub.n], (4)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

The objective function of the NWAP, as defined by Equation (1), is an additive function of utilities of the individual departments, g([p.sub.d]), for 1 [less than or equal to] d [less than or equal to] D. As shown in Equation (5), the utility of department d is a quadratic function of departmental shortage. If the productive workload in department d equals or exceeds the labor requirement (i.e., [p.sub.d] [greater than or equal to] [r.sub.d]), then the full contribution of weighted utility is awarded (i.e., [w.sub.d][r.sub.d.sup.2]). However, if [p.sub.d] < [r.sub.d], then the contribution to the utility is reduced by weighting the squared shortage. Specifically, [w.sub.d][r.sub.d.sup.2] is reduced by [w.sub.d]([r.sub.d]-[p.sub.d])[.sup.2]. Constraint set (2) ensures that each worker is assigned to only one department. Constraint set (3) links departmental productive workload to worker assignments. Constraint set (4) imposes binary restrictions on the assignment variables.

2.2. Variations of the objective function for the NWAP

The objective function of the NWAP reduces the department utility by imposing a quadratic penalty for shortages. This criterion, which draws heavily on the work of Warner and Prawda (1972), is predicated on the assumption that shortage costs are a non-linear increasing function of the magnitude of the shortage, see also Hershey et al. (1974). Warner and Prawda (1972) cited several hospital staffing studies to support the quadratic shortage penalty (Connor, 1960; Stafford and Schlotfeldt, 1960; Feyerherm and Kirk, 1964). Quadratic, or variance-type criteria for equitable distribution of employee surpluses have also been described in the literature (Bechtold, 1981; Easton and Rossin, 1991).

For consistency with the work presented in Campbell (1999) and Campbell and Diaby (2002), our presentation of solution methods for the NWAP in subsequent sections will use their original objective function as defined by Equations (1) and (5). Nevertheless, we recognize that different objective criteria could also be employed. An alternative presentation of the objective function of the NWAP facilitates the development of other objective criteria. Specifically, Equations (1) and (5) can be collapsed as follows:

max [Z.sub.1] = [D.summation over (d=1)][w.sub.d][r.sub.d.sup.2] - [D.summation over (d=1)][w.sub.d](max([r.sub.d] - [p.sub.d], 0))[.sup.2]. (6)

The first term in Equation (6) is a constant, which is collected in the objective function regardless of whether departmental shortages do or do not exist (see Equation (5)). Accordingly, this constant term can be deleted from the model. The second term in Equation (6) imposes the quadratic penalty based on the shortage. Deletion of the constant term and changing the sign of the second term clearly illustrates that the objective function of the NWAP can be stated precisely as minimizing a weighted quadratic function of shortage:

min [Z.sub.2] = [D.summation over (d=1)][w.sub.d](max([r.sub.d] - [p.sub.d], 0))[.sup.2]. (7)

Using this restatement of the objective function of the NWAP it is easy to construct a host of alternative objective criteria. We offer two possible adaptations. The first adaptation is based on the criticism that Equation (7) does not consider the magnitude of the shortage relative to the requirement A shortage of three workers would incur the same penalty in the objective function regardless of whether the labor requirement was ten or 100. For service environments where there is considerable disparity among the labor requirements, an alternative criterion that expresses the shortage as a percentage of the requirement might be appropriate:

min [Z.sub.3] = [D.summation over (d=1)][w.sub.d](max([[r.sub.d] - [p.sub.d]]/[r.sub.d], 0))[.sup.2]. (8)

As another example, consider service systems where customer waiting can be reduced by providing additional workers. In such instances, the provision of surplus employees could possibly offer an improvement in utility Although many alternatives for accommodating this scenario exist, one potential modification of Equation (7) is

max [Z.sub.4] = [D.summation over (d=1)][w.sub.d]([alpha](max{[p.sub.d] - [r.sub.d], 0})[.sup.2] - (1 - [alpha])(max{[r.sub.d] - [p.sub.d], 0})[.sup.2]). (9)

The objective function posed by Equation (9) maximizes a weighted function of shortages and surpluses If [p.sub.d] > [r.sub.d], then a positive contribution to the objective function, weighted by [alpha], is awarded for the squared surplus On the other hand, if [p.sub.d] < [r.sub.d], then a penalty on the objective function, weighted by (1 - [alpha]), is imposed for the squared shortage. The parameter [alpha] (0 < [alpha] < 1) controls the relative importance of surpluses and shortages For example, if [alpha] = 1/3, then a shortage would be penalized twice as much as a surplus of the same magnitude would be rewarded.

2.3. Linear assignment heuristic

Campbell and Diaby (2002) observed that the NWAP can be approached using a variety of heuristic solution procedures. Additionally, these authors concluded that verifiably optimal solutions for the general case that permits fractional productivity coefficients would likely remain elusive, and that branch-and-bound schemes would typically require excessive computation times. Campbell and Diaby (2002) developed a linear assignment heuristic, which produces guaranteed optimal solutions when the productivity coefficients are binary, and sharply outperformed a greedy heuristic and a Lagrangian relaxation heuristic in their experiments. In addition to the previously presented notation, the linear assignment heuristic requires definition of the following parameters.

B = an N x D matrix, [[b.sub.nd]], with columns containing the ranked [a.sub.nd] values in descending order;

pm[x.sub.dq] = the largest possible value of [p.sub.d] prior to assignment of slot q (i.e., the qth worker assigned) in department d (this quantity is the sum of the first q - 1 elements in column d of matrix B), for 1 [less than or equal to] d [less than or equal to] D and 1 [less than or equal to] q [less than or equal to] N;

[[DELTA].sub.dq.sup.n] = an estimate of the improvement in the objective function value (1) that is realized from assigning worker n to slot q in department d for 1 [less than or equal to] n [less than or equal to] N, 1 [less than or equal to] d [less than or equal to] D and 1 [less than or equal to] q [less than or equal to] N;

The computation of [[DELTA].sub.dq.sup.n] proceeds as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

We also define following decision variables:

[x.sub.ndq] = 1 if worker n is assigned to slot q in department d, 0 otherwise, for 1 [less than or equal to] n [less than or equal to] N, d [member of] [S.sub.n] and 1 [less than or equal to] q [less than or equal to] N.

With these definitions in place, the Campbell-Diaby heuristic requires solution of the following linear assignment problem.

max [Z.sub.5] = [N.summation over (n=1)][summation over (d[member of][S.sub.n])][N.summation over (q=1)][[DELTA].sub.dq.sup.n][x.sub.ndq], (11)

subject to

[summation over (d[member of][S.sub.n])][N.summation over (q=1)][x.sub.ndq] = 1 for 1 [less than or equal to] n [less than or equal to] N, (12)

[N.summation over (n=1)][x.sub.ndq] [less than or equal to] 1 for 1 [less than or equal to] d [less than or equal to] D, 1 [less than or equal to] q [less than or equal to] N, (13)

[x.sub.ndq] [member of] {0, 1} for 1 [less than or equal to] n [less than or equal to] N, d [member of] [S.sub.n]. (14)

The objective function (11) represents the maximization of the estimated utility. Constraint set (12) requires each worker to be assigned to one of the available department slots. Constraint set (13) ensures that no more than one worker is assigned to a slot, and constraint set (14) places the binary restrictions on the assignment variables.

The use of slots and the clever development of the [[DELTA].sub.dq.sup.n] parameters are the crux of the Campbell-Diaby procedure. For the case of [a.sub.nd] [member of] {0, 1} for all 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D, the parameter estimates of [[DELTA].sub.dq.sup.n] represent the exact marginal contribution to the objective function, and thus the optimal solution to the linear assignment heuristic is also an optimal solution to the NWAP However, in the case of fractional productivity coefficients, the [[DELTA].sub.dq.sup.n] values can underestimate the actual marginal contribution. The reason for this underestimation is that the pm[x.sub.dq] values are computed based on maximum possible [p.sub.d] values, which might not be realized because slots could be filled by workers with productivity coefficients that are smaller than the maximum possible for slots.

3. A branch-and-bound algorithm

3.1. Algorithm development

We offer a branch-and-bound method for obtaining optimal solutions to the NWAP. The algorithm uses a forward branching scheme where the level of depth in the search tree corresponds to a particular worker. We refer to a partial assignment as one where some, but not all, workers have been assigned to a department. We have found that sequencing the workers, such that those with primary responsibility in the departments with greater workload requirements (i.e., larger [r.sub.d] values) are placed first in the ordering, reduces the computation time. We also compute two sets of indices prior to entering the branch-and-bound process These indices, which play significant roles during the execution of the branch-and-bound algorithm, need only be computed once and are subsequently called as necessary during the search process They are computed as follows:

[[tau].sub.nd] = [N.summation over (m=n+1)][a.sub.md] for 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D, (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)

The value of [[tau].sub.nd] represents the best possible further contribution to productivity in department d that can be realized across all N - n workers after worker n in the list (for 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D). The values of [[PHI].sub.jnde] facilitate the avoidance of redundant solutions. For example, suppose that worker j precedes worker n in the list of workers, and that worker j has already been assigned to department d and worker n is currently under consideration for assignment to department e. If [a.sub.ne] = [a.sub.je], [a.sub.nd] > [a.sub.jd], and d [not equal to] e, then we could get the same coverage in department e and better coverage in department d by switching the assignments of the two workers and, therefore, [[PHI].sub.jnde] is set to one to ensure that the partial assignment would be pruned. Similarly, if [a.sub.ne] = [a.sub.je], [a.sub.jd] = [a.sub.nd] and d [not equal to] e, then switching the assignments of workers n and j would have no effect; however, one of the partial assignments (j assigned to d and n assigned to e, or j assigned to e and n assigned to d) must be pursued. Hence, for this condition, we only prune if d > e. The steps of the branch-and-bound algorithm are as follows:

Step 0. INITIALIZE. Compute [[tau].sub.nd] for 1 [less than or equal to] n [less than or equal to] N and 1 [less than or equal to] d [less than or equal to] D. Compute [[PHI].sub.jnde] for 1 [less than or equal to] j < n [less than or equal to] N and 1 [less than or equal to] d, e [less than or equal to] D. Set n = 0, [[lambda].sub.m] = 0 for 1 [less than or equal to] m [less than or equal to] N, [lambda]* = [[[lambda].sub.1], [[lambda].sub.2],..., [[lambda].sub.N]], f([lambda]*) = 0, and [[gamma].sub.d] = 0 for 1 [less than or equal to] d [less than or equal to] D.

Step 1. ADVANCE. Set n = n + 1, d = 1, [[lambda].sub.n] = d and [[gamma].sub.d] = [[gamma].sub.d] + [a.sub.nd].

Step 2. SUBOPTIMAL ASSIGNMENT. If [a.sub.nd] = 0, then go to Step 6.

Step 3. REDUNDANCY. If [[PHI].sub.jned] = 1 for any 1 [less than or equal to] j [less than or equal to] n - 1 where e = [[lambda].sub.j], then go to Step 6.

Step 4. BOUND TEST Compute the following upper bound for a completed solution:

[f.sub.UB] = [D.summation over (d=1)][h.sub.d], (17)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

If [f.sub.UB] < f([lambda]*), then go to Step 6.

Step 5. COMPLETE ASSIGNMENT? If n [not equal to] N, then go to Step 1. Otherwise, set [lambda]* = [lambda] and store f([lambda]*).

Step 6. DISPENSATION. If d = D, then go to Step 8.

Step 7. DEPARTMENT REASSIGNMENT. Set [[gamma].sub.d] = [[gamma].sub.d] - [a.sub.nd]. Set d = d + 1, [[lambda].sub.n] = d and [[gamma].sub.d] = [[gamma].sub.d] + [a.sub.nd]. Return to Step 2.

Step 8. RETRACTION. Set [[lambda].sub.n] = 0, [[gamma].sub.d] = [[gamma].sub.d] - [a.sub.nd] and n = n - 1. If n = 0, then return the incumbent solution, which is an optimal solution, and STOP; otherwise, set d = [[lambda].sub.n] and return to Step 6.

Step 0 requires the preliminary computations of [[tau].sub.nd] and [[PHI].sub.jnde] parameters. The pointer for the branch-and-bound algorithm, which marks the worker whose assignment is under current consideration, is set to n = 0. An N-dimensional vector, [lambda], with elements [[lambda].sub.m] (1 [less than or equal to] m [less than or equal to] N) representing the department to which worker m is assigned is also initialized to zero. This vector is the initial incumbent solution, [lambda]*, with the corresponding objective value of f ([lambda]*) = 0. The productivity sums for each department, 1 [less than or equal to] d [less than or equal to] D are also initialized to zero at Step 0.

Step 1 advances the pointer to the next worker by setting n = n + 1, and this worker is assigned to the first department, d = 1. Department 1 is recorded as the placement of worker n (i.e., [[lambda].sub.n] = d) and the current productivity sum is incremented for the department via [[gamma].sub.d] = [[gamma].sub.d] + [a.sub.nd]. Steps 2 through 4 are the most important steps of the algorithm because they provide rules for pruning of partial assignments and prevent complete enumeration of all feasible solutions. Step 2 prunes a partial assignment if [a.sub.nd] = 0, and is based on the rationale that an assignment of worker n to department d when [a.sub.nd] = 0 ([a.sub.nd] [not equal to] 0) cannot possibly improve (worsen) the objective function. To avoid redundant solutions as described above, Step 3 prunes a partial assignment of worker n to department d if [[PHI].sub.jned] = 1 for any worker j earlier in the list assigned to department e = [[lambda].sub.j].

At Step 4, a partial assignment is pruned if it can be verified that a completed solution stemming from the partial assignment cannot achieve a utility value greater than the incumbent value, f ([lambda]*). The upper bound, [f.sub.UB], computed in Equations (17) and (18) combines the current departmental assignments ([[gamma].sub.d] 1 [less than or equal to] d [less than or equal to] D) and the greatest possible additional contribution to each department's assignment from workers n + 1,..., N ([[tau].sub.nd], 1 [less than or equal to] d [less than or equal to] D). Thus, [f.sub.UB] provides a best-case scenario for completion of the partial assignment, and if [f.sub.UB] < f ([lambda]*), then a pruning operation occurs. A partial assignment that makes it to Step 5 has passed all of the pruning tests. If n = N at Step 5, then the current partial assignment is, in fact, a complete assignment and is accepted as the new best-found solution. If n < N at Step 5, then processing returns to Step 1 for advancement in the search tree via assignment of the next worker in the list.

Step 6 controls the processing of pruned partial solutions, as well as completed solutions. If d < D at Step 6, then the department assignment for the current worker n is incremented to the next department in Step 7. Department reassignment in Step 7 requires removal of the productivity contribution from worker n in the current department ([[gamma].sub.d] = [[gamma].sub.d] - [a.sub.nd]), advancement of the department index (d = d + 1), and then addition of the productivity contribution for this new department assignment ([[gamma].sub.d] = [[gamma].sub.d] + [a.sub.nd]). If d = D at Step 6, then advancement of the department index for the current position is not possible and retraction occurs at Step 8 by backing up one worker in the sequence (n = n - 1). If n = 0, then all assignments have been explicitly or implicitly enumerated and the algorithm terminates with an optimal solution; otherwise, processing returns to Step 6 for dispensation of the partial assignment.

3.2. Strengths and limitations of the algorithm

In the worst case, the proposed branch-and-bound algorithm for solving the NWAP can devolve into exhaustive enumeration of all possible assignments Accordingly, we acknowledge that our proposed method can require significant computation time for some test problems. We have successfully solved NWAPs with up to N = 80 workers and D = 8 departments. Some problems of this size are solved in seconds, whereas other instances require several hours or more. This potential limitation notwithstanding, our computational experience with the algorithm has revealed that it is extremely efficient in obtaining optimal solutions for many problems of practical size.

One of the most important benefits of the branch-and-bound algorithm is that its deployment in computational experiments obviates any concerns about the potential confounding effects of algorithm suboptimality. When heuristic methods are used for computational investigation of workforce policies, there is always the potential for estimates of factor effects to be distorted by the differential performance of the heuristic across cells of the experimental design. Recognizing the potential for this circumstance, Campbell (1999) took great care in his experiments to demonstrate that his heuristic method was robust across experimental conditions. Given our use of the exact branch-and-bound procedure, such a demonstration is unnecessary.

Another positive aspect of the proposed branch-and-bound algorithm is that the basic structure is adaptable for different criteria and contexts. For example, we have developed a version of the branch-and-bound algorithm that uses Equation (8) instead of Equation (6) as the objective function of the NWAP. This program will be used for comparative purposes in Section 4. The algorithm could also be modified for objective function (9) or related criteria; however, the computational performances for such criteria are dependent on the quality of the bounds and pruning rules that can be constructed. The algorithm is also commensurate with those designed for partitioning problems, such as the minimum sum of squares clustering problem (Koontz e al., 1975; Klein and Aronson, 1991; Brusco and Stahl, 2005). These partitioning problems may also have practical relevance to certain types of workforce planning problems, such as the selection of cross-functional teams. To give an example, suppose we have a non-negative N x N matrix, with off-diagonal elements representing the dissimilarity between pairs of workers with respect to their skills. We might wish to form C teams from the data, where each team, 1 [less than or equal to] c [less than or equal to] C, has at least some minimum number of members. A typical objective criterion might be to form the teams so as to maximize the diversity within the groups (see, for example, Baker and Powell (2002) who address formation of student teams).

4. Numerical examples

4.1. Application to a previously published test problem

Campbell (1999) and Campbell and Diaby (2002) present an example of a test problem for the NWAP The problem consists of N = 20 workers and D = 4 departments, with department requirements of [r.sub.1] = 8.38, [r.sub.2] = 3.55, [r.sub.3] = 8.58 and [r.sub.4] = 4.00, and department utility weights of [w.sub.1] = 0.84, [w.sub.2] = 1.39, [w.sub.3] = 1.44 and [w.sub.4] = 0.94. Workers are cross-trained for one secondary department, and productivity coefficients for the secondary department vary from 0.4 to 1.0 in increments of 0.2. Campbell (1999) and Campbell and Diaby (2002) do not report solutions for the test problem. Therefore, we obtained solutions using both the linear assignment heuristic and the branch-and-bound algorithm. The linear assignment formulation was solved using CPLEX 6.5 (Anon, 1999), whereas the branch-and-bound program was written and implemented in Fortran. Solutions were obtained using a 2.2 GHz Pentium PC with 1 GB of RAM. The results are displayed in Table 1, with worker assignments shown in bold type.

The branch-and-bound algorithm obtained the optimal solution for the test problem in less than 0.01 seconds, yielding a utility value of [Z.sub.1] = 186.40908. The linear assignment heuristic produced a near-optimal utility value of [Z.sub.1] = 186.36452 in 0.25 seconds. The superior solution provided by the branch-and-bound method was achieved by assigning worker 2 to department 2 instead of department 4, and assigning worker 10 to department 1 instead of department 2. From a utility standpoint, the effect of this modification is to the reduce the weighted utility in department 4, as follows: [0.94((4.47)[.sup.2] - (4.47 - 3)[.sup.2])] - [0.94((4.47)[.sup.2] - (4.47 - 4)[.sup.2])] = -1.8236. The weighted utility in department 1, however, is improved by an amount computed as follows: [0.84((8.38)[.sup.2] - (8.38 - 5.8)[.sup.2])] - [0.84((8.38)[.sup.2] - (8.38 - 5.4)[.sup.2])] = +1.86816. Thus, the total utility improves by 1.86816 - 1.8236 = 0.04456, from 186.36452 to 186.40908.

To understand why the linear assignment heuristic fails to find the optimal solution, it is insightful to closely inspect the effect of reassigning worker 10 to department 1. We can perceive worker 10 as being assigned the seventh slot in department 1, joining workers 1, 5, 9, 13, 17 and 8, who occupy the first six slots. The key is that worker 8, placed in the sixth slot, has a productivity coefficient of 0.4 not unity. However, the linear assignment objective coefficient, [[DELTA].sub.17.sup.10], for placing worker 10 in slot 7 of department 1 is based on the maximum possible assignment up through the first six slots. Given that there are six ones in column d = 1, the linear assignment heuristic considers the effect of adding worker 10 to slot 7 to increase the productive workforce in department 1 from 6 to 6.4, not from 5.4 to 5.8 as is actually the case. The marginal increase in the utility of department 1 from an increase of productive workforce from 6 to 6.4 is [0.84((8.38)[.sup.2] - (8.38 - 6.4)[.sup.2])] - [0.84((8.38)[.sup.2] - (8.38 - 6)[.sup.2])] = +1.46496. This increase understates the true increase of 1.86816, and is too small to offset the productivity reduction in department 4.

We also applied a version of the branch-and-bound algorithm that uses Equation (8) as the objective criterion of the NWAP. The optimal solution was obtained in less than 0.01 seconds, and the resulting objective value is [Z.sub.3] = 0.24001. The assignment of workers to departments is the same as the branch-and-bound solution for criterion (6) shown on the right-hand side of Table 1, except that worker 8 is reassigned from department 1 to department 4, and worker 10 is reassigned from department 1 to department 2. These two workers were contributing a productivity of 0.4 to department 1, which has a relatively high demand and low weight. By moving worker 10 to department 2 with full productivity, the shortage is eliminated in this low-demand department that has relatively high weight. Similarly, assigning worker 8 to department 4 with full productivity will place four workers in that department, mitigating the shortage in this low-demand department. These changes are perfectly consistent with objective criterion (8), which penalizes shortages in low-demand departments more severely.

4.2. Application to a larger test problem

For a second illustration, we applied the linear assignment heuristic and branch-and-bound algorithm to a test problem that, although synthetically constructed, was based on data collected from the Maternal/Child Service Center of a large Florida hospital (Brusco, 1990). The input data for the test problem are summarized in the top panel of Table 2. The test problem consists of N = 69 nurses assigned to D = 5 departments. We assumed that roughly 70% of the nurses in each unit were cross-trained for one secondary nursing unit, and that a chaining structure was implemented. For example, 35.7% of the nurses in the Pediatric Unit were cross-trained for the Family Care Unit, and 35.7% of the nurses in the Pediatric Unit were cross-trained for the Neonatal Unit. Cross-trained nurses in the Family Care Unit could work in either the Neonatal Unit or the Stepdown Unit, etc. Productivity coefficients for the secondary department ranged from 0.4 to unity in increments of 0.2, and the department weights were assumed to be equal. The nominal shortage in the unit was 11.7%.

We applied the linear assignment heuristic and both versions of the branch-and-bound algorithm (objective criteria (6) and (8)) to this test problem, and the resulting assignments are shown in the bottom panel of Table 2. For criterion (6), the branch-and-bound algorithm obtained the optimal solution for the test problem in 0.47 seconds, yielding a utility value of [Z.sub.1] = 1449.836. Once again, the linear assignment heuristic produced a good, but suboptimal, utility value of [Z.sub.1] = 1448.44. To assess the value of cross-training, Campbell (1999) uses a measure (Vcross) that represents the percentage improvement in utility relative to no cross-training. If all nurses are assigned to their home nursing unit, then [Z.sub.1] = 1196.7344. Thus, the branch-and-bound algorithm and linear assignment heurstic provide utility improvements of 21.15 and 21.03%, respectively.

When using Equation (8) as the objective criterion for the NWAP, the branch-and-bound algorithm obtained the optimal solution for the test problem in 0.83 seconds, yielding a utility value of [Z.sub.3] = 0.09543. The bottom panel of Table 2 shows that, relative to the solutions for maximizing [Z.sub.1], the nursing unit assignments when minimizing [Z.sub.3] prevent large shortages from occurring in the units with lower demand. For example, we observe that the total productivity assignment for the Pediatrics and Stepdown Units are closer to the labor requirement when minimizing [Z.sub.3].

In hospital nursing, another common paradigm is to use a pool of float nurses who can be assigned to any nursing unit, usually with full productivity for each unit. If we assume that the N = 69 nurses formed a float pool, and could each work in any department, then the resulting solution would provide a baseline as a "best possible" scenario for cross-training. The optimal solution under this assumption yields [Z.sub.1] = 1466.3, and Vcross = 22.53%. Thus, for this particular test problem, it is encouraging to observe that cross-training provides an improvement in utility that is only slightly less than what is achievable from a float pool.

5. An experimental analysis of cross-training policies

5.1. Experimental design

The experimental design in this paper is an extended version of the study presented in Campbell (1999). Campbell's experiment consisted of seven factors, each measured at two levels, resulting in [2.sup.7] = 128 cells. He generated four replications per cell, resulting in a total of 512 unique test problems. We have added three additional factors, each measured at two levels. Therefore, our study consists of [2.sup.10] = 1024 cells and 1024 x 4 = 4096 unique test problems. Each test problem represents an instance of the NWAP, with Equation (6) as the objective function for consistency with Campbell's (1999) study. Each problem was solved to optimality using the branch-and-bound algorithm, which was implemented on a 3.4 GHz Pentium PC with 1 GB of RAM. The data collected were the total CPU time required to solve the test problem and Campbell's measure of the value of cross-training, Vcross = (f([lambda]*) - f([lambda]'))/f([lambda]'), where [lambda]' is an assignment of workers to their primary department. The Vcross results were the response measures for the ANOVA model that was used to evaluate the effects of the factors. The ten factors and their levels are listed in Table 3.

The first two factors, the number of departments (DEPTS) and the number of workers per department (WORKERS), effectively define the sizes of the cross-utilization problems. The levels for DEPTS were four and six, whereas the levels for WORKERS were four and eight. Thus, the smallest (largest) problems consisted of 16 (48) workers and four (six) departments. The third factor, the percentage of cross-trained workers, was introduced to estimate the effects of a partially cross-trained workforce. The levels of the third factor (PARTIAL) were 40 and 80%. The fourth factor (CHAINING) corresponded to the type of chaining policy. One level of this factor was strict cross-chaining, where secondary departments were systematically selected to build the chain. For the second level, fuzzy chaining, secondary departments for each worker were selected randomly, such that chaining would only arise from randomness. The number of secondary departments (NUMSEC) was the fifth factor, and was tested at levels of one and two departments. NUMSEC is a measure of the breadth of cross-training (see Brusco and Johns (1998)). To illustrate the interrelationship between factors 4 and 5, consider CHAINING = "strict" and NUMSEC = 2. This corresponds to what Hopp et al. (2004) term a "3-DSC" (three-department skill chaining) policy, where workers in department d were cross-trained for departments d + 1 and d + 2 for 1 [less than or equal to] d [less than or equal to] D - 2, workers in department D - 1 were cross-trained for departments D and 1, and workers in department D were cross-trained for departments 1 and 2.

In our experiments, worker productivity coefficients for the primary departmental assignment were always unity The sixth factor (PROD) corresponds to the minimum level of productivity for workers in their secondary departments. For the first level, the productivity for worker n in a secondary department was randomly selected (with equal probability) as 0.8 or unity. For the second level, we used equal probability selection among 0.4, 0.6, 0.8 and unity, as alternatives. The seventh factor, which Campbell (1999) termed "nominal shortage", represents the total shortage of labor across all departments. The two levels of this factor (NOMSHOR) were 10 and 20%. Departmental requirements for labor were generated from a normal distribution with a fixed mean and standard deviation for each department. The eighth factor (CV) controlled the dispersion of labor requirements via manipulation of the coefficient of variation, which was tested at levels of 0.3 and 0.6. The ninth factor (WEIGHTS) controlled for the relative importance or "criticality" of departments through a weight factor. For the first level of the ninth factor, each department received a weight of unity, whereas for the second level, weights were selected randomly from a uniform distribution on the interval [0.5, 1.5]. The tenth factor, absenteeism, was added to reflect that the need for cross-training can arise not only from unexpectedly high demand, but also from capacity shortfalls. The two levels of the tenth factor (ABSENT) were 10 and 0% (no absenteeism).

The additions to Campbell's (1999) design were factors 3 (PARTIAL), 4 (CHAINING), and 10 (ABSENT). We felt that a factor (PARTIAL) that allowed for some cross-trained and some non-crossed-trained workers for each department was appropriate in light of the recommendations of Pinker and Shumsky (2000), who warned against the degradation in service quality from using only cross-trained workers. The inclusion of the CHAINING factor was based on the demonstrated importance of this factor in other service contexts (Brusco and Johns, 1998; Inman et al., 2005). The ABSENT factor was included based on the noted importance of this factor in previous studies (Slomp and Molleman, 2002; Bokhorst et al., 2004).

5.2. Experimental results part I. The CPU time

Table 4 presents, for each level of each factor, the average improvements in utility relative to no cross-training, as well as the average CPU time required by the branch-and-bound algorithm. The average CPU time across all 4096 test problems was 2.05 seconds. Approximately 96% of the test problems were solved in less than a CPU second, and 99.24% of the test problems were solved in less than a CPU minute. The maximum CPU time across all test problems was 865.68 seconds. The principal factors influencing the CPU time were the number of departments (DEPTS) and the number of workers per department (WORKERS). Together, these factors jointly define the size of the test problem. For the smallest test problems, consisting of D = 4 departments and four workers per department, the average CPU time was less than 0.01 seconds. In contrast, for the largest test problems, consisting of six departments (D = 6) and eight workers per department, the average CPU time was 8.20 seconds.

Other factors with a strong influence on the CPU time were the extent of partial cross-training (PARTIAL), the number of secondary departments (NUMSEC) and, to a slightly lesser extent, the coefficient of variation (CV). Specifically, increases in the proportion of cross-trained workers and the number of secondary departments, along with a smaller coefficient of variation, tended to increase the computational difficulty. To illustrate, consider the 128 test problems in the experiment consisting of six departments, eight workers per department, 80% of the workforce cross-trained, two secondary departments and CV = 0.3. The average CPU time for these "difficult" test problems was 63.13 seconds.

5.3. Experimental results part II. The main effects for Vcross

A comparison of the Vcross means for each level of each factor in Table 4 provides some indication of the importance of each factor in influencing the cross-training benefits. We conducted a more formal analysis of Vcross using an ANOVA model with all main effects and two-way interactions. The ANOVA results included estimates of effect size (partial eta squared, [[eta].sub.p.sup.2]) for each term in the model. Consideration of effect sizes is important because all main effects were statistically significant, which is not surprising given the large number of test problems in the experiment. The resulting ANOVA table is displayed in Table 5 and contains all significant (p-value <0 .05) terms in the model.

The ANOVA results showed that the CV factor had the largest effect ([[eta].sub.p.sup.2] = 0.445) on utility improvement. At the smaller level of variation in labor requirements of CV = 0.3, the average improvement in utility was only 2.25%, which was less than one-fourth of the average improvement of 9.88% observed for CV = 0.6. The results for the CV factor are perfectly consistent with Campbell's findings, where CV was, by far, the most important factor affecting utility improvement. The natural explanation for these findings is that greater demand variation creates greater opportunity for cross-utilizing workers from low-demand departments in high-demand departments. Another interesting observation pertaining to the CV factor is that, whereas average utility improvement at CV = 0.6 was more than four times the improvement at CV = 0.3, the average CPU time for the branch-and-bound algorithm at CV = 0.6 was less than 1/25th of the average time for CV = 0.3. Thus, problems where cross-utilization was of greatest benefit were generally easier to solve.

The ABSENT factor had the second largest effect ([[eta].sub.p.sup.2] = 0.315) on utility improvement. A reduction in absenteeism from 10 to 0% provided an increase in labor capacity that facilitated an average improvement in Vcross from 3.17 to 8.96%. Thus, whereas CV was the most important demand factor influencing utility improvement, absenteeism was the most important capacity factor. Greater absenteeism reduces utility; however, this should not be misinterpreted as a lack of importance for cross-training in the presence of greater absenteeism. Two other capacity factors, PARTIAL ([[eta].sub.p.sup.2] = 0.209) and NUMSEC ([[eta].sub.p.sup.2] = 0.123) had the third and fourth largest effect sizes, respectively. An increase in the proportion of cross-trained workers from 40 to 80% resulted in an average improvement in Vcross from 3.87 to 8.26%. Similarly, an increase from one to two secondary departments yielded an average improvement in Vcross from 4.47 to 7.66%. This latter finding is in marked contrast to Campbell's results, which showed a negligible improvement in Vcross when moving from one to three secondary departments. We believe that this disparity between our results and Campbell's is likely attributable to the fact that his study did not consider absenteeism, partial cross-training or chaining of secondary departments.

The WORKERS factor had the fifth largest effect on utility improvement ([[eta].sub.p.sup.2] = 0.093). The average utility improvements realized for four and eight workers per department were 4.70 and 7.43%, respectively. These findings are also contradictory to those reported by Campbell, who found a slightly greater utility improvement at five workers per department (9.48%) than at ten workers per department (8.45%). A plausible explanation for this discrepancy is the presence of the PARTIAL and ABSENT factors in our study, which were not included in Campbell's study.

It is also insightful to consider some of the factors with small effect sizes. For example, although the main effects for the DEPTS, NOMSHOR, WEIGHTS and CHAINING factors were statistically significant at the [alpha] = 0.05 level, their effect sizes were each less than [[eta].sub.p.sup.2] = 0.008. The lack of relative importance of the first three of these factors is consistent with Campbell's findings. However, the finding for the CHAINING factor is new. The average Vcross improvements for strict and fuzzy chaining differed only slightly, at 6.39 and 5.74%, respectively. From a practical standpoint, it was interesting to observe that service managers can realize comparable improvements in utility with either strict or fuzzy chaining. This is a valuable finding. Whereas some service environments might be able to create strict chaining either through training programs or hiring practices, others might be more at the mercy of the labor market. For example, in a multilingual call center environment, it is not practical to "train" agents in multiple languages (Iravani et al., 2007); however, our results provide the comforting finding that a natural mix of agents speaking different pairs of languages can still yield exceptional benefits.

5.4. Experimental results part III. The interaction effects for Vcross

Some of the most interesting findings from our experimental analysis corresponded to two-way interaction effects. The NUMSEC x CV term had the largest interaction effect ([[eta].sub.p.sup.2] = 0.061) on utility improvement. A practical interpretation of this interaction term is that having an additional secondary department was more important for improving Vcross when CV = 0.6, relative to the lower demand variation level of CV = 0.3. At CV = 0.3, the average improvement in Vcross with one secondary department was 1.74%, and there was a slight increase to 2.76% when there were two secondary departments. In contrast, at CV = 0.6, the average improvement in Vcross with one secondary department was 7.20%, but there was a sizable increase to 12.56% when there were two secondary departments.

The PARTIAL x CV term had the second largest interaction effect ([[eta].sub.p.sup.2] = 0.048) on utility improvement, and the interpretation is similar to that of the NUMSEC x CV term. Specifically, having a larger percentage of cross-trained workers was more important when CV was high. At CV = 0.3, the average improvement in Vcross with 40% of the workforce cross-trained was 1.01%, and there was an increase to 3.49% when 80% of the workforce was cross-trained. In contrast, at CV = 0.6, the average improvement in Vcross with 40% of the workforce cross-trained was 6.73%, and there was a tremendous increase to 13.03% when 80% of the workforce was cross-trained.

The WORKERS factor had two strong interaction terms in our experiment: (i) WORKERS x PARTIAL ([[eta].sub.p.sup.2] = 0.015); and (ii) WORKERS x ABSENT ([[eta].sub.p.sup.2] = 0.018). Given that the PARTIAL and ABSENT factors were not included in Campbell's study, these interactions help to explain why our findings for the main effect of WORKERS differed from his results. An increased number of workers per department was more important when only 40% of the workforce was cross-trained, and when there was a 10% absentee rate. At PARTIAL = 40%, the average improvement in Vcross with four workers per department was 1.99%, and there was a fairly sizable increase to 5.76% when there were eight workers per department. However, at PARTIAL = 80%, the corresponding Vcross improvement when moving from four to eight workers per department was only from 7.42% to 9.10%. Similarly, at ABSENT = 10%, the average improvement in Vcross with four workers per department was 1.23%, and there was a noteworthy increase to 5.11% when there were eight workers per department. However, at ABSENT = 0%, the corresponding Vcross improvement when moving from four to eight workers per department was only from 8.17% to 9.74%. The relatively smaller effects of the WORKERS factor at PARTIAL = 80% and ABSENT = 0% are consistent with Campbell's findings, which were based on PARTIAL = 100% and ABSENT = 0% throughout his entire study. Our results, however, suggest that the WORKERS factor has a much stronger effect at different levels of partial cross-training and absenteeism.

5.5. Experimental results part IV. Alternative computation of Vcross in the case of absenteeism

The experimental results reported in Tables 4 and 5 and discussed in Sections 5.3 and 5.4 assume that f([lambda]') in the Vcross expression is computed prior to consideration of absent workers. Based on this assumption, increased absenteeism has an adverse effect on the benefits realized from cross-training, resulting in a reduction of average Vcross from 8.96 to 3.17% when moving from 0 to 10% absenteeism. An alternative approach is to compute f([lambda]') after adjusting for absent workers in each department. This alternative computation procedure does not effect the results for ABSENT = 0%; however, the average Vcross value for ABSENT = 10% increases markedly to 15.21%. It is important to clarify that this result does not imply that there is greater overall utility when absenteeism is present. Instead, the correct interpretation is that greater absenteeism provides more opportunity for a larger percentage utility improvement to be realized from cross-training when f([lambda]') is computed after adjustment for absent workers.

We re-ran the ANOVA analyses on the data obtained from the alternative computation of Vcross. The results were strikingly consistent with those reported in Table 5. For example, the six largest main effects were CV ([[eta].sub.p.sup.2] = 0.509), ABSENT ([[eta].sub.p.sup.2] = 0.297), PARTIAL ([[eta].sub.p.sup.2] = 0.195), NUMSEC ([[eta].sub.p.sup.2] = 0.111), WORKERS ([[eta].sub.p.sup.2] = 0.047), PROD ([[eta].sub.p.sup.2] = 0.044), respectively. This is precisely the same order as the six largest main effects in Table 5. The most important two-way interactions obtained using the alternative computation of Vcross were also consistent with those in Table 5, with mostly minor differences in ordering with respect to effect size. Based on these results, we are confident that our major findings are not an artifact of the method for computing Vcross.

6. Conclusions

The principal methodological contribution of our paper is the provision of a branch-and-bound algorithm for solving an important NWAP originally posed by Campbell (1999). Whereas Campbell (1999) and Campbell and Diaby (2002) relied on heuristics for their experiments on the same problem, our proposed method typically produced guaranteed optimal solutions in a few seconds. The development and implementation of exact algorithms are valuable because they enable managers and researchers to analyze policies without any uncertainty about the relative performance of heuristics across cells of an experiment. We acknowledge that, like most branch-and-bound procedures, our algorithm does tend to total enumeration when the bounds are not sharp. Nevertheless, we were encouraged by its ability to obtain optimal solutions for problems of practical size. Improvements of the branch-and-bound methodology could expand the size of allocation problems that can be solved optimally.

Through a broadening of Campbell's (1999) experiment, we were able to uncover some new findings within the context of the NWAP. For example, we found that absenteeism, partial cross-training, cross-training breadth and the number of workers per department were important factors affecting the utility of worker allocations. These latter two factors exhibited much less importance in Campbell's (1999) study, presumably because his original study did not consider absenteeism, partial cross-training and chaining as experimental factors. Another interesting finding from our experiment was that strict and fuzzy chaining provided comparable improvements in utility. Several important two-way interactions were also identified. The two largest interaction effects suggested that greater cross-training breadth and a workforce with a greater proportion of cross-trained workers were especially important when demand variation was high.

The computational experiment offered in this paper could be adapted in a variety of ways. Assuming that effective algorithms can be developed for alternative objective criteria, a comparison of cross-training policy effects across objective criteria would be interesting. Another extension would be to use the algorithm and experimental results to provide prescriptive information. For example, Slomp and Molleman (2002) conducted analyses to determine which employees should be the next to be cross-trained. The use of the NWAP to determine precisely how and where cross-training should be expanded (and possibly where it should be contracted) could prove quite valuable from a cost perspective.

Acknowledgement

I am extremely grateful for the helpful comments of three anonymous reviewers, which led to significant improvements in this article.

References

Abernathy, W.J., Baloff, N., Hershey, J.C. and Wandel, S. (1973) A three-stage manpower planning and scheduling model--a service sector example. Operations Research, 21, 693-711.

Andrews, B.H. and Cunningham, S.M. (1995) L.L. Bean improves call center forecasting. Interfaces, 25, 1-13.

Anon (1999) ILOG CPLEX 6.5 User's Manual, ILOG, Inc, Mountain View, CA.

Baker, K.R. and Powell, S.G. (2002) Methods for assigning students to groups: a study of alternative objective functions. Journal of the Operational Research Society, 53, 397-404.

Bard, J.F. (2004) Staff scheduling in high volume service facilities with downgrading. IIE Transactions, 36, 983-997.

Bard, J.F. and Purnomo, H.W. (2005) Hospital-wide reactive scheduling of nurses with preference considerations. IIE Transactions, 37, 589-608.

Bard, J.F. and Wan, L. (2005) Weekly scheduling in the service industry: an application to mail processing and distribution centers. IIE Transactions, 37, 379-396.

Batta, R., Berman, O. and Wang, Q. (2007) Balancing staffing and switching costs in a service center with flexible servers. European Journal of Operational Research, 177, 924-938.

Bechtold, S.E. (1981) Work-force scheduling for arbitrary cyclic demands. Journal of Operations Management, 1, 89-107.

Bokhorst, J.A.C., Slomp, J. and Molleman, E. (2004) Development and evaluation of cross-training policies for manufacturing teams. IIE Transactions, 36, 969-984.

Brusco, M.J. (1990) An evaluation of nurse staffing policies in a constrained labor environment. Doctoral dissertation, Florida State University, Tallahassee, FL 32306, USA.

Brusco, M.J. and Jacobs, L.W. (1998) Personnel tour scheduling when starting-time restrictions are present. Management Science, 44, 534-547.

Brusco, M.J. and Jacobs, L.W. (2000) Optimal models for meal-break and start-time flexibility in continuous tour scheduling. Management Science, 46, 1630-1641.

Brusco, M.J. and Johns, T.R. (1998) Staffing a multiskilled workforce with varying levels of productivity: an analysis of cross-training policies. Decision Sciences, 29, 499-515.

Brusco, M.J. and Stahl, S. (2005) Branch-and-Bound Applications in Combinatorial Data Analysis, Springer, New York. NY, ch. 2.

Campbell, G.M. (1999) Cross-utilization of workers whose capabilities differ. Management Science, 45, 722-732.

Campbell, G.M. and Diaby, M. (2002) Development and evaluation of an assignment heuristic for allocating cross-trained workers. European Journal of Operational Research, 138, 9-20.

Connor, R.J. (1960) A hospital inpatient classification system. Doctoral dissertation, Johns Hopkins University, Baltimore, MD.

Easton, F.F. and Rossin, D.F. (1991) Equivalent alternate solutions for the tour scheduling problem. Decision Sciences, 22, 985-1007.

Feyerherm, A.M. and Kirk, W.R. (1964) Effect of census variation on nursing activity patterns. Hospitals, 38, 62-74.

Graves, S.C. and Tomlin, B.T. (2003) Process flexibility in supply chains. Management Science, 49, 907-919.

Hershey, J.C., Abernathy, W.J. and Baloff, N. (1974) Comparison of nurse allocation policies--a Monte Carlo model. Decision Sciences, 5, 58-72.

Hopp, W.J., Tekin, E. and Van Oyen, M.P. (2004) Benefits of skill chaining in serial production lines with cross-trained workers. Management Science, 50, 83-98.

Hopp, W.J. and Van Oyen, M.P. (2004) Agile workforce evaluation: a framework for cross-training and coordination. IIE Transactions, 36, 919-940.

Hueter, J. and Swart, W. (1998) An integrated labor-management system for Taco Bell. Interfaces, 28, 75-91.

Inman, R.R., Blumenfeld, D.E. and Ko, A. (2005) Cross-training hospital nurses to reduce staffing costs. Health Care Management Review, 30, 116-123.

Iravani, S.M., Kolfal, B. and Van Oyen, M.P. (2007) Call center labor cross-training: it's a small world after all. Management Science, 53, 1102-1112.

Iravani, S.M., Van Oyen, M.P. and Sims, K.T. (2005) Structural flexibility: a new perspective on the design of manufacturing and service operations. Management Science, 51, 151-166.

Jack, E.P. and Powers, T.L. (2004) Volume flexible strategies in health services: a research framework. Production and Operations Management, 13, 230-244.

Jacobs, L.W. and Brusco, M.J. (1996) Overlapping start-time bands in implicit tour scheduling. Management Science, 42, 1247-1259.

Jarrah, A., Bard, J. and de Silva, A. (1994) Solving large-scale tour scheduling problems. Management Science, 40, 1124-1144.

Jordan, W.C. and Graves, S.C. (1995) Principles on the benefits of manufacturing process flexibility Management Science, 41, 577-594.

Jordan, W.C., Inman, R.R. and Blumenfeld, D.E. (2004) Chained cross-training of workers for robust performance. IIE Transactions, 36, 953-967.

Klein, G. and Aronson, J.E. (1991) Optimal clustering: A model and method. Naval Research Logistics, 38, 447-461.

Koontz, W.L.G., Narendra, P.M. and Fukunaga, K. (1975) A branch and bound clustering algorithm. IEEE Transactions on Computers, C-24, 908-915.

Mason, A.J., Ryan, D.M. and Panton, D.M. (1998) Integrated simulation, heuristic, and optimisation approaches to staff scheduling. Operations Research, 46, 161-175.

Pinker, E.J. and Shumsky, R.A. (2000) The efficiency-quality tradeoff of cross trained workers. Manufacturing and Services Operations Management, 2, 32-48.

Slomp, J. and Molleman, E. (2002) Cross-training policies and team performance. International Journal of Production Research, 40, 1193-1219.

Stafford, B.J. and Schlotfeldt, R.M. (1960) Nursing service staffing and quality of nursing care. Nursing Research, 9, 149-154.

Trivedi, V.M. and Warner, D.M. (1976) A branch and bound algorithm for optimum allocation of float nurses. Management Science, 22, 972-981.

Warner, D.M. and Prawda, J. (1972) A mathematical programming model for scheduling nursing personnel in a hospital. Management Science, 19, 411-422.

Wright, P.D., Bretthauer, K.M. and Cote, M.J. (2006) Reexamining the nurse scheduling problem: staffing ratios and nursing shortages. Decision Sciences, 37, 39-70.

Biographies

Michael J. Brusco is the Synovus Professor of Marketing and Operations Research at Florida State University. His research focuses on the development of optimal and heuristic solution procedures for combinatorial optimization problems related to scheduling, location, layout and data analysis. He is a past member of the board of directors for the Classification Society of North America, and currently serves on the editorial board of the Journal of Classification.

MICHAEL J. BRUSCO

Department of Marketing, College of Business, Florida State University, Tallahassee, FL 32306-1110, USA

E-mail: mbrusco@cob.fsu.edu

Received October 2006 and accepted June 2007

Table 1. Linear assignment heuristic and branch-and-bound solutions for
the test problem presented in Campbell (1999, p. 726)

           Linear assignment
           heuristic solution*         Branch-and-bound solution*
Worker     d = 1  d = 2  d = 3  d = 4  d = 1  d = 2  d = 3  d = 4

n = 1      1.0#   0.0    1.0    0.0    1.0#   0.0    1.0    0.0
n = 2      0.0    1.0    0.0    1.0#   0.0    1.0#   0.0    1.0
n = 3      0.4    0.0    1.0#   0.0    0.4    0.0    1.0#   0.0
n = 4      0.0    0.6    0.0    1.0#   0.0    0.6    0.0    1.0#
n = 5      1.0#   0.0    0.0    0.6    1.0#   0.0    0.0    0.6
n = 6      0.0    1.0#   0.0    0.6    0.0    1.0#   0.0    0.6
n = 7      1.0    0.0    1.0#   0.0    1.0    0.0    1.0#   0.0
n = 8      0.4#   0.0    0.0    1.0    0.4#   0.0    0.0    1.0
n = 9      1.0#   0.0    0.4    0.0    1.0#   0.0    0.4    0.0
n = 10     0.4    1.0#   0.0    0.0    0.4#   1.0    0.0    0.0
n = 11     0.0    0.0    1.0#   1.0    0.0    0.0    1.0#   1.0
n = 12     0.0    1.0    0.0    1.0#   0.0    1.0    0.0    1.0#
n = 13     1.0#   0.0    0.4    0.0    1.0#   0.0    0.4    0.0
n = 14     0.0    1.0    0.4#   0.0    0.0    1.0    0.4#   0.0
n = 15     0.8    0.0    1.0#   0.0    0.8    0.0    1.0#   0.0
n = 16     0.0    0.8    0.0    1.0#   0.0    0.8    0.0    1.0#
n = 17     1.0#   0.0    0.0    1.0    1.0#   0.0    0.0    1.0
n = 18     0.0    1.0#   0.0    0.6    0.0    1.0#   0.0    0.6
n = 19     0.0    1.0    1.0#   0.0    0.0    1.0    1.0#   0.0
n = 20     0.0    0.0    1.0#   1.0    0.0    0.0    1.0#   1.0
[p.sub.d]  5.40   3.00   6.40   4.00   5.80   3.00   6.40   3.00
[r.sub.d]  8.38   3.55   8.58   4.47   8.38   3.55   8.58   4.47
[w.sub.d]  0.84   1.39   1.44   0.94   0.84   1.39   1.44   0.94
           Utility, [Z.sub.1] =        Utility, [Z.sub.1] =
           186.36452                   186.40908

*Values in bold indicate the department to which the worker is assigned.

Note: The values indicated with # indicate the department to which the
worker is assigned.

Table 2. The top portion presents the problem characteristics for an
illustrative example based on data from the Maternal/Child Service
Center of a Florida hospital (Brusco, 1990). The bottom portion presents
departmental productivity assignments obtained from three different
solution procedures

Nursing unit number                      d = 1       d = 2   d = 3
Nursing unit name                        Pediatrics  Family  Neonatal
                                                     Care
Number of RNs                            14          16      24
Percentage of cross-trained nurses       71.4        68.8    75.0
Secondary departments                     2, 3        3, 4    4, 5
Department weight ([w.sub.d])             1.0         1.0     1.0
Department requirement ([r.sub.d])       10.42       20.12   28.25
Department productivity from maximizing   8.8        18.2    25.6
  [Z.sub.1] using the linear assignment
  heuristic
Department productivity from maximizing   8.8        17.8    25.4
  [Z.sub.1] using the branch-and-bound
  algorithm
Department productivity from minimizing  10.0        16.8    21.4
  [Z.sub.3] using the branch-and-bound
  algorithm

Nursing unit number                      d = 4     d = 5
Nursing unit name                        Stepdown  Pediatric Sp. Care
Number of RNs                             3        12
Percentage of cross-trained nurses       66.7      75.0
Secondary departments                     5, 1      1, 2
Department weight ([w.sub.d])             1.0       1.0
Department requirement ([r.sub.d])        8.82      9.46
Department productivity from maximizing   4.6       9.0
  [Z.sub.1] using the linear assignment
  heuristic
Department productivity from maximizing   5.4       8.0
  [Z.sub.1] using the branch-and-bound
  algorithm
Department productivity from minimizing   8.2       9.0
  [Z.sub.3] using the branch-and-bound
  algorithm

Table 3. Factors and factor levels for the computational experiment

           Description                            Level 1  Level 2

Factor 1   Number of departments (DEPTS)           4        6
Factor 2   Number of workers per department        4        8
             (WORKERS)
Factor 3   Percentage of workforce cross-trained  40%      80%
             (PARTIAL)
Factor 4   Type of cross-chaining (CHAINING)      Strict   Fuzzy
Factor 5   Number of secondary departments         1        2
             (NUMSEC)
Factor 6   Minimum productivity (PROD)             0.8      0.4
Factor 7   Nominal shortage (NOMSHOR)             10%      20%
Factor 8   Coefficient of variation for            0.3      0.6
             requirements (CV)
Factor 9   Department weights (WEIGHTS)           Equal    Unequal
Factor 10  Percentage of workers absent (ABSENT)  10%       0%

Table 4. Experimental results: average utility improvements and CPU
times

Factor    Levels                        Vcross* (%)  CPU time (seconds)

DEPTS     D = 4                         6.26         0.00
          D = 6                         5.87         4.10
WORKERS   4 per department              4.70         0.00
          8 per department              7.43         4.10
PARTIAL   40% of workers cross-trained  3.87         0.00
          80% of workers cross-trained  8.26         4.10
CHAINING  Strict                        6.39         0.18
          Fuzzy                         5.74         3.93
NUMSEC    One secondary department      4.47         0.00
          Two secondary department      7.66         4.11
PROD      Minimum = 0.8                 7.03         0.93
          Minimum = 0.4                 5.10         3.17
NOMSHOR   10%                           5.80         1.19
          20%                           6.33         2.91
CV        0.3                           2.25         3.96
          0.6                           9.88         0.15
WEIGHTS   Equal                         5.68         2.44
          Unequal                       6.45         1.67
ABSENT    10% absenteeism               3.17         1.21
          No absenteeism                8.96         2.90
OVERALL                                 6.07         2.05

*Vcross is the percentage improvement in utility relative to no
cross-utilization.

Table 5. Experimental results: ANOVA table for Vcross with effect sizes*

Source              Sum of squares  df    Mean square  F        p-value

Corrected model     15.24557          55   0.2772       150.44  0.000
Intercept           15.06693           1  15.0669      8177.19  0.000
DEPTS                0.01598           1   0.0160         8.67  0.003
WORKERS              0.75952           1   0.7595       412.21  0.000
PARTIAL              1.97267           1   1.9727      1070.61  0.000
CHAINING             0.04351           1   0.0435        23.61  0.000
NUMSEC               1.04280           1   1.0428       565.95  0.000
PROD                 0.38527           1   0.3853       209.09  0.000
NOMSHOR              0.02967           1   0.0297        16.10  0.000
CV                   5.95661           1   5.9566      3232.80  0.000
WEIGHTS              0.06102           1   0.0610        33.12  0.000
ABSENT               3.42402           1   3.4240      1858.30  0.000
DEPTS x CV           0.04183           1   0.0418        22.70  0.000
DEPTS x ABSENT       0.03057           1   0.0306        16.59  0.000
WORKERS x PARTIAL    0.11225           1   0.1122        60.92  0.000
WORKERS x CHAINING   0.00905           1   0.0091         4.91  0.027
WORKERS x CV         0.05242           1   0.0524        28.45  0.000
WORKERS x ABSENT     0.13694           1   0.1369        74.32  0.000
PARTIAL x NOMSHOR    0.01290           1   0.0129         7.00  0.008
PARTIAL x CV         0.37524           1   0.3752       203.65  0.000
PARTIAL x ABSENT     0.01802           1   0.0180         9.78  0.002
CHAINING x NUMSEC    0.03168           1   0.0317        17.19  0.000
CHAINING x CV        0.01946           1   0.0195        10.56  0.001
NUMSEC x CV          0.48304           1   0.4830       262.16  0.000
PROD x CV            0.07925           1   0.0793        43.01  0.000
NOMSHOR x CV         0.01700           1   0.0170         9.23  0.002
NOMSHOR x ABSENT     0.04063           1   0.0406        22.05  0.000
CV x ABSENT          0.05044           1   0.0504        27.38  0.000
Error                7.44393        4040   0.0018
Total               37.75643        4096
Corrected total     22.68950        4095

Source              Effect size [[eta].sub.p.sup.2]

Corrected model     0.672
Intercept           0.669
DEPTS               0.002
WORKERS             0.093
PARTIAL             0.209
CHAINING            0.006
NUMSEC              0.123
PROD                0.049
NOMSHOR             0.004
CV                  0.445
WEIGHTS             0.008
ABSENT              0.315
DEPTS x CV          0.006
DEPTS x ABSENT      0.004
WORKERS x PARTIAL   0.015
WORKERS x CHAINING  0.001
WORKERS x CV        0.007
WORKERS x ABSENT    0.018
PARTIAL x NOMSHOR   0.002
PARTIAL x CV        0.048
PARTIAL x ABSENT    0.002
CHAINING x NUMSEC   0.004
CHAINING x CV       0.003
NUMSEC x CV         0.061
PROD x CV           0.011
NOMSHOR x CV        0.002
NOMSHOR x ABSENT    0.005
CV x ABSENT         0.007
Error
Total
Corrected total

Only main effects and interaction terms that were statistically
significant (p < 0.05) are shown.