Dynamic Assignment of Flexible Service Resources

2.1. Stochastic Dynamic Programming Formulation

Given the set of available resources and their capabilities, and the demand distribution and profit margin for each job type, the flexible resource deployment problem entails deciding which incoming jobs (service requests) to accept in each period before the service date and what resource to assign to each accepted job in order to maximize the total expected profit. We model this problem as a stochastic dynamic program in which stages correspond to periods of the finite decision horizon. Let J={1, 2, …, m} be the set of m different job types offered by the firm. Each accepted job of type j∈J yields a profit margin of π_j to the training firm. We index the job types in decreasing order of profitability, i.e., π ₁≥π ₂ … ≥π_m . Consistent with revenue management models that seek to maximize profits using a given set of resources, we assume that the profit margin of a job is the same regardless of the resource type assigned to this job. (Later, we selectively discuss how some of our results and methods extend to problems with resource‐dependent profit contributions.) Let R={1, 2, …, l} denote the set of l different resource types that the firm employs, each capable of performing a specified subset of job types. For each resource type r∈R, let J _r ⊆J denote the subset of job types that resource type r can perform. Conversely, for each job type j∈J, let R _j ⊆R be the subset of resource types that can perform type‐j jobs. The resource capability sets J _r represent the firm's resource flexibility structure. We refer to any resource type that can perform only one job type as a specialized resource; at the other extreme, a flexible resource that can perform all job types is called a versatile resource. We are primarily concerned with solving problems with general resource flexibility structures containing some flexible resource types with overlapping but non‐dominated capabilities, but we do consider certain special flexibility structures to characterize the optimal policy and highlight the challenges of solving problems with general flexibility structure.

The definition of job and resource types, with the associated capability sets, permits modeling a wide variety of situations. For instance, if profit margins vary by customer class or if certain customers have specific resource preferences, we can capture these features by defining separate job types for such customers. Similarly, although price is not a decision variable, we can incorporate different pre‐determined price categories (analogous to fare classes in airline reservations) for the same service by introducing one job type corresponding to each price. We can also include additional costs (e.g., goodwill loss) for not accepting jobs. Specifically, if α_j denotes the penalty cost for rejecting a type‐j job, we can account for this cost by redefining the parameter π_j for type‐j jobs as the profit margin for this job type plus the penalty α_j .

We consider dynamic decisions over a decision horizon consisting of T periods, indexed backwards from t=T to 1. Period T denotes the start of the decision horizon, and period 1 is the last period for customer requests before the service date. As noted earlier, the choice of period length, which can vary during the decision horizon, depends on the desired customer response lead time and determines the extent to which demands can be accumulated before making acceptance and assignment decisions. In the limit, by choosing very short period lengths, we can model situations in which the firm must make acceptance and assignment decisions as soon as each job arrives.

For r∈R and t=1, 2, …, T, let n_rt be the number of available (unassigned) type‐r resources at the start of period t, and define n _t ={n _1t , n _2t , …, n_lt } as the resource availability vector at time t. The firm's initial resource capacity, at the start of the decision horizon, is n _T ={n _1T , n _2T , …, n_lT }. Let D _jt be the random demand for type‐j jobs in period t; D _t ={D _1t , D _2t , …, D_mt } is the period‐t demand vector. Let d _t ={d _1t , d _2t , …, d_mt } be the vector of realized demands d_jt for type‐j jobs in period t. P(D _t =d _t ) is the joint probability that the demand in period t is d _t . We do not assume any particular functional form for the demand distribution (demand can even be non‐stationary, arrive in batches, or correlated among job types), but require demands across time periods to be independent.

The stochastic dynamic programming formulation of the flexible resource deployment problem consists of T stages, one for each period t=1, 2, …, T. The resource availability vector n _t ={n_rt } and realized demand vector d _t ={d_jt } describe the state of the system in period t. Define u_t (n _t , d _t ) as the maximum expected profit‐to‐go at stage t for the state (n _t , d _t ). Then, we can express the value function v_t (n _t ) associated with having n _t resources at the start of period t, before observing the actual demand in this period, as follows: 1

The profit‐to‐go u_t (n _t , d _t ) depends on the job acceptance and resource assignment decisions in period t, after observing the actual demand d _t , and the value function for the remaining unassigned resources at the end of the period. For each j∈J and r∈R _j , let x_jrt be the number of type‐r resources assigned to type‐j jobs in period t after observing demand. These assignment decisions must satisfy:

(i)

the demand constraints for all j∈J, specifying that we cannot assign more resources to any job type than the actual demand for that job type in period t, and

Let denote the action set containing all the feasible assignments for resources in period t, given the state (n _t , d _t ). Then, using e _k to denote the kth unit vector, we can express the maximum profit‐to‐go function u_t (n _t , d _t ), for all periods t=1, 2, …, T, as follows: 2

That is, the profit‐to‐go u_t (n _t , d _t ) is the sum of the rewards collected in period t plus the maximum expected profit over the remaining time horizon. Given the firm's starting resource capacity n _T , the maximum expected profit over the decision horizon is v_T (n _T ). Computing this value entails recursively applying (2) from t=1 to t=T, with the boundary condition v ₀(n ₀)=0 for all n ₀≤n _T , specifying that the value of any unassigned resources left over at the end of the horizon is zero.

Finding the exact policy, i.e., the profit‐maximizing dynamic policy for optimal job acceptance and resource assignment decisions at each period, is computationally intractable because the state space grows exponentially with the number of jobs, resources, and time periods. Next, we consider a deterministic version of the problem that provides upper bounds on the maximum expected profit for the stochastic problem and also underlies approximate policies.

2.2. Deterministic Acceptance and Resource Assignment Problem

Suppose, at period t, we know with certainty the cumulative future demand cd_jt of each job type j∈J over the remaining t periods, and let cd _t ={cd _1t ,cd _2t , …, cd_mt }. Then, given the set of available resources n _t , the resource deployment decision reduces to the following deterministic demand acceptance and resource allocation problem, with decision variables y_jr denoting the total number of type‐r resources assigned to type‐j jobs in the remaining t periods: 3 subject to: 4 5 6

Given the solution y={y_jr } to this problem, we can determine the job acceptance and resource assignments x _jrt′, for each period t′=t, …, 1, in many different ways (e.g., prefer accepting jobs that arrived earlier, and assign the allocated resource types in arbitrary order) to satisfy, for all j∈J, the demand requirements and resource allocations for all r∈R _j .

Since this model assumes that future demand is known, we refer to it as the Deterministic demand selection and resource assignment (DD) model. We can transform the optimization problem (3)–(6) into a single‐commodity minimum cost network flow problem defined over a network containing m job nodes, l resource nodes, and an additional source node. Since the minimum cost network flow model has an integer optimal solution if demands and capacities are integer‐valued, we do not need to explicitly impose integrality restrictions on the y‐variables.

The DD problem is easy to solve for certain special resource flexibility structures. Consider, for instance, a system containing m resource types, indexed as r=1, 2, …, m, with resource type r capable of performing job type j=r and all less profitable (higher‐indexed) job types, i.e., with J _r ={r, r+1, …, m}. Thus, lower‐indexed resource types are more flexible than higher‐indexed resource types. We refer to this special resource flexibility configuration as the Downward flexibility structure. For this structure, a greedy procedure that sequentially considers job types in order of increasing index j (decreasing profitability), and accepts as many jobs as possible using the remaining resources yields the optimal solution to the DD problem. In contrast, with general flexibility structure, since resources do not have a complete ordering in terms of their flexibility, making demand acceptance and resource assignment decisions even with known demand requires solving the linear program (3)–(6). The difficulty is compounded when we consider dynamic decisions with unknown future demand.

For the stochastic problem, the DD model, applied using appropriate point estimates of demand, may serve to guide resource allocation decisions for approximate policies. Moreover, as we discuss next, this model is also useful for generating upper bounds on the optimal value of the stochastic problem. First, suppose we solve this model for every possible realization cd _t of the stochastic cumulative demand vector CD _t ={CD _1t ,CD _2t , …, CD_mt }, and obtain the corresponding optimal value U_t (n _t , cd _t ). Multiplying this value by the probability of realizing the cumulative demand vector cd _t and summing over all demand scenarios gives the expected PI value E[U_t (n _t , CD _t )]. This value is an upper bound on the expected profit v_t (n _t ). Next, for each j∈J, suppose we replace cd_jt in the demand constraint (4) with the expected value of the cumulative demand E(CD_jt ) for type‐j jobs from period t to the end of the decision horizon. We refer to this version of the DD model as the expected demand model. Let be the optimal value of its linear programming relaxation. The following proposition relates this value to the expected PI value E[U_t (n _t , CD _t )] and the profit v_t (n _t ) for the exact dynamic policy.

Proposition 1. .

Proof. The optimal value U_t (n _t , cd _t ) of the linear program (3)–(6) is concave in cd _t . Therefore, applying Jensen's inequality, we get . Moreover, given the actual demand realization vector cd _t , the optimal value U_t (n _t , cd _t ) equals or exceeds the profit obtained using any dynamic policy (with unknown demand). Hence, the expected PI value is no less than the expected profit using the exact dynamic policy, i.e., . □ 

Proposition 1 states that the optimal value of the expected demand model is an upper bound on the expected PI value which in turn overestimates the expected profit of the exact dynamic policy. Since finding the exact policy is intractable, Proposition 1 provides a means to assess the effectiveness of approximate policies by comparing their expected profits to either of these upper bounds. Bertsimas and Popescu (2003) developed similar bounds for a network revenue management problem. Next, we analyze the structure of the exact dynamic policy for a special case, and later (in section 4) develop approximate policies for the general problem.

4.1. Preliminaries and Notation

To streamline the presentation of our dynamic resource assignment policies, we introduce some additional notation and terminology. For each job type j∈J, let s_j be the index of the specialized resource type that can perform only this job type, and let RF _j =R _j \{s_j } be the index set of flexible resource types that can perform type‐j jobs. RF=R\{s_j ∀j∈J} is the index set of all flexible resource types that can each perform more than one job type.

As we noted in section 3, whenever specialized type‐s_j resources are available, it is optimal to accept and assign arriving type‐j jobs to these resources. Accordingly, after observing the demand in every period, each of our policies first assigns any available specialized resources to the incoming jobs. Hence, if d_jt denotes the actual demand for type‐j jobs and is the number of available type‐s_j resources at the start of period t, then this initial “Assign and update specialized resources” step accepts units of the incoming type‐j jobs to specialized type‐s_j resources, and updates for every job type j∈J. Let denote the remaining or residual demand for type‐j jobs in period t. With CD_jt denoting the (random) cumulative demand for type‐j jobs from period t onwards, define as the residual cumulative demand from period t onwards after we use up all the available type‐s_j specialized resources.

4.2. DCA Policy

The DCA policy addresses the challenge of determining which subset of resource types will jointly constrain future job acceptances by using the expected demand model of section 2.2 to plan a tentative allocation of resource types to current and future demand. This linear program captures well the capacity interactions among resource types within a general resource flexibility structure, but does not consider demand stochasticity. However, from Proposition 1 we know that the optimal value of the expected demand model is an upper bound on the true value function for the stochastic problem. For other stochastic dynamic programming problems, researchers (e.g., Bertsekas and Tsitsiklis 1998, Bertsimas and Popescu 2003) have previously proposed and successfully applied a similar tactic of replacing the true value function with a deterministic approximation obtained by assuming fixed values for the stochastic variables.

For the dynamic flexible resource deployment problem, the DCA policy consists of two main steps in each period t. In the first step, we apply the deterministic optimization model, using the number of residual jobs on hand plus the expected value of residual cumulative demand from the next period (t−1) onwards as type‐j demand. The solution to this profit‐maximizing problem provides a proposed mix of job types to be accepted using the available resources. Since this model combines current and future demands and does not distinguish between using alternative resource types, we employ a second optimization step to decide how many of the current jobs to accept and which resources to assign to these accepted jobs. This latter model uses shadow price information from the previous solution to identify and preserve “valuable” resources for future periods while accepting the same total number of jobs as the resource allocation plan from the first step. A formal description of the DCA policy follows.

DCA Policy:

Step 0:

Assign and update specialized resources.

The resource assignment model's objective function (13) maximizes the net profit from jobs accepted this period, where we define the net profit of assigning a type‐r resource to a type‐j job as the profit margin π_j of the job minus the shadow price σ_rt of the resource. Constraints (14) and (15) specify that we cannot assign more than and resources, respectively, to current and future jobs of each type. Constraints (16) are resource capacity constraints, while constraints (17) ensure that the total number of accepted jobs (for current and future demands) for each job type j equals the value ξ_j chosen by the optimal solution to model [DSP]. The model judiciously assigns resources to current jobs, preserving resource types with high value (shadow price) for future use. For a problem with m job types and l resource types, we can represent both problem [DSP] and problem [RAP] as minimum cost network flow problems defined over appropriate networks with O(m+l) nodes and O(ml) arcs. The assignment of resources to current jobs in Steps 0 and 2 require O(ml) effort. The overall complexity of the DCA method is governed by the time to solve the network flow problems which is O{(ml)²(m+l)log(m+l)} per period (Orlin 1997). For problems in which job profitability varies with the resource assigned to the job, we can readily adapt the DCA method by replacing the parameters π_j in the objective functions (9) and (13) of the optimization models [DSP] and [RAP] with resource‐dependent profit margins.

4.3. NCR Policy

For the Star flexibility structure that we analyzed in section 3, the exact policy accepts an incoming type‐j job only if the number of available flexible resources at any period t exceeds a state‐dependent threshold value. This value represents the amount of versatile capacity we wish to reserve to meet the future demand for all the job types that are more profitable than type‐j jobs. The NCR policy extends this approach to general resource structures. Specifically, for each job type j, we first determine the desired total capacity (of all capable resource types) to be reserved for future demand (after period t) of all job types that are more profitable than type‐j jobs, and then determine which specific resource types to reserve. We refer to this capacity reservation scheme as a nested policy since, instead of reserving capacities separately for each job type j, it pools the capacity needed for the more‐profitable job types 1, 2, …, (j−1). Determining the exact threshold function, i.e., optimal capacity reservations, for this nested scheme is an intractable problem. We, therefore, use an approximate newsvendor‐like method to determine the capacity reservations, and then solve an optimization problem to decide which specific resource types to reserve for future demand.

The capacity reservation choice depends on the tradeoff between accepting a current job to capture its profit versus preserving the resource for possible future use to perform a more profitable job. Since this tradeoff is analogous to the balance between overage and underage costs in the traditional newsvendor problem, we use a critical fractile approach to determine the desired capacity reservations. Researchers have previously used the newsvendor principle to develop approximate policies for other revenue management problems. For instance, to allocate a common pool of seats (single resource type) among multiple fare classes (job types), Belobaba (1989) proposed setting the booking limit for each fare class using a newsvendor model.

To motivate our capacity reservation method, we first explore the capacity reservation decision for a two‐period problem with two job types, and three corresponding resource types—specialized type‐1 and type‐2 resources for job types 1 and 2, respectively, and versatile type‐3 resources. In the first period (t=2), after observing the demands for type‐1 and type‐2 jobs, the optimal policy accepts as many type‐1 jobs as possible using available type‐1 and type‐3 resources, and assigns any available specialized type‐2 resources to the incoming type‐2 jobs. Let n ₃>0 be the number of remaining versatile type‐3 resources available after these initial assignments. (To simplify the notation, we omit the time index for the state variables.) We wish to determine how many of these n ₃ resources to reserve for future type‐1 jobs; this decision will determine how many of the current residual type‐2 jobs to accept and assign to versatile resources (in the first period). Let denote the residual type‐2 jobs after assigning specialized type‐2 resources. (If , then all n ₃ versatile resources are carried forward to the next period.) To focus on the tradeoff between using available versatile resources to process current type‐2 jobs versus future type‐1 jobs, we consider the most adverse situation in which only type‐1 jobs arrive in the second period (t=1). Let D ₁ denote the unknown demand for type‐1 jobs in the second period, and define as the residual type‐1 demand after assigning the n ₁ specialized type‐1 resources carried forward from the first period. For our analysis, we assume that is a continuous random variable, and let be its cumulative distribution function. If we decide to reserve Q versatile resources for use in the second period, with , then we can accept (n ₃−Q) of the residual type‐2 jobs in the first period and assign versatile resources to these accepted jobs. Thus, the maximum expected profit‐to‐go after observing demand in the first period but before accepting any residual type‐2 jobs is 19

The unconstrained (without resource limits) optimal quantity Q ₁ to maximize the expected profit satisfies the classical newsvendor‐type condition , or 20

Accounting for the resource constraints , the optimal number of versatile resources to reserve for type 1 jobs in the second period is if Q ₁<, and is min{Q ₁, n ₃} otherwise.

Since extending this characterization of the exact reservation policy to a system with more than two job types and with general resource flexibility structure is analytically intractable, we adapt the approach using some approximations. First, in each period t, we treat the demand during the remaining (t−1) periods as an aggregate demand that occurs in a single future period. Second, analogous to the previous assumption that only type‐1 jobs arrive in the second period, we only consider the future demand for type‐j and more profitable jobs when deciding the capacity reservation for these jobs. Finally, for deciding whether to accept a current type‐(j+1) job, instead of making a separate capacity reservation for each job type that is more profitable than job type (j+1), we determine a combined reservation for all the more‐profitable job types k=1, 2, …, j, effectively treating these job types together as a composite job type with an appropriate weighted average profit parameter, as discussed below. (For airline seat reservations, researchers have distinguished between analogous partitioned and nested booking limits except that these limits refer to allocation of versatile or downward flexible resources whereas we are concerned with determining the desired total capacity, over multiple resource types with arbitrary flexibility structure, to allocate for various job types.) For a multi‐class newsvendor problem, Sen and Zhang (1999) showed numerically that reserving capacity separately for each demand class is inferior to using a combined reservation for all more‐profitable demand classes. Our preliminary computational experiments (not reported here) also confirmed that, for the flexible resource deployment problem, our combined reservation approach yields higher profits than a separate reservation for each job type.

For j=1, 2, …, m−1, let Q_j be the desired number of resources that we wish to reserve for future arrivals of jobs of type‐1 through type‐j. We now discuss how to adapt expression (20) (for Q ₁ in the two job‐type problem) to compute Q_j in the m job‐type problem. First, since Q_j will be used to decide whether to accept a current type‐(j+1) job, the “overage” cost or opportunity cost of over‐reserving capacity for future jobs is the profit margin π _j+1 of the current job. Hence, we replace π ₂ in (20) with π _j+1. Next, for the two job‐type problem, the value π ₁ in expression (20) represents the unit profit margin of the more‐profitable job for which we are reserving capacity. In the context of our approximation, we replace this value with the following demand‐weighted average profit for all the job types that are more profitable than job type ( j+1): 21

For k=1, 2, …, j, expression (21) uses the expected future residual demand of type‐k jobs from period (t−1) onwards as the weight for the type‐k job's profit margin π _k. Finally, instead of the uncertain future residual demand (D ₁−n ₁)⁺ of the single more‐profitable job type (i.e., type 1) in expression (20), we aggregate the future residual demands for all the job types k=1, 2, …, j that are more profitable than job type‐(j+1). Using these principles, we compute Q_j in period t as: 22

In the context of airline reservations, the expected marginal seat revenue (EMSR‐b) heuristic (Belobaba 1989) uses the same approach to determine protection levels for controlling the usage of a single resource type. Since expression (22) does not consider the currently available resource capacities, we may not have as many resources as we would like to reserve. We therefore refer to Q_j as the aggregate capacity reservation target for type‐j and more profitable jobs. For the two job‐type problem, since we have only a single flexible resource type (i.e., type 3), with n ₃ available units, we could easily determine the actual reservation as either or min{Q ₁, n ₃}. With general flexibility structure, we have many different resource types that can perform some or all of the job types k=1, 2, …, j. Hence, we face the additional challenge of deciding how many of each specific resource type to reserve for future jobs in order to meet the aggregate capacity reservation target Q_j . To account for the actual available capacities, we employ a capacity reservation linear program [CRP] that simultaneously considers the aggregate capacity targets for all j, and attempts to achieve reservations as close as possible to (but not exceeding) the target values, giving preference to reservations for more profitable job types. The NCR policy first solves this linear program to determine the number of jobs of each type to accept in the current period, and later (in the second step) selects the specific resources to assign to the current accepted jobs based upon the resource optimal shadow prices for [CRP]. A formal statement of the procedure follows:

NCR Policy:

Step 0:

Assign and update specialized resources.

Unlike the DCA algorithm, which uses the expected future residual demand of each job type j to guide planned resource allocations for future demand, model [CRP] reserves resources based on the target aggregate capacity reservation values Q_j . The w_jr values represent the planned (tentative) allocation of type‐r resources for future type‐j jobs. Since the objective function includes the profits from these allocations, the optimal solution will favor reserving capacity (as much as possible, using the currently available mix of resources) for more profitable job types, subject to the nested reservation limits Q_j . Model [CRP] can have alternate optimal solutions that differ in their allocation of capacity between current and future type‐j jobs, for each j. Hence, in Step 2, we first set the number of current type‐j jobs to be accepted, u_jt , equal to the smaller of the current residual demand or the total number of resources assigned by the [CRP] solution to type‐j jobs, and then assign less valuable resources, based on resource shadow prices, to these accepted jobs. As in the DCA method, we can represent the optimization model [CRP] as an equivalent minimum cost network flow problem on a network with O(m+l) nodes and O(ml) arcs which can be solved in O{(ml)²(m+l)log(m+l)} time per period. Again, the assignment of resources to current jobs in Steps 0 and 2 require O(ml) effort in total, and so the NCR method has the same computational complexity as the DCA method.

4.4. BCR Policy

Unlike the DCA policy, the NCR policy considers demand stochasticity when determining the capacity reservation targets Q_j to decide whether to accept current jobs. However, by using nested targets, the approach ignores the actual flexibility structure, effectively assuming that a unit of capacity that is not assigned to a current type‐j job can be used to process any of the more‐profitable job types k=1, 2, …,  or j−1. But, depending on the resource structure, the acceptance decision for the type‐j job may have no impact on the available capacity for some of these more‐profitable job types, in which case we should not consider the future demand for such jobs when making acceptance decisions for type‐j jobs. Ideally, when considering the use of a type‐r resource for a current type‐j job, we must examine whether this assignment can create or exacerbate a future capacity “bottleneck” for any subset of more‐profitable job types. With general flexibility structures, each job type can be performed by multiple alternative resource types that have arbitrary overlapping capabilities. Hence, bottlenecks are not associated with individual job or resource types, but are rather defined by groups or subsets of job types and the corresponding resource types that can perform any job type in the subset. As we explain below, our BCR policy makes simultaneous job acceptance and assignment decisions based on capacity reservation targets for such bottlenecks.

The BCR policy considers job types j in order of decreasing profitability and resource types r∈RF _j in order of increasing value (to be defined later). To decide whether to assign a type‐r resource to a current type‐j job, the method first identifies subsets S of more‐profitable job types for which capacity can become a future bottleneck due to this r‐to‐j assignment. Such subsets include not only the more‐profitable job types that the type‐r resource can perform, but also other job types that are indirectly affected by the r‐to‐j assignment due to job‐resource chaining effects induced by resource flexibility. (Jordan and Graves 1995 introduced chaining in the context of flexible manufacturing; Graves and Tomlin 2003, Hopp et al. 2004, and others have since extended and applied this concept to various contexts.) We defer discussion on how to identify such subsets in order to first define what we mean by a bottleneck. For any subset of job types S⊆J, let denote the subset of flexible resource types that can perform one or more job types in S. Following our approach for the NCR policy, for any subset S, with π_k >π_j for all k∈S, we define a capacity reservation value Q _S,j as the number of resources that we would like to reserve for future demand of job types in S instead of assigning them to current type‐j jobs. We say that the job subset S is a bottleneck relative to job type j if the total number of currently available resources to process jobs in S is less than or equal to Q _S,j , i.e., if . To compute Q _S,j , we apply the previous critical fractile approach by first defining the following weighted profit parameter for job types in S, with the expected future residual demand for each job type in S as the weight for that job type's profit margin: 28

Then, as in expression (22), we define: 29

To assess the possible impact of assigning a type‐r resource to a current type‐j job on the available capacity for more profitable job types in the future, we should consider all job subsets S satisfying two conditions: S contains only job types k<j that are more profitable than job type j, and r∈RF_S . We refer to such subsets as <j, r>‐subsets. If any such subset S is a bottleneck, i.e., if , then we should not assign a type‐r resource to the type‐j job. If none of the <j, r>‐subsets are bottlenecks, then resource type r is a candidate for assignment to a current type‐j job; in this case, we refer to resource type r as a non‐bottleneck resource.

Rather than enumerating every possible subset S of job types 1, 2, …, j−1, and then checking if r∈RF_S , we reduce the enumeration effort using the following approach. Consider a flexibility graph GF(j) containing one node for every currently available flexible resource type r∈RF with n_rt >0, and one node for every job type k<j. The graph contains edge (r′, k) if k∈J _r′ , i.e., if type‐r′ resources can perform type‐k jobs. We say that a type‐k job is reachable from a type‐r resource if this flexibility graph contains at least one path from the resource node r to the job node k. Observe that, even if the type‐r resource cannot directly perform a type‐k job, having one extra unit of a type‐r resource permits accepting an extra unit of any type‐k job that is reachable from r through a process of successive resource substitution for the intermediate job types in the path connecting r to k in GF(j). With this construction, each <j, r>‐subset S is a subset of the reachable jobs from the resource node r.

Next, we discuss a resource valuation metric that the BCR policy uses to select from among alternative resource types that are available for assignment to a current type‐j job. Define as an indicator for the tightness of capacity for type‐j jobs. Observe that 0≤θ_j ≤1 (if at least one currently available resource can perform job type j), with higher values of θ indicating tighter capacity for type‐j jobs. We now define the value of a type‐r resource as 30

Roughly, interpreting θ_j as the likelihood that a type‐j job will be assigned a type‐r flexible resource, the resource value τ_r represents the expected profit generated by this resource. This metric accounts for both the profit margins of the job types that a type‐r resource can perform and the capacity tightness for each of these job types. Moreover, it assigns higher value to resources that are more flexible: for any pair of resource types r and r′ with , the definition (30) of relative value ensures that , as desired.

Returning to the overall BCR policy, at each period t, after assigning specialized resources, the method considers job types j=1, 2, …, m in decreasing profit sequence. For each j, the method first attempts to assign resource types r∈RF _j for which the type‐j job is most profitable. Let denote these preferred resource types for type‐j jobs. If RP _j contains more than one resource type, the method assigns resources in increasing order of the resource value τ_r . When all resources in RP _j are exhausted, the method identifies all non‐bottleneck resource types M _j ⊆RF _j \RP _j that can process job type j. The BCR policy considers these resource types r in decreasing order of slack capacity (i.e., smallest excess capacity over all subsets S of reachable jobs that are more profitable than type j), and assigns slack resources until they are exhausted or all type‐j jobs have been accepted. A formal description of the method follows:

BCR Policy:

Step 0:

Assign and update specialized resources.

Compute the value τ_r of each resource type r∈RF.

Step 1:

For j=1, 2, …, m,

•

 For each preferred resource type r∈RP _j , in increasing order of value τ_r :

  Accept jobs and assign type‐r resources to these jobs;

  Update and .

Step 2:

For j=1, 2, …, m,

  Set M _j =∅. M _j represents the set of non‐bottleneck resources for job type j.

  Step 2.1: For every resource type r∈RF _j \RP _j with n_rt >0,

•

construct the flexibility graph GF(j), and determine the job types j′<j that are reachable from resource type r. Let L _jr denote the set of these job types.

   Let be the slack for resource r. If b_jr >0, update .

  Step 2.2: If M _j is empty, go to next job type j in Step 2. Otherwise, let .

  Step 2.3: Assign units of type‐r′ resources to type‐j jobs.

       Update the remaining current demand () and resource levels ().

       If , go to next job type in Step 2. Otherwise, update the list of non‐bottleneck resources (), and return to Step 2.2.

If j=m, set for all r∈RF.

By considering all possible subsets of more‐profitable (and reachable) job types at each iteration j of Step 2, the BCR policy generalizes the NCR policy (which considers only one “nested” subset consisting of all job types that are more profitable than type j). In the worst case, Step 2 of the BCR algorithm must enumerate all reachable job subsets for every pair of job and resource types, and hence the complexity of the algorithm is O(2 ^mml) per period. Although the BCR policy must assess the capacity‐demand match for many more job subsets than the NCR policy, in our computational tests the BCR policy required only a modest amount of additional computational time compared with the NCR and DCA policies. Note that the bottleneck set can change dynamically depending on the demand realizations and acceptance/assignment decisions in each period. The BCR policy accounts for this “shifting” bottleneck phenomenon by recomputing the bottleneck set in every period.

We conclude this discussion of approximate policies by noting that, although we have presented each policy in the discrete‐time setting, these methods also apply when firms need to make job acceptance and assignment decisions as soon as each individual job arrives. Moreover, as we illustrate in section 6, we can also adapt the methods to situations where acceptance decisions are dynamic but resource assignments can be deferred until the end of the decision horizon. Next, we describe our computational experiments and results to evaluate the performance of the three policies.

5.1. Problem Generation and Experimental Design

We test the performance of different policies over many different problem scenarios, obtained by varying six key problem characteristics that can influence problem difficulty.

1. Number of job types. Problems with more job types are harder to solve both due to larger problem dimensions and more complex job acceptance and resource assignment tradeoffs. For our computations, we consider problems with three to five job types.

2. Resource flexibility structure. For a problem with m job types, we can have up to (2 ^m −1) resource types. If different resource types have large overlap in terms of their capabilities, then the number of available resource choices for each job increases, making the problem more challenging. We expect problems with intermediate levels of flexibility to be more difficult than the two extreme configurations containing either only specialized resources or only versatile resources. Iravani et al. (2005) propose indices to characterize the level of flexibility of manufacturing and service systems and measure their ability to respond to variability. Since acceptance and assignment decisions are trivial when the system contains specialized resources, we do not include any specialized resources in our test problems. To understand the influence of flexibility structure, we consider the following canonical structures:

•

k‐Chain. For 1<k<m, this structure consists of m resource types that can each perform k“consecutive” (with wrap‐around) job types, i.e., for r=1, 2, …, m, resource type r can perform job type, r, (r+1) mod m, …, (r+k−1) mod m. Chains permit sequential reallocation of capacity among different job types, and so are effective for handling variability in the mix of demand across job types. Jordan and Graves (1995) showed that a 2‐Chain structure meets almost as much total demand as a system in which all resources are versatile. Chou et al. (2008) and others have since studied similar desirable properties of k‐Chains, for k>2.

The Versatile structure has the highest level of flexibility, and so will yield the largest profit. The relative profitability of the other structures depends on the number of resources of each type as well as the relative demand for different job types. With equal distribution of capacities and demand across resource and job types, the k‐All structure is superior to the k‐Chain structure.

3. Decision frequency. For a given length of the decision horizon, increasing the decision frequency corresponds to making each period shorter so as to respond quicker to customer requests. Since resource deployment decisions must now be made with less demand information, expected profits will decline as decision frequency increases. We consider problem scenarios with five to 60 decision periods, keeping the horizon length and demand rate constant.

4. Capacity tightness. With ample resources, we can accept most, if not all, jobs. At the other extreme, when capacity is very tight, all but the most profitable jobs must be rejected. We, therefore, expect dynamic resource deployment problems with intermediate levels of capacity tightness to be most difficult. We define the capacity tightness index η as the ratio of the total number of resources initially available to the total expected demand (over all job types) during the horizon. For our experiments, we randomly select η from a user‐specified interval [η _min, η _max]. We consider scenarios with moderately tight and loose capacities.

5. Relative profitability of job types. When some job types are much more profitable than others, a “wrong” acceptance or resource assignment decision can significantly decrease the relative profit performance of any approximate policy. To study this effect, we vary the ratio of profits for successive job types. For j=1, 2, …, m−1, let denote the reward ratio for type‐j jobs relative to type‐(j+1) jobs. We select γ_j randomly from a user‐specified interval [γ _min, γ _max]. By varying γ _min and γ _max, we can increase or decrease the relative profit margins of job types. For our experiments, we consider three ranges of reward ratios to capture small, moderate, and large differences in profit margins.

6. Demand distribution. As demand variability increases, the performance of the approximate policies may deteriorate. To permit proper profit comparisons across scenarios, we fix the total expected demand for all job types during the entire decision horizon; let κ denote this expected value. In our base case, arrivals of different job types follow independent Poisson processes, with mean λ_j =κ/mT for all j∈J in each period t=1, 2, …, T. To study the effect of demand variability on policy performance, we also consider certain discrete demand distributions with small, medium, and large variances (relative to the mean). Further, we consider both balanced and unbalanced expected demand across job types.

The preceding six key problem characteristics, and their associated parameters, provide a convenient framework for specifying problem scenarios. We refer to each combination of settings for the six dimensions as a scenario. In all, our computational study considers 25 different problem scenarios. For each scenario, we randomly generate 10,000 random problem instances, and average the results (relative profits) over these instances to quantify the performance (relative profits) of each policy. To generate a particular problem instance for a given scenario, we first randomly select a value for the capacity tightness index η from [η _min, η _max], and set the total number of resources equal to ηκ, where κ is the total expected demand of all job types over the decision horizon. Each of these resources is equally likely to be designated as one of the l resource types in the chosen flexibility structure. To determine the profit margin for each job type, we normalize π_m =1; then, for j=m−1, …, 1, we randomly select γ _j from the interval [γ _min, γ _max], and set π_j =γ_jπ _j+1. Finally, we generate the number of arrivals of each job type in every period t of the decision horizon using the chosen demand distribution. We set κ=60 for all scenarios, and assume that demand is stationary.

For every problem instance, we applied the DCA, NCR, and BCR policies and determined the PI solution by solving the DD model described in section 2.2. For problem instances with three and four job types, we also computed the exact policy (for the problem with general flexibility structure and multiple job arrivals in each period) by solving the dynamic program (1) and (2) using backward induction. Finally, to provide a benchmark for comparing the profits of our optimization‐based flexible resource deployment policies, we applied the following FCFS policy to every problem instance. In each period t, this policy considers job types j in order of decreasing profit, accepting as many of the arriving type‐j jobs as possible using available resources, i.e., the policy accepts jobs, where n_rt is the number of currently available type‐r resources. To assign specific resources to accepted type‐j jobs, the FCFS method favors using resources r∈R _j that are less flexible, i.e., that can perform fewer job types (Chevalier and Van den Schrieck 2008 applied this rule for skills‐based routing in a call center). When there are ties, i.e., if two or more available resource types in R _j can perform the same number of job types, the method prefers assigning resources that perform less‐profitable job types. Specifically, for each resource type r, let A_r be the characteristic 0–1 m‐vector with element a_rj =1 if resource type r can perform job type j, and 0 otherwise. Then, among all the available resource types that can perform the same number of job types, the FCFS method assigns resources in lexicographically increasing order of A_r . We implemented the problem generator and various resource deployment policies in the C programming language, using CPLEX 8.1 for the optimization subroutines.

We assess the economic value of each of our approximate policies by comparing their profits with those obtained by the FCFS policy. The profit of the exact policy or the PI upper bound serves to validate the quality of the approximate solutions. We divide our computational results into two sets. In the first set, we focus on determining whether our policies are effective and identifying the best among the three approximate methods. We find that the BCR policy consistently generates near‐optimal profits and outperforms the other policies. Our second set of computations tests the robustness of the approximate policies' performance to variations in problem characteristics such as resource flexibility, capacity tightness, demand variability and balance, relative profitability of jobs, and decision frequency.

5.2. Effectiveness of the Approximate Policies

Our first set of computations seeks to address three main questions: which among our three approximate policies performs best, what benefit do these policies provide relative to the FCFS policy, and does the best policy generate near‐optimal profits? For this purpose, we consider problem scenarios with three to five job types, and various flexibility structures. For problems with three and four job types, we are able to determine the exact policy using dynamic programming, whereas for five job‐type problems, we use the PI upper bound to assess the quality of the approximate solutions. We fix the number of decision periods at T=10, consider moderately tight resource capacities (η∈[0.6, 0.9]) and moderate reward ratios (γ∈[1.5, 2.5]) across job types, and simulate Poisson arrivals with equal expected demand across job types. Such scenarios with balanced demand across job types and equal expected resource capacity for each job type are likely to be the most challenging since all job types have equally tight capacities and contend for flexible resources.

Table 1 summarizes the average optimality gaps between the approximate and exact solution values for problems with three and four job types for various flexibility structures. With three job types (m=3), the 2‐All flexibility structure is the same as the 2‐Chain structure. For problems with more than three job types, to avoid spreading the resources among too many resource types, we do not consider the Complete or (m−1)‐All flexibility structures. We measure the performance of each approximate policy for any scenario as the gap (averaged over 10,000 instances) between the profits of the exact and approximate policies expressed as a percentage of the exact policy's profit.

OPEN IN VIEWER

Table 1

 Policy Effectiveness for Three and Four Job‐Type Scenarios

No. of job types (m)	Resource structure					% of FCFS‐to‐exact gap closed by BCR
		FCFS	DCA	NCR	BCR
3	2‐Chain	14.23	1.92	1.46	1.05	92.62	3.23
	Complete	16.52	2.58	2.14	1.59	90.38	1.42
	Versatile	18.77	2.88	1.67	1.66	91.13	1.27
	Average %	16.51	2.46	1.76	1.43	91.88	1.97
4	2‐Chain	25.77	3.92	2.13	1.70	93.40	5.15
	2‐All	26.86	3.84	1.96	1.46	94.56	4.13
	3‐Chain	28.74	3.40	1.92	1.61	94.40	2.66
	Versatile	28.14	3.94	1.06	1.06	96.23	1.64
	Average %	27.38	3.78	1.77	1.46	94.65	3.40

FCFS, first‐come first‐served; DCA, Deterministic Capacity Allocation; NCR, Nested Capacity Reservation; BCR, Bottleneck Capacity Reservation; PI, perfect‐information.

The results in Table 1 show that all three policies generate good solutions, with optimality gaps of less than 4% for every scenario. (For each scenario, Table 1 shows the smallest gap among the approximate policies in bold.) Among our three policies, the NCR policy is uniformly superior to the DCA policy, but the BCR policy consistently outperforms both the DCA and NCR policies in every problem scenario, generating profits that are within 1.7 % of the exact policy's profits for every scenario. The average gap for the BCR policy, relative to the exact policy, is less than 1.5% for both three and four job types. This near‐optimal performance of the BCR policy (confirmed by our later experiments) underscores the importance of considering both demand stochasticity and shifting resource bottlenecks to decide job acceptance and resource assignments.

Comparing the gaps for our approximate policies with those for the FCFS policy reinforces the importance of implementing an optimization‐based policy to guide dynamic resource deployment decisions. The profits generated by the FCFS policy are 14.2% to 28.7% lower than those of the exact policy, and the BCR policy closes over 90% of this gap. The last column of Table 1 shows the percentage gaps between the PI solution values and exact profits. The PI values overestimate the exact profits by as much as 5%, with the PI upper bound becoming weaker as the number of job types increases from three to four. As resource flexibility increases (e.g., comparing the results for 2‐Chain and Versatile resource structures), the PI‐to‐Exact gaps decrease, implying that the exact policy is able to achieve almost as much profit as decisions based on perfect information.

Table 2 reports the results for five job‐type problem scenarios. (For each scenario, Table 2 shows the smallest gap among the approximate policies in bold.) Since finding the exact policy for these problems is computationally prohibitive, we use the PI value as the benchmark to assess the relative performance of our three approximate policies and the FCFS policy. As before, for all scenarios, the BCR policy provides the highest average profit among the three approximate policies. The percentage gaps in Table 2 are notably higher than those in Table 1 because we measure these gaps relative to the PI upper bound rather than the exact value. And, as we noted previously, this upper bound appears to become looser as the number of job types increases. Assuming that the PI‐to‐exact gap increases by 1 to 2% when the number of job types increases from four to five (as it does when number of job types increase from three to four), the results in Table 2 suggest that the actual optimality gaps (relative to the exact policy's profits) of our approximate policies should be comparable to those in Table 1. We also note that, as the problem size increases, the resource structure becomes more complex, vastly increasing the number of decision options and hence the possibility of sub‐optimal choices at each stage. This increased complexity adversely affects performance, particularly for the DCA policy.

OPEN IN VIEWER

Table 2

 Policy Effectiveness (Relative to PI Upper Bound) for Five Job‐Type Scenarios

Resource structure
	FCFS	DCA	NCR	BCR
2‐Chain	37.50	10.13	7.93	7.29
2‐All	39.16	8.54	6.95	6.55
3‐Chain	40.76	7.77	6.31	6.35
3‐All	40.66	7.21	4.87	4.64
4‐Chain	39.16	6.18	4.33	4.24
Versatile	41.81	5.34	4.16	4.16
Average %	39.84	7.53	5.76	5.54

FCFS, first‐come first‐served; DCA, Deterministic Capacity Allocation; NCR, Nested Capacity Reservation; BCR, Bottleneck Capacity Reservation; PI, perfect‐information.

5.3. Robustness of Policy Performance: Impact of Key Problem Dimensions

Having established the effectiveness of our approximate policies, we now study their robustness with respect to the key problem dimensions. For this purpose, we consider variations around a base scenario with three job types, Complete flexibility structure, Poisson arrivals with balanced demand, moderately tight capacity availability η (∈[0.6, 0.9]), moderate reward ratios γ (∈[1.5, 2.5]), and ten periods in the decision horizon. We vary the base scenario, one dimension at a time, to assess the effect on policy performance of capacity tightness, demand characteristics, relative profit margins, and decision frequency. Figure 1 (a–e) displays the percentage gaps, averaged over 10,000 problem instances, between the approximate policies' profits and the exact value for each scenario variant. The results for the base scenario are displayed as grey bars.

OPEN IN VIEWER

Figure 1

 Robustness of Policy Performance

As before, across all the 12 additional scenarios covered by these experiments, the results of Figure 1 show the same consistent pattern of relative performance as in section 5.2: the BCR policy is superior to the NCR policy, which in turn outperforms the DCA policy. For the 12 new scenarios, the average BCR‐to‐Exact gap is only 1.19%, validating the robustness of the BCR policy. We next discuss the results for each of the five scenario variants.

Figure 1(a) compares the gaps for the base case, with moderately tight capacities, and a scenario with moderately loose capacities (η∈[0.9, 1.2]). As capacity increases, more incoming jobs can be accepted, and so we expect the approximate policies to achieve profits closer to the exact profits. Figure 1(a) confirms this performance improvement (reduction in gaps) for the loose capacity scenario. The FCFS‐to‐Exact gap also reduces (to 5.8%) when capacity becomes looser, implying that using our optimization‐based policy is more important when capacity is tight.

Figure 1(b) and (c) address two aspects of the demand process that can affect policy performance— variability in demand and the mix of demand across job types. For the base scenario, with the Poisson demand distribution, the variance of demand equals the mean. To assess the impact of demand variance, we consider three discrete demand distributions that have the same mean as the base scenario (two jobs per period per job type), but different variances. Specifically, we consider scenarios with low variance (1.2), medium variance (2), and high variance (3) using, respectively, a triangular distribution, uniform distribution, and bi‐modal distribution weighted at the extremes. Higher demand variability increases the chances of making erroneous job acceptance and resource assignment decisions. Figure 1(b) confirms this effect, showing that the approximate policies have lower gaps when demand has smaller variation. Turning to the demand mix, our base model assumes that every job type has the same expected demand per period. We are interested in assessing the effect of having unequal expected demand across job types. Varying the relative demand, while keeping the expected number of resources the same for all resource types, introduces variations in capacity availability across job types. We expect this variation to reduce problem difficulty (compared with balanced demand), and so improve the performance of the approximate policies. We consider three unbalanced demand scenarios, one corresponding to each job type j having higher demand than the other two job types. For j=1, 2, and 3, we define the type‐j heavy demand scenario as one in which the expected arrival rate per period is 3 for type‐j jobs and 1.5 for the other two job types (so the total expected demand across all job types is the same as the base scenario). Figure 1(c) confirms our intuition that scenarios with balanced demand are more difficult to solve. The average Approximate‐to‐Exact percentage gaps for the unbalanced problems are significantly lower than those for the balanced problems for all three approximate policies, with the gaps being lowest when the least profitable job type (type 3) has high demand. The FCFS policy has an average optimalicy gap of 7.97% over the three unbalanced demand scenarios. Hence, our optimization‐based policies continue to be valuable for generating higher profits, although less so than with balanced demand.

Figure 1(d) compares the performance of the approximate policies as the relative profitability of job types, captured by the reward ratios, changes. With small reward ratios (γ∈[1.5, 2.5]), job types do not differ much in their profit margins compared with the base scenario with moderate reward ratios, and so the impact of wrong acceptance or assignment decisions on overall profits is lower. In this case, we expect the approximate policies to yield profits that are closer to the exact profits. At the other extreme, with large reward ratios (γ∈[2, 3]), wrong acceptance decisions can have significant profit impact. The results in Figure 1(d) validate this hypothesis; the gaps increase as the reward ratio increases. Notably, however, the BCR policy's performance is robust to changes in the reward ratio, with the gap remaining at less than 1.65% even with high reward ratios. In contrast, the FCFS policy has an average gap of 11.9% for small reward ratios, whereas this gap more than doubles to 27.2% for large reward ratios.

Finally, we study the effect of decision frequency on policy performance. Increasing the decision frequency (by increasing the number of decision periods T in the horizon) permits the firm to be more prompt in its responsiveness to customer requests, but reduces the opportunity to accumulate requests before making acceptance and assignment decisions. To contrast with the base setting of 10 periods, we considered three alternative scenarios with 5, 20, and 60 decision periods, respectively, while keeping the total expected demand in the horizon fixed. As the results in Figure 1(e) show, increasing the number of periods, and hence decision frequency, increases the percentage gap, but only minimally for the BCR policy. The DCA policy's optimality gap more than triples when the decision frequency increases from 10 to 60 (from 2.6% to 8.2%), whereas the BCR policy is much more robust (its gap increases from 1.6% to just 2.2%). The FCFS‐to‐Exact gap increases from 10.9% to 29.3% when the decision frequency increases from 5 to 60. This study also permits us to assess the “cost” of making decisions with less information as decision frequency increases. Figure 1 shows the normalized average profit for the exact, BCR, and FCFS policies as the number of periods T increases from 5 to 60. (We normalize the profits so that the average exact profit for the base case, with T=10, is 100.) The figure also displays the PI value; when T=1 (i.e., single decision period at the end of the horizon), both the exact and BCR policies achieve this value. As expected, the profits of all three policies decrease as decision frequency increases; the figure shows that profit decreases at a decreasing rate with T. Compared with the base case of ten decision periods, doubling the decision frequency (to T=20) reduces the exact profits by 1.8%, while halving the frequency (to T=5) raises profit by 1%. The FCFS policy's performance deteriorates significantly as the number of periods grows; its profit gap relative to the exact policy increases from 16.5% to 29.3% when T increases from 10 to 60, whereas the BCR policy's gap is relatively flat.

To summarize, in this section, we have covered a wide range of problem scenarios to capture many different operating conditions of a firm. Remarkably, the BCR policy always achieves profits that are within 2.2% of the exact policy's profits, and in many cases attains optimality gaps well below 1%. For problems with three or four job types (for which we have the exact profits), over the 19 corresponding problem scenarios (covered in Table 1 and Figure 1), the BCR policy has an average optimality gap of 1.3% (relative to the exact profits), while the NCR and DCA policies have gaps of 1.7% and 3.2%, respectively. The FCFS policy, on the other hand, has an average optimality gap of 18.8% over the same set of problem scenarios. Our experiments have confirmed that contextual features such as moderately tight capacities, high reward ratios, and balanced demand increase problem difficulty.

6.1. Model Formulation for Dynamic Acceptance‐Deferred Assignment Problem

To formulate the deferred assignment model, we first note that, since resources are not committed until the end of the horizon, the state of the system in each period must specify the number of jobs of each type accepted until that period (instead of the number of remaining unassigned resources for the dynamic assignment model). For t=T, …, 1 and j∈J, let ζ _jt denote the cumulative accepted demand for type‐j jobs up to and including period t, and let _t ={ζ_1t , ζ_2t , … ζ _mt }. By definition, _T+1=0 and ₁ is the vector of total acceptances over the entire planning horizon. As before, d _t denotes the vector of realized demands in period t. Then, the state of the system at the beginning of period t is ( _t+1, d _t ).

In each period t, we must ensure that the number of new type‐j jobs accepted in this period, say, g_jt for all j∈J, is feasible, i.e., the available (initial) capacity must be adequate to process these and previously accepted jobs. For special resource structures, maintaining feasibility is easy. For instance, if all resources are versatile, then we only need to ensure that the total number of jobs of all types accepted thus far does not exceed the total number of resources. However, with general resource flexibility structures, the feasibility check is not trivial. Specifically, although resources assignments are not finalized until the end of the horizon, the firm must develop a “tentative” plan for resource assignments in each period to ensure that it has enough resources to process the jobs accepted thus far. For this purpose, we introduce auxiliary decision variables h_jrt , for all j∈J and r∈R _j , denoting the number of type r resources that are tentatively assigned to the type‐j jobs accepted at and before period t. Then, the feasible region of acceptance decisions in period t for the deferred assignment (DA) model is defined as follows:

The constraints ensure that: (i) the number g_jt of type‐j jobs accepted in period t does not exceed the demand d_jt observed in the period; (ii) the total number of type‐j jobs tentatively assigned to resources equals the number previously accepted (ζ _j,t+1) plus acceptances in the current period t, and (iii) the total number of jobs tentatively assigned to type‐r resources does not exceed the initial capacity n_rT .

Now, let be the maximum expected profit‐to‐go in period t at the current state (, d _t ). Given that the firm has accepted jobs before period t, the value function is , where P (D _t =d _t ) is the joint probability that the demand in period t is d _t . We can express the profit‐to‐go as 31

In the last period (t=1), after determining ζ ₁, we can decide the final assignment of resources to accepted jobs by solving a simple assignment problem. We refer to the solution to the stochastic dynamic program (31), with deferred assignment, as the Exact^DA policy.

6.2. BCR Policy with Deferred Resource Assignments

We can modify all three approximate policies of section 4 to handle deferred rather than dynamic resource assignments. To illustrate the needed changes, we modify the BCR policy to handle deferred assignments and report computational results using this modified policy, which we call the BCR^DA policy. The BCR policy's strength lies in its ability to dynamically identify resource and job subsets that together constitute capacity bottlenecks taking into account stochasticicy of future demand and the flexibility structure of currently available resources. These bottlenecks then guide decisions on which jobs among the new arrivals in this period to accept. However, while the method accepts new jobs only if the system has adequate capacity to process these jobs, it requires as input the “remaining” resources of each type after assigning to previously accepted jobs to ensure feasibility of these acceptance decisions. For the context with deferred assignments, we have the opportunity to reallocate (tentatively) the resources among accepted jobs in each period. We, therefore, augment the original BCR policy (section 4.4) with a third step, after all acceptance decisions in a period, to reassign resources and determine the remaining resources for new assignments in the next period. Specifically, at the end of Step 2 of the previous BCR procedure for period t, the total number of newly accepted type‐j jobs in this period is . Hence, the total number of accepted type‐j jobs up to and including this period is for all job types j∈J. We then apply the following Step 3 to tentatively assign resources to these accepted jobs, starting with assignment of specialized resource types (Step 3.1) and assignment to preferred resource types (Step 3.2). For this discussion, recall that, for each job type j, s_j , RF _j , and RP _j refer, respectively, to the index of the specialized resource type, set of flexible resource types, and set of preferred resource types (for which job type j is the most profitable). We use and to denote the remaining number of accepted type‐j jobs and remaining number of type‐r resources as we assign specialized and preferred resources.

Step 3 for BCR^DA policy:

 Step 3.1: For j=1, 2, …, m, assign as many type‐j jobs to specialized resources as possible, i.e., set and .

 Step 3.2: For j=1, 2, …, m, assign preferred resources. That is,
      For resource types r∈RP _j , in lexicographically increasing order, set and update .

 Step 3.3: Let be the set of job types with remaining accepted demand, and be the set of flexible resources types with remaining resources capable of performing job type j∈J′. Solve the following Resource Reallocation Problem [RRP], with decision variables h_jrt denoting the number of type‐r resources assigned to remaining accepted type‐j jobs, for j∈J′ and . 32 subject to 33 34 and 35

Set if for some j∈J′, and otherwise.

The [RRP] model assigns remaining flexible resources to the remaining accepted demand (after assignment of specialized and preferred resources) so as to minimize the value τ _r of the resources used. The objective function (32) minimizes this value, while constraints (33) and (34) specify, respectively, that resources must be assigned to all the remaining accepted demand for each job type, and the number of resources assigned must not exceed the number of remaining resources for each resource type r. The BCR^DA policy consists of applying steps 1 and 2 of the BCR policy (section 4.4) followed by the above Step 3 at each period t=T, T−1, …, 1. Next, we discuss computational results using this policy for the flexible resource deployment problem with deferred assignments.

6.3. Computational Results for Deferred Assignment Model

To assess the value of deferring resource assignment decisions and validate the effectiveness of the approximate policy, we implemented the Exact^DA and BCR^DA policies, and applied them to test problems obtained using our problem generation framework of section 5. We expect the Exact^DA policy's profit to be higher than that of the previous exact policy with dynamic assignments but lower than the PI solution value. We first explore these profit gaps for the different scenarios introduced in section 5.3. As before, we use the three job‐type problem with Complete flexibility structure, Poisson arrivals, 10‐period decision horizon, and moderate capacity tightness and reward ratios as the base scenario. We consider variants of this base model to study how the flexibility level, capacity tightness, demand variance, demand mix, relative profitability, and decision frequency affect the benefits of deferred assignments. Table 3 compares the average gap (for 10,000 instances) between the PI value and exact profits with the gap between the Exact^DA and exact profits for various scenarios; both gaps are expressed as percentages of the exact profits.

OPEN IN VIEWER

Table 3

 Benefits of Deferred Resource Assignment

1. Flexibility level
2‐Chain	3.23	1.13
Complete	1.42	0.89
Versatile	1.27	0.00
2. Capacity
Tight	1.42	0.89
Loose	1.05	0.88
3. Demand balance
Balanced	1.42	0.89
Type‐1 heavy	3.91	0.92
Type‐2 heavy	1.91	0.57
Type‐3 heavy	1.43	0.55
4. Demand variance
Low	1.75	1.31
Moderate	2.11	0.97
High	3.25	2.01
5. Reward ratio
Small	1.30	0.85
Moderate	1.42	0.89
Large	3.22	2.09
6. Number of periods
T=5	0.46	0.35
T=10	1.42	0.89
T=20	3.26	1.74

PI, perfect‐information; DA, deferred assignment.

Since the PI solution assumes that both acceptance and assignment decisions can be made after observing the demand for all T periods, the PI‐to‐Exact gap measures the percentage improvement in profit if we can defer both job acceptance and resource assignment decisions to the end of the horizon. On the other hand, the Exact^DA‐to‐Exact gap represents the profit improvement when just resource assignments are deferred to the end. On average, over all scenarios, deferring the assignment decision increases profit by only 1% compared with the 2.1% increase when both acceptance and assignment decisions are deferred. However, deferring assignments can be attractive in certain scenarios. Specifically, when demand has high variance, reward ratios are large, or decision frequency is high, deferring resource assignment decisions captures more than 50% of the total profit increase that a firm can realize by deferring both acceptance and assignment decisions. This finding is not surprising since dynamic decisions are likely to reduce profits the most under these three extreme scenarios.

Next, we test the effectiveness of the BCR^DA policy, in terms of its near‐optimality, for scenarios with three and four job types. Table 4 presents the average gap between the Exact^DA and BCR^DA profits, as a percentage of the Exact^DA profits, for various flexibility structures. To facilitate comparison with the performance of the original BCR method (without deferred assignment), the last column of Table 4 reports the corresponding Exact‐to‐BCR gaps (previously reported in section 5.2). The average Exact^DA‐to‐BCR^DA gap over all scenarios is only 1.3%, which is slightly lower than the previous average Exact‐to‐BCR optimality gap of 1.4% for the original BCR policy applied to the same problem scenarios but with dynamic assignments. These results suggest that the BCR policy continues to be effective in generating near‐optimal solutions when adapted to problems with deferred assignments.

OPEN IN VIEWER

Table 4

 BCR^DA Policy Effectiveness for Three and Four Job‐Type Scenarios

No. of job types (m)	Resource structure
3	2‐Chain	1.25
	Complete	1.76
	Versatile	1.15
4	2‐Chain	1.15
	2‐All	1.81
	3‐Chain	1.42
	Versatile	0.74

BCR, Bottleneck Capacity Reservation; DA, deferred assignment.