5.1 Hierarchical controls of single or parallel machine systems under symmetric deterioration and cancelation rates

Let us consider a manufacturing system whose system dynamics satisfy the differential equation

$$\dot{\mbox{\boldmath$x$ }}^{\varepsilon}(t) =- f({\mbox{\boldmath......}}, \ \{\mbox{\boldmath$x$ }}^{\varepsilon}(0)={\mbox{\boldmath$x$ }} \in R^n,$$ (5.1)

where ${\mbox{\boldmath$a$ }}=(a_1,...,a_n)$ with a_i>0 and$f({\mbox{\boldmath$a$ }},{\mbox{\boldmath$x$ }}^{\varepsilon}(t))=\mbox{diag} (a_1,...,a_n){\mbox{\boldmath$x$ }}^{\varepsilon}(t)$. The attrition rate a_i represents the deterioration rate of the inventory of the finished product type i when $x^{\varepsilon}_i(t)>0$, and it represents a rate of cancelation of backlogged orders when$x_i^{\varepsilon}(t)<0$. We assume symmetric deterioration and cancelation rates for product i only for convenience in exposition. It is easy to extend our results when a⁺_i>0 denotes the deterioration rate and a^-_i>0 denotes the order cancelation rate.

Let $m(\varepsilon, t) \in {\cal M} = \{0,1,...,m\}$,$t\geq 0$, denote a Markov process generated by$Q^{(1)}+(1/\varepsilon)Q^{(2)}$, where $\varepsilon >0$ is a small parameter and $Q^{(\ell)}=(q^{(\ell)}_{ij})$,$i,j\in{\cal M}$ is an (m+1) x (m+1) matrix such that$q^{(\ell)}_{ij}\geq 0$ for $i\neq j$ and$q^{(\ell)}_{ii}=-\sum_{j \neq i}q^{(\ell)}_{ij}$ for $\ell=1,2$. We let $m(\varepsilon,t)$ represent the machine capacity state at time t.

Definition 5.1   A production control process${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)=\{ {\mbox{\boldmath$u$ }}^{\varepsilon}(t):t\geq0\}$ is admissible, if

(i)

${\mbox{\boldmath$u$ }}^{\varepsilon}(t)\in {\cal F}^{(\varepsilon)}_t \equiv \sigma (m(\varepsilon,s), 0 \leq s \leq t)$;

(ii)

$u_k^{\varepsilon}(t)\geq0$, k=1,2,...,n, $\sum_{k=1} ^n u^{\varepsilon}_k(t) \leq m(\varepsilon , t)$ for all $t\geq 0$.

We denote by ${\cal A}^{{\mbox{\boldmath$a$ }},\varepsilon}(m)$ the set of all admissible controls with the initial condition $m(\varepsilon,0)=m$.

Definition 5.2   A function ${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }}, m)$ defined on $R^n\times {\cal M}$ is called an admissible feedback control or simply a feedback control, if

(i)

for any given initial surplus and production capacity, the equation

$$\dot{{\mbox{\boldmath$x$ }}}^{\varepsilon}(t)=-f({\mbox{\bo......}^{\varepsilon}(t),m(\varepsilon,t))-{\mbox{\boldmath$z$ }}$$

has a unique solution;

(ii)

the control defined by ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)=\{{\mbox{\boldmath$u$ }}^{\vareps......silon,t)), t \geq 0 \}\in {\calA}^{{\mbox{\boldmath$a$ }}, \varepsilon} (m)$.

With a slight abuse of notation, we simply call ${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }}, m)$, a feedback control when no ambiguity arises. For any ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\in {\cal A}^{{\mbox{\boldmath$a$ }},\varepsilon}(m)$, define the expected long-run average cost

$$\bar J^{{\mbox{\boldmath$a$ }},\varepsilon}({\mbox{\boldmath$x$ }......boldmath$x$ }}^{\varepsilon}(t))+c({\mbox{\boldmath$u$ }}^{\varepsilon}(t)))dt,$$ (5.2)

where ${\mbox{\boldmath$x$ }}^{\varepsilon}(\cdot)$ is the surplus process corresponding to the production process ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot )$ in ${\cal A}^{{\mbox{\boldmath$a$ }},\varepsilon}(m)$ with ${\mbox{\boldmath$x$ }}^{\varepsilon}(0)={\mbox{\boldmath$x$ }}$, and $h(\cdot)$ and $c(\cdot)$ are given as in Section 2. The problem is to obtain${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\in {\cal A}^{{\mbox{\boldmath$a$ }},\varepsilon}(m)$ that minimizes $\bar J^{{\mbox{\boldmath$a$ }},\varepsilon}({\mbox{\boldmath$x$ }},m,{\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot))$. We formally summarize our control problem as follows: $$\bar {\cal P}^{{\mbox{\boldmath$a$ }},\varepsilon} : \left ......box{\boldmath$u$ }}^{\varepsilon}(\cdot)).\end{array} \right.$$

Here we assume that the production cost function $c(\cdot)$ and the surplus cost function $h(\cdot)$ satisfy Assumption 3.1, and the machine capacity process $m(\varepsilon,t)$ satisfies Assumptions 3.2 and 3.3. Furthermore, similar to Assumption 4.3, we also assume

Assumption 5.1$\sum_{j=0}^pj\nu_j \geq \sum_{i=1}^nz_i$.

As in Fleming and Zhang (1998), the positive attrition rate${\mbox{\boldmath$a$ }}$ implies a uniform bound for ${\mbox{\boldmath$x$ }}^{\varepsilon}(t)$. In view of the fact that the control ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot )$ is bounded between 0 and m, this implies that any solution ${\mbox{\boldmath$x$ }}^{\varepsilon}(\cdot)$ to (5.1) must satisfy

$$\vert x_i^{\varepsilon}(t)\vert \left \vert x_ie^{-a_it} +e^{-a_it} \int^t _0 e^{a_is}(u_i^{\varepsilon}(s)-z_i)ds \right\vert$$ =

$$\leq \vert x_i\vert e^{-a_it}+(m+z_i)\int^t _0 e^{-a_i(t-s)}ds$$

$$\leq \vert x_i\vert e^{-a_it} +\frac {m+z_i} {a_i},\ \ i=1,...,n.$$ (5.3)

Thus under the positive deterioration/cancelation rate, the surplus process ${\mbox{\boldmath$x$ }}(t)$ remains bounded.

The average cost optimality equation associated with the average-cost optimal control problem in ${\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$, as shown in Sethi, Zhang, and Zhang (1997), takes the form

$${\bar \lambda }^{\varepsilon} \inf_{u_i\geq0, \sum_{i=1} ^n u_i\leq k} \left \{ \frac {\partia......ox{\boldmath$u$ }}-{\mbox{\boldmath$z$ }})} +c({\mbox{\boldmath$u$ }})\right\}$$ =

$$\ \ \ +h({\mbox{\boldmath$x$ }})+\left(Q^{(1)}+\frac {1}{\vareps......bar W}^{{\mbox{\boldmath$a$ }},\varepsilon}({\mbox{\boldmath$x$ }},\cdot) (m),$$ (5.4)

where ${\bar W}^{{\mbox{\boldmath$a$ }},\varepsilon} ({\mbox{\boldmath$x$ }},m)$ is the potential function of the problem ${\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$. The analysis begins with the proof of the boundedness of$\lambda^{\varepsilon}$. Sethi, Zhang, and Zhang (1997) prove

Theorem 5.1   The minimum average expected cost $\lambda^{\varepsilon}$ of ${\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$is bounded in$\varepsilon$, i.e., there exists a constant C>0 such that

$$0\leq \lambda ^{\varepsilon } \leq C_{51} \ \ \mbox{for all} \ \varepsilon >0.$$

 In order to construct open-loop and feedback hierarchical controls for the system, one derives the limiting control problem as$\varepsilon\rightarrow0$. As in Sethi, Zhang, and Zhou (1994), consider the enlarged control space

$$\begin{eqnarray*}% latex2html id marker 4887&&{\cal A}^{\mbox{\boldmath$a$ }......\ \ \ \ \ U(\cdot ) \ \ \mbox {is a deterministicprocess} \}.\end{eqnarray*}$$ Then define the limiting control problem $\bar {\cal P}^{\mbox{\boldmath$a$ }}$ as follows: $$\bar {\cal P}^{\mbox{\boldmath$a$ }}:\left \{\begin{array...... }}({\mbox{\boldmath$x$ }},U(\cdot)).\end{array}\right.$$

The average-cost optimality equation associated with the limiting control problem $\bar {\cal P}^{\mbox{\boldmath$a$ }}$ is

$$\bar \lambda=\inf_{u_i^k\geq0,\sum_{i=1}^n u^k _i \leq k, k \in{......m_{k=0}^p \nu_kc({\mbox{\boldmath$u$ }}^k)\right \} +h({\mbox{\boldmath$x$ }}),$$ (5.5)

where $\bar W^{\mbox{\boldmath$a$ }}({\mbox{\boldmath$x$ }})$ is a potential function for ${\calP}^{\mbox{\boldmath$a$ }}$. From Sethi, Zhang, and Zhang (1997), we know that there exist $\bar \lambda$ and $\bar W^{\mbox{\boldmath$a$ }}({\mbox{\boldmath$x$ }})$ such that (5.5) holds. Moreover, $\bar W^{\mbox{\boldmath$a$ }}({\mbox{\boldmath$x$ }})$ is the limit of $\bar W^{{\mbox{\boldmath$a$ }},\varepsilon}({\mbox{\boldmath$x$ }},k)$ as $\varepsilon\rightarrow0$.

Armed with Theorem 5.1, one can derive the convergence of the minimum average expected cost $\lambda^{\varepsilon}$ as$\varepsilon$ goes to zero, and establish the convergence rate.

Theorem 5.2   There exists a constant C such that for all $\varepsilon >0$,

$$\vert\lambda ^{\varepsilon} -\lambda\vert \leq C_{52} \varepsilon ^{\frac {1} {2}}.$$

This implies in particular that $\lim_{\varepsilon \rightarrow 0} \lambda ^{\varepsilon} =\lambda$.
 

Here we only outline the major steps in the proof. For the detailed proof, the reader is referred to Sethi, Zhang, and Zhang (1997). The first step is to prove ${\lambda}^{\varepsilon}\leq \lambda + C_{52} \varepsilon^{\frac {1} {2}}$ by constructing an admissible control ${\mbox{\boldmath$u$ }}^{\varepsilon}(t)$ of $\bar {\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$ from the optimal control of the limiting problem $\bar {\cal P}^{\mbox{\boldmath$a$ }}$, and by estimating the difference between the state trajectories corresponding to these two controls. Then one establishes the opposite inequality, namely,${\lambda}^{\varepsilon} \geq \lambda -C_{52} \varepsilon^{\frac{1} {2}}$, by constructing a control of the limiting problem$\bar {\cal P}^{\mbox{\boldmath$a$ }}$ from a near-optimal control of $\bar {\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$ and then using Assumptions 2.1.

The following theorem concerning open-loop controls is proved in Sethi, Zhang, and Zhang (1997).

Theorem 5.3 (Open-loop control)  Let$\bar U(\cdot)=(\bar {\mbox{\boldmath$u$ }}^0(\cdot), \bar {\mbox{\boldmath$u$ }.........,\bar {\mbox{\boldmath$u$ }}^p(\cdot)) \in {\cal A}^{\mbox{\boldmath$a$ }}$be an optimal control for$\bar {\cal P}^{\mbox{\boldmath$a$ }}$, and let

$${\mbox{\boldmath$u$ }}^{\varepsilon} (t)= \sum_{i=0} ^p I_{\{m (\varepsilon, t)=i\}}\bar {\mbox{\boldmath$u$ }}^i (t).$$ Then ${\mbox{\boldmath$u$ }}^{\varepsilon} (\cdot)\in {\cal A}^{{\mbox{\boldmath$a$ }},\varepsilon} (m(\varepsilon,0))$, and${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot )$is asymptotically optimal for$\bar {\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$, i.e., $$\vert\lambda ^{\varepsilon} -J^{{\mbox{\boldmath$a$ }}, \vare......epsilon} (\cdot))\vert \leq C_{53}\varepsilon^{\frac {1} {2}}$$

for some positive constant C.
 

We next consider feedback controls. We begin with an optimal feedback control for $\bar {\cal P}^{\mbox{\boldmath$a$ }}$, which with a slight abuse of notation is denoted as $\bar U({\mbox{\boldmath$x$ }}) =(\bar {\mbox{\boldmath$u$ }}^0 ({\mbox{\boldmat......box{\boldmath$x$ }}),...,\bar {\mbox{\boldmath$u$ }}^p({\mbox{\boldmath$x$ }}))$. This is obtained by minimizing the right-hand side of (5.5), i.e.,

$$\begin{eqnarray*}&& \left ( \sum_{i=0} ^p \gamma _i \bar {\mbox{\boldmath$u$ }......\mbox{\boldmath$u$ }}^i ) \right \} +h({\mbox{\boldmath$x$ }}).\end{eqnarray*}$$ We then construct the control

$${\mbox{\boldmath$u$ }}^{\varepsilon} ({\mbox{\boldmath$x$ }}, m(\......m(\varepsilon , t)=i\}} \bar {\mbox{\boldmath$u$ }}^i ({\mbox{\boldmath$x$ }}),$$ (5.6)

which is clearly feasible (satisfies the control constraints) for$\bar {\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$. Furthermore, if each $\bar{\mbox{\boldmath$u$ }}^i ({\mbox{\boldmath$x$ }})$ is locally Lipschitz in ${\mbox{\boldmath$x$ }}$, then the system

$$\dot{{\mbox{\boldmath$x$ }}}^{\varepsilon} (t)=-f({\mbox{\boldmat......t))-{\mbox{\boldmath$z$ }}, \ {\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }},$$ (5.7)

has a unique solution, and therefore ${\mbox{\boldmath$u$ }}^{\varepsilon}({\mbox{\boldmath$x$ }}(t), m(\varepsilon, t)), \ t \geq 0$, is also an admissible feedback control for $\bar {\calP}^{{\mbox{\boldmath$a$ }},\varepsilon}$. According to Lemma J.10 of Sethi and Zhang (1994a), there exists an$\varepsilon_0$ such that $Q^{(1)} + {\varepsilon}^{-1} Q^{(2)}$ is weakly irreducible for $0<\varepsilon\leq\varepsilon_0$. Let$\nu^{\varepsilon} =(\nu_0 ^{\varepsilon}, \nu_1^{\varepsilon},...,\nu_m ^{\varepsilon})$ denote the equilibrium distribution of $Q^{(1)} + {\varepsilon}^{-1} Q^{(2)}$, i.e.,

$$\nu ^{\varepsilon} \left(Q^{(1)}+\varepsilon^{-1} Q^{(2)}\right)=0 \ \ \mbox{and} \ \ \sum_{i=0} ^m \nu^{\varepsilon} _i=1.$$ (5.8)

Sethi, Zhang, and Zhang (1997) prove the following result, but only in the single product case.

Theorem 5.4 (Feedback control)  Let n=1. Assume (A.2.1) and (A.9.3) and that the feedback control of the limiting problem $\bar u(x)$is locally Lipschitz in x. Furthermore, suppose that for each$\varepsilon \in [0, \varepsilon_0]$, the equation 

$$-f(a,x)+\sum_{i=0} ^p \nu_i ^{\varepsilon} \bar u^i (x)-z =0$$ (5.9)

has a unique solution$\theta^{\varepsilon}$, called the threshold. Moreover, suppose that for$x \in (\theta^{\varepsilon}, \infty)$,

$$-f(a,x) +\sum_{i=0} ^p \nu^{\varepsilon} _i \bar u^i (x) -z <0,$$ (5.10)

and for $x \in (-\infty, \theta^{\varepsilon}),$

$$-f(a,x) +\sum_{i=0} ^p \nu_i ^{\varepsilon} \bar u^i (x) -z >0,$$ (5.11)

where$\gamma ^0 =\gamma$. Then the feedback control given in (5.6) is asymptotically optimal, i.e., $$\lim_{\varepsilon \rightarrow 0} \vert\bar J^{a,\varepsilon}(x,\alpha(\epsilon,0), u^{\varepsilon} (\cdot)) - \lambda\vert=0,$$

where$u^{\varepsilon} (t) =u^{\varepsilon} (x(t),m(\varepsilon,t))$.
 

Since there are several hypotheses, namely (5.9)-(5.11), in Theorem 5.4, it is important to provide at least an example for which these hypotheses hold. Below we provide such an example and at the same time illustrate the ideas of constructing the asymptotically optimal controls.

Example 5.1. Consider the problem

$$\bar {\cal P}^{a,\varepsilon} : \left \{\begin{array}{lll......arepsilon}(x,k,u^{\varepsilon}(\cdot)),\end{array}\right.$$

with ${\cal M}=\{0,1\}$ and the generator for $m(\varepsilon,t)$ to be

$$Q^{(1)}+\frac{1}{\varepsilon}Q^{(2)}=\frac{1}{\varepsilon......\begin{array}{cc}-1 & 1\\1 &-1\end{array}\right).$$

This is clearly a special case of the problem formulated in this section. In particular, Assumptions 3.3 and 3.4 hold and$\nu^\varepsilon=\nu=(\nu_0,\nu_1)=(1/2,1/2)$. The limiting problem is

$$\bar {\cal P}^a:\left \{\begin{array}{lll}& \bar J^a( x......)\in {\cal A}^0}\bar J^a(x,U(\cdot)),\end{array}\right.$$

where we use $u^0(t) \equiv 0$. Let us set the function

$$\bar U(x)=(\bar u^0(x),\bar u^1(x))\equiv (0, 1/2)$$ (5.12)

to be a feedback control for $\bar {\cal P}^a$. Clearly the cost associated with (5.12) is zero. Since zero is the lowest possible cost, our solution is optimal and $\lambda=0$. Furthermore, since $\bar U(x)$ is locally Lipschitz in x and satisfies hypotheses (5.9)-(5.11), Theorem 5.4 implies that $$u^{\varepsilon}(x, m(\varepsilon, t))=I_{\{m(\varepsilon, t)=1\}}\bar u^1(x)$$

is an asymptotically optimal feedback control for $\bar {\cal P}^{a,\varepsilon}$.

Remark 5.1   It is possible to obtain other optimal feedback controls for Example 5.1. It is also possible to provide examples with nonzero production cost, for which Lipschitz feedback controls satisfying (5.9)-(5.11) can be obtained, and their optimality asserted by a verification theorem similar to Theorem 4.3 in Sethi, Suo, Taksar, and Yan (1998).

Remark 5.2   A similar averaging approach is introduced in Altman and Gaitsgory (1993) and Altman and Gaitsgory (1997), Nguyen and Gaitsgory (1997), Shi, Altman and Gaitsgory (1998), Nguyen (1999) and references there in. They consider a class of nonlinear hybrid systems in which the parameters of the dynamics of the system may jump at discrete moments of time, according to a controlled Markov chain with finite states and action spaces. They assume that the unit of the length of intervals between the jumps is small. They prove that the optimal solution of the hybrid systems governed by the controlled Markov chain can be approximated by the solution of a limiting deterministic optimal control problem.