3.1 Hierarchical controls for single or parallel machine  systems

Sethi and Zhang (1994b) and Sethi, Zhang, and Zhou (1994) consider a stochastic manufacturing system with surplus (state)${\mbox{\boldmath$x$ }}^{\varepsilon}(t)\in R^n$ and production rate (control)${\mbox{\boldmath$u$ }}^{\varepsilon}(t)\in R^n_+$ satisfying

$$\dot {\mbox{\boldmath$x$ }}^{\varepsilon}(t)={\mbox{\boldmath$u$ ......)-{\mbox{\boldmath$z$ }}, \{\mbox{\boldmath$x$ }} (0)= {\mbox{\boldmath$x$ }},$$ (3.1)

where ${\mbox{\boldmath$z$ }}\in R^n_+$ is the constant demand rate and ${\mbox{\boldmath$x$ }}$ is the initial surplus ${\mbox{\boldmath$x$ }}^{\varepsilon}(t)$.

Let $m(\varepsilon,t)\in {\cal M}=\{0,1,2,\cdots, p \}$ denote the machine capacity process of our manufacturing system, where$\varepsilon$ is a small parameter to be specified later. Then the production rate ${\mbox{\boldmath$u$ }}^{\varepsilon}(t)\geq 0$ must satisfy${\mbox{\boldmath$r$ }}\cdot {\mbox{\boldmath$u$ }}^{\varepsilon}(t)\leq m(\varepsilon,t)$ for some positive vector ${\mbox{\boldmath$r$ }}$. We consider the cost function$J^{\varepsilon}({\mbox{\boldmath$x$ }},m, {\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot))$ with$m(\varepsilon,0)=m$ and ${\mbox{\boldmath$x$ }}^{\varepsilon}(0)={\mbox{\boldmath$x$ }}$ defined by

$$J^{\varepsilon}({\mbox{\boldmath$x$ }},m,{\mbox{\boldmath$u$ }}^{......boldmath$x$ }}^{\varepsilon}(t))+c({\mbox{\boldmath$u$ }}^{\varepsilon}(t))]dt,$$ (3.2)

where $\rho>0$ is the discount rate, $h(\cdot)$ is the cost of surplus, and $c(\cdot)$ is the cost of production. The problem is to find a control ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\geq 0$ with${\mbox{\boldmath$r$ }}\cdot {\mbox{\boldmath$u$ }}^{\varepsilon}(t)\leq m(\varepsilon,t)$, that minimizes $J^{\varepsilon}({\mbox{\boldmath$x$ }},k,{\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot))$. We make the following assumptions on the machine capacity process and the cost function on production rate and the surplus.

Assumption 3.1$c({\mbox{\boldmath$u$ }})$ and $h({\mbox{\boldmath$x$ }})$ are convex. Furthermore, for all ${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}'$, there exist constants C₃₁ and$\kappa_{31}$ such that $$0\leq h({\mbox{\boldmath$x$ }})\leq C_{31}(1+\vert{\mbox{\boldmath$x$ }}\vert^{\kappa_{31}+1}) \mbox{ and }$$

and

$$\vert h({\mbox{\boldmath$x$ }})-h({\mbox{\boldmath$x$ }}') ......}) \vert {\mbox{\boldmath$x$ }}-{\mbox{\boldmath$x$ }}'\vert.$$

Assumption 3.2   Let $Q^{(\varepsilon)}=Q^{(1)}+\varepsilon^{-1}Q^{(2)}$, where$Q^{(\ell)}$ is an (p+1) x (p+1) matrix such that $Q^{(\ell)}=(q_{ij}^{(\ell)})$ with $q^{(\ell)}_{ij}\geq 0$ if $i\neq j$ and$q^{(\ell)}_{ii}=-\sum_{j \neq i}q^{(\ell)}_{ij}$, for $\ell=1,2.$ The capacity process $0\leq m(\varepsilon,t)\in{\cal M}$ is a finite state Markov process governed by $Q^{(\varepsilon)}$, that is,

$$\begin{eqnarray*}L\psi(\cdot)(i)=\varepsilon^{-1}Q\psi(\cdot)(i),\end{eqnarray*}$$ for any function $\psi$ on ${\cal M}$.

Assumption 3.3   The Q⁽²⁾ is weakly irreducible, i.e., the equations $$\nu Q^{(2)}=0 \ \mbox{and} \ \sum_{j=0}^p\nu_j=1$$ have a unique solution$\nu=(\nu_0,\nu_1,\cdots,\nu_p)>0$. We call $\nu$ to be the equilibrium distribution of Q.

Remark 3.1   Jiang and Sethi (1991) and Khasminskii, Yin, and Zhang (1997) consider a model in which the irreducibility Assumption 3.3 can be relaxed to incorporate machine state processes with a generator that consists of several irreducible submatrices. In these models, some jumps are associated with a fast process, while others are associated with a slow process; see Section 5.5.

Definition 3.1   We say that a control ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)=\{{\mbox{\boldmath$u$ }}^{\varepsilon}(t):\; t\geq 0\}$ is admissible if

(i)

${\mbox{\boldmath$u$ }}^{\varepsilon}(t)\geq 0$ is an ${\cal F}_t=\sigma\{m(\varepsilon,s),0 \leq s\leq t\}$ adapted measurable process;

(ii)

${\mbox{\boldmath$r$ }}\cdot {\mbox{\boldmath$u$ }}^{\varepsilon}(t)\leq m(\varepsilon,t)$ for all $t\geq 0$.

We use ${\cal A}^{\varepsilon}(m)$ to denote the set of all admissible controls with the initial condition $m(\varepsilon,0)=k$. Then our control problem can be written as follows:

$${\cal P}^{\varepsilon}:\left\{\begin{array}{lll}\mbox{minimize}......ldmath$x$ }},m,{\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)).\end{array}\right.$$ (3.3)

Similar to Theorem 2.1, we can show that the value function $v^{\varepsilon}({\mbox{\boldmath$x$ }},m)$ is convex in${\mbox{\boldmath$x$ }}$ for each m. The value function $v^{\varepsilon}(\cdot, \cdot)$ satisfies the dynamic programming equation

$$\rho v^{\varepsilon}( {\mbox{\boldmath$x$ }},m) \min_{{\mbox{\boldmath$u$ }}\geq 0,{\mbox{\boldmath$r$ }}\cdot{\......\mbox{\boldmath$x$ }},m) +h({\mbox{\boldmath$x$ }})+c({\mbox{\boldmath$u$ }})]$$ =

$$\ \ \ +Lv^{\varepsilon}({\mbox{\boldmath$x$ }},\cdot)(m), m\in{\cal M},$$ (3.4)

in the sense of viscosity solutions.

Sethi, Zhang, and Zhou (1994) consider a control problem in which the stochastic machine capacity process is averaged out. Let ${\cal A}^0$ denote the control space

$$\begin{eqnarray*}{\cal A}^0=\{ U(t)=({\mbox{\boldmath$u$ }}^0(t),{\mbox{\boldm......}}\cdot {\mbox{\boldmath$u$ }}^i(t)\leq i, \ 0 \leq i \leq p\}.\end{eqnarray*}$$ Then we define the control problem ${\cal P}^0$ as follows:

$${\cal P}^0:\left\{\begin{array}{lll}\mbox{minimize}& J^0({\mbox......J^0({\mbox{\boldmath$x$ }}, {\mbox{\boldmath$u$ }}(\cdot)).\end{array}\right.$$ (3.5)

Sethi and Zhang (1994b) and  Sethi, Zhang, and Zhou (1994) construct a solution of ${\cal P}^{\varepsilon}$ from a solution of ${\cal P}^0$ and show it to be asymptotically optimal as stated below.

Theorem 3.1 (i)   There exists a constant C₃₂ such that

$$\vert v^{\varepsilon}({\mbox{\boldmath$x$ }},m)-v({\mbox{\bol......\mbox{\boldmath$x$ }}\vert^{\kappa_{31}})\sqrt {\varepsilon}.$$

(ii) Let$U(\cdot)\in {\cal A}^0$denote an$\varepsilon$-optimal control. Then${\mbox{\boldmath$u$ }}^{\varepsilon}(t)=\sum_{i=0}^p I_{\{m(\varepsilon,t)=i\}}{\mbox{\boldmath$u$ }}^i(t)$is asymptotically optimal, i.e.,

$$\left\vert J^{\varepsilon}({\mbox{\boldmath$x$ }},m,{\mbox{\bold......q C_{32} (1+\vert{\mbox{\boldmath$x$ }}\vert^{\kappa_{31}})\sqrt{\varepsilon}.$$ (3.6)

(iii) Assume in addition that$c({\mbox{\boldmath$u$ }})$is twice differentiable with$(\frac{\partial^2}{\partial u_i\partialu_j})\geq c_0I_{n\times n}$, the function$h(\cdot)$is differentiable, and constants C₃₃and $\kappa_{32}>0$exist such that $$\begin{eqnarray*}\left\vert h({\mbox{\boldmath$x$ }}+{\mbox{\boldmath$y$ }})-h......h$x$ }}\vert^{\kappa_{32}}) \vert{\mbox{\boldmath$y$ }}\vert^2.\end{eqnarray*}$$ Then, there exists a locally Lipschitz optimal feedback control$U^*({\mbox{\boldmath$x$ }})$ for ${\cal P}^0$. Let

$${\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }},m(\varepsilon, t)......I_{\{m(\varepsilon, t)=i\}}{\mbox{\boldmath$u$ }}^{i*}({\mbox{\boldmath$x$ }}).$$ (3.7)

Then,${\mbox{\boldmath$u$ }}^{\varepsilon}(t)={\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }}(t),m(\varepsilon,t))$is an asymptotically optimal feedback control for${\cal P}^{\varepsilon}$with the convergence rate of$\sqrt{\varepsilon}$, i.e., (3.6) holds.
Remark 3.2   Part (ii) of the theorem states that from an $\varepsilon$-optimal open-loop control of the limiting problem, we can construct an$\sqrt{\varepsilon}$-optimal open-loop control for the original problem. With further restrictions on the cost function, Part (iii) of the theorem states that from the$\varepsilon$-optimal feedback control of the limiting problem, we can construct an $\sqrt{\varepsilon}$-optimal feedback control for the original problem.
Remark 3.3   It is important to point out that the hierarchical feedback control (3.7) can be shown to be a threshold-type control if the production cost$c({\mbox{\boldmath$u$ }})$ is linear. Of course, the value of the threshold depends on the state of the machines. For single product problems with constant demand, this means that production takes place at the maximum rate if the inventory is below the threshold, no production takes place above it, and production rate equals the demand rate once the threshold is attained. This is also the form of the optimal policy for these problems as shown, e.g., in Kimemia and Gershwin (1983), Akella and Kumar (1986), and Sethi, Soner, Zhang, and Jiang (1992a). The threshold level for any given machine capacity state in these cases is also known as a hedging point in that state following Kimemia and Gershwin (1983). In these simple problems, asymptotic optimality is maintained as long as the threshold, say, $\theta (\varepsilon),$ goes to 0 as $\varepsilon \rightarrow 0.$ Thus, there is a possibility of obtaining better policies than (3.7) that are asymptotically optimal. In fact, one can even minimize within the class of threshold policies for the parallel-machines problems discussed in this section.

Remark 3.4   Gershwin (1989) constructs a solution for ${\cal P}^{\varepsilon}$ by solving a secondary optimization problem and conjectures his solution to be asymptotically optimal.  Sethi and Zhang (1994b), Remark (6.3) prove the conjecture. It should be noted, however, that the conjecture cannot be extended to include the simple two-machine example in Gershwin (1989) with one flexible and another inflexible machine. The presence of the inflexible machine requires aggregation of some products at the level of ${\cal P}^0$ and subsequent disaggregation in the construction of a solution for ${\cal P}^{\varepsilon}$. Also note that Gershwin, Caramanis, and Murray (1988), in their simulation study, consider hierarchical systems that do not involve aggregation and disaggregation.
 

Soner (1993) and Sethi and Zhang (1994c) consider ${\cal P}^{\varepsilon}$ in which $Q=\frac{1}{\varepsilon}Q({\mbox{\boldmath$u$ }})$ depends on the control variable ${\mbox{\boldmath$u$ }}$. They show that under certain assumptions, the value function $v^{\varepsilon}$ converges to the value function of a limiting problem. Moreover, the limiting problem can be expressed in the same form as ${\cal P}^0$ except that the equilibrium distribution $\nu_i, i = 0, 1, 2, \cdots, p,$ are now control-dependent. Thus $\nu_i$ in Assumption 3.3 is now replaced by $\nu_i ({\mbox{\boldmath$u$ }}(t))$ for each i; see also (3.31). Then an asymptotically optimal control for${\cal P}^{\varepsilon}$ can be obtained as in (3.7) from the optimal control of the limiting problem. As yet, no convergence rate has been obtained in this case.

An example of $Q({\mbox{\boldmath$u$ }})$ in a one-machine case with two (up and down) states is

$$Q({\mbox{\boldmath$u$ }}) = \left( \begin{array}{cc} -\mu & \mu \......{\mbox{\boldmath$u$ }})& - \lambda({\mbox{\boldmath$u$ }})\end{array}\right).$$

Thus, the breakdown rate $\lambda({\mbox{\boldmath$u$ }})$ of the machine depends on the rate of production ${\mbox{\boldmath$u$ }}$, while the repair rate $\mu$ is independent of the production rate. These are reasonable assumptions in practice.