2. MODEL DESCRIPTION AND FORMULATION

Throughout the rest of the article we restrict our attention to a set of policies that are deterministic and Markovian. Thus, a decision rule is a function that maps a current state to an admissible action. A sequence of decision rules is called a policy and prescribes the best action for each state at any particular time. Without loss of generality, a set of deterministic Markov policies is sufficient to guarantee optimality over a larger set of nonanticipating policies.

Furthermore, a simple interchange argument shows that it is never optimal to hold inventory when there is at least one class 1 order backordered. Therefore, under any optimal policy, if the inventory level is positive, then there can be no class 1 backorders; and if a class 1 backorder exists, then there can be no inventory on-hand. From this, let (X(t),Y(t)) denote the state at time t such that

Let Π denote the set of Markov deterministic policies, and suppose for any u ∈ Π and t ≥ 0 that (X^u(t),Y^u(t)) represent the inventory and backorder process in the class 1 queue, and the backorder process in the class 2 queue under policy u at time t, respectively. At time t, the decision-maker chooses a service rate u_c(t), makes a production decision u_p(t), and makes a rationing decision u_r(t), defined as follows:

A control policy specifies the action taken at any time given the state of the system. Denote a policy u by {(u_c(t),u_p(t),u_r(t))|t ≥ 0}, where u_q(t) = u_q(t,X(t),Y(t)) for q = (c,p,r). Define the finite horizon expected discounted cost, the infinite horizon expected discounted cost, and the long-run average cost starting in state (x,y) respectively by

In each case, we define the optimization equation:

Given any Markov deterministic policy u, (X^u(t),Y^u(t)) is a continuous-time Markov chain. In the continuous-time formulation, decisions can be made at any point in time. However, because state transitions are Markovian, it suffices to consider policies where decisions are made at discrete epochs (order arrivals and job completions). Thus, instead of a continuous-time control problem, we apply uniformization in the spirit of Lippman [10] and solve an equivalent discrete-time problem. Define γ to be the maximum rate of transition: γ = μ + s + λ₁ + λ₂. Without loss of generality, scale ρ and γ so that ρ + γ = 1. Then the optimality equation for the infinite-horizon discounted cost is written as

The first term, c(x,y) = hx⁺ + b₁ x⁻ + b₂ y, represents inventory holding and backorder costs in state (x,y). Two minimization operators T_r and T_p from

corresponding to rationing and production decisions, respectively, are

We also write optimality equations for the n-stage and average cost cases respectively:

Note that in the average cost case, g is the optimal average expected cost per unit time and w(x,y) is a relative value function in state (x,y).

3. STRUCTURE OF OPTIMAL POLICY

In this section we characterize the structure of the optimal policy. We do this by characterizing properties of the value function and showing that these properties are preserved by the minimization operators and by the optimality equation. We characterize the optimal policy for the finite-horizon case and then extend to the infinite-horizon discounted and average cost cases.

We first show that there exists a subset of A from which the optimal service rate will be chosen for all states at any point in time. In other words, there exists an efficient frontier comprising undominated pairs (s,r(s)),s ∈ A. Define B = {(s,r)|s ∈ A,r ≥ r(s)} and its convex hull C(B) on s ∈ [0,s]. Note that when A is a discrete set, then C(B) can be expressed by a finite set of linear inequalities. Otherwise, C(B) = {(s,r)|r ≥ g(s) for each s ∈ [0,s]}, where g(s) is the largest convex function on [0,s] such that r(s) ≥ g(s) for all s ∈ A. We define a subset of A, A′, as follows: A′ = {s ∈ A| there are no

, and α ∈ (0,1) such that

. A subset of the lower boundary of C(B), {(s,r(s))|s ∈ A′}, is called an efficient frontier. Note that this efficient frontier always contains (0,0) and (s,r(s)). Figure 1 illustrates these definitions. Here A′ = {0, 1} ∪ [2,3] ∪ {3.5, 4} and the efficient frontier is {(s,r(s));s ∈ A′}.

Example of A, C(B), and A′.

Our first result shows that there exists an optimal policy that selects a service rate from A′ in all states.

Theorem 3.1: If s ∈ A − A′, then there exists an optimal policy that does not choose s in any state.

Proof: We prove this by contradiction. Suppose a rate s ∈ A − A′ is in fact optimal in some state (x,y) with k + 1 (k ≥ 0) periods to go. Then there must exist

such that

. Since s is optimal in (x,y), we have

It suffices to consider the case where both inequalities are strict since the claim holds trivially otherwise. Applying a little algebra, we get

Defining f_k(x,y) = T_p v_k(x,y) − v_k(x,y) and rewriting the inequalities in terms of f_k(x,y), we have

Multiplying (10) by α and (11) by (1 − α) and then adding the two inequalities, we have

This contradicts the fact that

. Therefore, s cannot be optimal. █

Theorem 3.1 implies that it suffices to restrict attention to a minimization problem over A′ instead of A for all states. It also implies that any open interval of feasible rates s for which r(s) is concave need not be considered. When r(s) is concave for all s ∈ A, this result simplifies the optimal service rate decision into a bang-bang control problem.

Corollary 3.1: If r(s) is concave in s, then the optimal service rate s* is either zero or s in all states.

Proof: The result immediately follows from Theorem 3.1 since (0,0) and (s,r(s)) are the only points on the efficient frontier {(s,r(s))|s ∈ A′}. █

Although Theorem 3.1 reduces the set of admissible rates to A′, we still need to solve the optimality equation to find an optimal rate as well as production and inventory policy in each state; that is, for k ≥ 0, the optimal service rate with k + 1 periods to go can be found by solving

Noting that some terms are independent of s, this is equivalent to finding

where T_p v_k(x,y) = min[v_k(x,y),v_k(x + 1,y),v_k(x,y − 1_{y>0})] and f_k(x,y) := T_p v_k(x,y) − v_k(x,y) ≤ 0. Since r(s) is increasing, it is easy to see that when f_k(x,y) = 0, the minimum occurs at s = 0. In addition, s_k+1*(x,y) is nonincreasing in f_k(x,y), as stated in the following lemma.

Lemma 3.1: Let

for a ≤ b ≤ 0. Then

.

Proof: Suppose

. From the definitions of

, we have

, respectively. Without loss of generality, it suffices to consider the case where at least one of the inequalities holds strictly. Otherwise, the claim holds trivially since one can choose

. Rearranging inequalities, we have

, respectively. Since at least one of the inequalities is strict, this contradicts b ≥ a. Therefore,

. █

For the remainder of this section, we will show that the optimal cost to go function v_k(x,y) satisfies a set of properties and that there exists a structured optimal policy for all finite-horizon problems. To do this, we define

to be the set of functions on

satisfying the following properties:

1. v(x + 1,y) ≤ v(x,y − 1) and v(x + 1,y) ≤ v(x,y) for x < 0 and all y > 0.

2. v(x,y) ≤ v(x,y + 1) for all

.

3. (Convexity) For all

:

3. (Submodularity and diagonal dominance) For all

:

Note that if

, then

for any scalar c ≥ 0 and that if

, then their sum v + w is also in

. Also note that

. We also define the following operators:

With several technical lemmas and an induction argument, we will show that if

, then there exists a structured optimal policy for the k + 1 stage problem and that

for all k. One might notice that the properties of

are similar to the ones used in Ha [8], where he characterized the structure of the optimal policy for a system with a fixed service rate μ. However, in our problem, the service rate is also a decision variable in the optimality equation; thus, the transition rate at which jobs are completed can vary in state. To use an inductive argument, one must show that the properties of

are preserved in the optimality equation, in particular under two minimization operations: one for the service rate decision and the other for the production and rationing decisions.

Suppose

for some k ≥ 0 (it is certainly true for k = 0). Let P_k(y) be a function in y ≥ 0 such that P_k(y) = min{x ∈ X|v_k(x + 1,y) > v_k(x,y − 1_{y>0})}. Then the following result must hold.

Lemma 3.2: If

for

, then P_k(y) is nonnegative and nonincreasing in y.

Proof: Since

, it follows that v_k(x + 1,y − 1) ≤ v_k(x + 1,y) ≤ v(x,y) for all x < 0. Thus, P_k(y) ≥ 0 for all y.

To prove that P_k(y) is nonincreasing, first consider when y = 0. Suppose P_k(1) > P_k(0) instead. This implies

This contradicts the fact that

—in particular Property 2, which states that v_k is nondecreasing in y. Now suppose there exists y ≥ 1 such that P_k(y + 1) > P_k(y); that is, v_k(P_k(y) + 1,y + 1) ≤ v_k(P_k(y),y). This inequality and Property 4(iii) imply that

This contradicts the definition of P_k(y); therefore, P_k(y + 1) ≤ P_k(y) for all y ≥ 0. █

Using this lemma, we now characterize the structure of optimal policy for the finite-horizon problem.

Theorem 3.2: If

, there exists an optimal policy for the k + 1 period problem described as follows.

(i) If x < P_k(y), produce to stock (or reduce the class 1 backorder when x < 0). If x ≥ P_k(y) and y > 0, produce to reduce class 2 backorders. Otherwise, do not produce.

(ii) When a class 2 order arrives, satisfy an order immediately from stock if x > P_k(y + 1). Otherwise, place an arriving class 2 order in the backorder queue.

(iii) s_k+1*(x,y) = arg min_s∈A′{r(s) + sf_k(x,y)} is decreasing in x and increasing in y and s_k+1*(x − 1,y) ≥ s_k+1*(x,y + 1) for x < P_k(y + 1) and all y. Furthermore, if it is optimal not to produce in state (x,y), then s_k+1*(x,y) = 0.

Proof:

(i) Consider x < P_k(y). The definition of P_k(y) and Property 2 of

imply that v_k(x + 1,y) ≤ v_k(x,y − 1_{y>0}) ≤ v_k(x,y); thus, it is optimal to produce to stock (or reduce class 1 backorders) in state (x,y). If x ≥ P_k(y), then v_k(x + 1,y) > v_k(x,y − 1_{y>0}). For y = 0, do nothing is optimal (i.e., v_k(x,0) = T_p v_k(x,0)). For y > 0, v_k(x,y − 1) ≤ v_k(x,y) (Property 2); thus, it is optimal to produce and reduce the class 2 backorder level.

(ii) Since x > x − 1 ≥ P_k(y + 1) ≥ 0, v_k(x,y + 1) > v_k(x − 1,y); hence, T_r v_k(x,y) = min[v_k(x,y + 1),v_k(x − 1,y)] = v_k(x − 1,y). On the other hand, if x ≤ P_k(y + 1), then T_r v_k(x,y) = v_k(x,y + 1); thus, it is optimal to backorder class 2.

(iii) We first show s_k+1*(x,y) is decreasing in x. From Lemma 3.1, it suffices to show f_k(x,y) is increasing in x. First, consider the case when y = 0. From the fact that

and claim (i), there are only three cases of the pair (T_p v_k(x,0),T_p v_k(x + 1,0)) = (min[v_k(x,0),v_k(x + 1,0)],min[v_k(x + 1,0),v_k(x + 2,0)]) to consider.

For y > 0, recall that T_p v_k(x,y) = min[v_k(x + 1,y),v_k(x,y − 1),v_k(x,y)]. From the fact that

and claim (i), only four distinct feasible cases of (T_p v_k(x,y),T_p v_k(x + 1,y + 1)) (out of nine possible cases) exist.

Thus, f_k(x,y) is increasing in x for all y ≥ 0 and s_k+1*(x,y) is decreasing in x. The proof for the monotonicity in y is similar and therefore omitted.

We now show that s_k+1*(x − 1,y) ≥ s_k+1*(x,y + 1) for x < P_k(y + 1). Since P_k(y) is nonincreasing in y, T_p v_k(x − 1,y) = v_k(x,y) and T_p v_k(x,y + 1) = v_k(x + 1,y + 1). From Property 4(ii), we get

From Lemma 3.1, s_k+1*(x − 1,y) ≥ s_k+1*(x,y + 1). Finally, if do nothing is optimal in state (x,y), then f_k(x,y) = v_k(x,y) − v_k(x,y) = 0. Hence, s_k+1*(x,y) = 0. █

A policy described in Theorem 3.2 agrees with our intuition that a monotone policy is optimal. For given x, it is optimal to serve class 2 only when the class 2 backorder level exceeds a nonnegative threshold (i.e., x > P_k(y)), which is decreasing in x. To put it differently, it is optimal to produce to raise the stock level for class 1 orders before producing for class 2 backorders. A similar policy is optimal for inventory rationing: Class 1 orders are always rationed from existing stock, but class 2 orders will be served from existing stock only if the system has enough inventory for future class 1 orders. The optimal service rate is monotone in state; that is, s_k+1*(x,y) decreases in x but increases in y. The service rate increases as inventory decreases or backorders increase. However, it is rather interesting to note that s_k+1*(x − 1,y) ≥ s_k+1*(x,y + 1) only when x < P_k(y + 1) instead of for all states. That is because the marginal (inventory and backorder) cost decreases when the state changes from (x + 1,y) to (x,y) for x ≥ P_k(y + 1) ≥ 0, whereas the marginal cost increases for the same transition when there are class 1 backorders (i.e., x < 0).

To show that a structured policy is optimal for all finite-horizon problems, we now only need to show that if

for some

. To see this, suppose

. From Theorem 3.2, there exists a structured optimal policy for the k + 1 stage problem. Applying this argument repeatedly, we get the desired result for any finite-horizon problem. Define an operator (mapping)

, which corresponds to a portion of the value function associated with s:

Then we write the optimality equation for the k + 1 stage problem as

The following two lemmas show that the properties of

are preserved when a function in

is mapped by minimum operators T_r, T_p, and T.

Lemma 3.3: If

, then

.

Proof: The proof is similar to that of Lemma 3.4 and therefore is omitted. █

Lemma 3.4: If

, then

.

Proof: The proof is provided in the Appendix. █

Using these two lemmas, we now show that Properties 1–4 are preserved by the optimality equation.

Theorem 3.3: If

, then

for all k ≥ 0.

Proof: Suppose that

. It is easy to show that

. Also, there exists a structured optimal policy as described in Theorem 3.2 for the k + 1 stage problem, and T_p v_k, T_r v_k, and

from Lemmas 3.3 and 3.4, respectively. The result then immediately follows from the fact that the class of functions

is closed under multiplication by a nonnegative scalar and the fact that the sum of functions in

are also in

. █

Thus far, we have shown that the optimality equation is in

, and from this, there exists a structured optimal policy for a finite-horizon problem. It is not hard to show that the result can be extended to the infinite-horizon problem.

Theorem 3.4 (Infinite-horizon discounted cost case):

(i)

.

Proof: The set of functions

is complete under the L^∞ metric; thus, the limit of any convergent sequence of functions in

is also in

. Let v_∞(x,y) be the limit of any convergent sequence. Theorem 3.2 implies that there exists a structured optimal policy for the one-stage minimization problem with terminal cost v_∞(x,y). Furthermore, Properties 1–4 are preserved in the optimality equation for the one-stage problem with terminal value v_∞(x,y). By Theorem 5.1 in Porteus [14],

and there exists a structured optimal policy. █

We note that the results also extend to the average cost case by taking the limit of the value function in the discounted cost problem and applying conditions (a)–(g) in Weber and Stidham [17].

An example of an optimal policy is illustrated in Figure 2. The bottom graph in Figure 2 describes an optimal production policy, which is characterized by a switching curve, P(0) = 20, P(y) = 3 for 0 < y < 16, and P(y) = 2 for y ≥ 16. The top graph in Figure 2 illustrates optimal production rates s*(x,y). As described in our result, the optimal service rate is decreasing in x and increasing in y. Furthermore, for states satisfying x < P(y + 1), monotonicity also holds in the diagonal direction.

Average cost optimal policy at h = 1, b1 = 150, b2 = 50, λ1 = 11, λ2 = 1,μ = 13, and an efficient frontier (s,r(s)) ∈ {(0, 0),(2.0, 0.5),(2.5, 15),(2.8, 100)}.

4. NUMERICAL STUDY

In Section 3 we have shown that an optimal policy is monotone and state dependent. To find an optimal policy, one must solve the optimality equation and simultaneously determine optimal service rate and production (and rationing) decisions for each state. Implementing such an optimal policy can be quite difficult; thus, one might prefer to use a simple heuristic policy if the additional benefit of using an optimal policy is not substantial. In this section we investigate whether the extra efforts of obtaining an optimal policy that dynamically adjusts both capacity and production decisions are well justified.

To answer this question, we conducted a numerical study to compare the optimal policies with three heuristic policies:

The first two policies use a suboptimal production policy but dynamically adjust the service rate based on the congestion level. Policy AM ignores the value of inventory completely, and operates the system as a multiclass queuing system. In policy AB the system produces up to a base-stock level but ignores dynamic rationing. In policy FD the system operates at a fixed service rate, but production (inventory) decisions are dynamically adjusted in the congestion level. Comparing the performance of these policies will highlight the benefit of joint optimal decisions, which we sought in Section 3.

We constructed examples that cover a wide range of scenarios. In all of our examples, we focused on the average cost problems to isolate the effects of planning the horizon and discount factors. For all examples, we assume A′ = {1,2,3}, which means that the system can operate at rate μ, μ + 1, μ + 2, or μ + 3. We fixed the backorder cost for the class 2 order at b₂ = 5 and the holding cost at h = 1 and varied other parameters as follows:

• Arrival rates (λ₁,λ₂): (1,10), (10,1), (1,1);
• Nominal utilization rate (λ₁ + λ₂)/μ: 0.5, 0.95;
• Backorder cost of class 1 order b₁: 10, 100;
• Cost function of additional capacity r(s),s = 1,2,3: Low (0.5, 1.5, 3.0), High (5, 15, 30).

Table 1 summarizes the result of our numerical study. We report the average costs under optimal and three heuristic policies as well as the percentage suboptimality of each heuristic policy. We also report the average suboptimality gaps of all three heuristic policies.

Summary of Numerical Results

Needless to say, policy AM performs extremely poorly in all examples since it ignores future orders and produce all orders in backorder. Although policy AB is substantially better than policy AM, the suboptimality gap is quite significant for some examples. Although policy AB keeps inventory for future orders, it uses the same rationing policy for existing inventory for both demand classes. On the other hand, the optimal policy dynamically changes rationing decisions based on the current state. Under the optimal policy, it might be optimal to keep inventory and class 2 backorders at the same time in order to serve future class 1 orders from existing stock. Class 2 orders are served only when the system has sufficient inventory to serve current and future class 1 orders. Thus, the difference between these two policies measures the benefit of dynamic rationing. The suboptimality gap tends to increase as arrival rate of class 2 orders increases and the difference of backorder costs increases. This shows that considerable savings can be realized from an efficient dynamic production and rationing policy.

We also report that the suboptimality gap between policy FD and the optimal policy can be quite large for a number of examples, particularly when the cost of increasing service rate is high. Since policy FD operates at a constant rate, it incurs unnecessarily high capacity costs when congestion level is low and it fails to ramp up capacity when congestion level is high. Thus, the difference between the two policies represents the benefit of flexibility in capacity (service rate). The results in Table 1 show that both a dynamic capacity decision and a production decision contribute to a substantial reduction of operating cost. Although a simple heuristic policy might be easy to implement, it fails to fully adjust the controls when the current state changes as the optimal policy does.

5. CONCLUSIONS

We have characterized the optimal policy for a make-to-stock production system with an adjustable service rate. We show that under an optimal policy, only service rates on an efficient frontier will be chosen and that a monotone policy is optimal for both service rate and production/inventory decisions. Our contribution is to address a gap in the literature regarding the effective control of make-to-stock systems. With a numerical study we demonstrate that the benefit from joint optimization can be substantial.

Building on our results with two demand classes, we are currently working on several extensions. We are working to extend the result to more than two demand classes and to include a fixed cost for adjusting the service rate. We are also considering models where the decision-maker can change the service rate at random epochs. Such situations arise when additional capacity is provided by workers (machines) who have other primary tasks and will be available to aid only when they are idle. Our preliminary result [11] indicates that an optimal policy might not be monotone and can be of a complex form. Further research will shed light on the structure of an optimal policy.