4.2 Optimal control of dynamic flowshops

We consider the same dynamic system as the one given in Section 2.2, i.e., we consider the system defined by (2.5). But here we do not minimize the total discounted cost. Instead our problem is to find an admissible control ${\mbox{\boldmath$u$ }}(\cdot)$ that minimizes the long-run average cost function

$$J({\mbox{\boldmath$x$ }}^{0},{\mbox{\boldmath$m$ }}^{0},{\m......}G({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$u$ }}(t))dt,$$ (4.17)

where $G(\cdot,\cdot)$ defines the cost of surplus and production given in Section 2.2,${\mbox{\boldmath$x$ }}(t)$ is the state process corresponding to the control${\mbox{\boldmath$u$ }}(t)$ with ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$, and ${\mbox{\boldmath$m$ }}^{0}$ is the initial value of${\mbox{\boldmath$m$ }}(t)$.

Before beginning the discussion of this problem, we give some requirements on the cost function and the machine capacity process$\{{\mbox{\boldmath$m$ }}(t): t \geq 0\}$. In place of Assumptions 2.4 and 2.5 of Section 2.2, we impose the following assumptions on the process${\mbox{\boldmath$m$ }}(t)=(m_{1}(t),\cdots ,m_{N}(t))$ throughout this section.

Assumption 4.4   The Markov process $\{{\mbox{\boldmath$m$ }}(t): t \geq 0\}$ is strongly irreducible and has the stationary distribution $p_{\mbox{{\footnotesize\boldmath$m$ }}^{j}}$,$j=1,\cdots,p$. Let $p_{k}=\sum_{j=1}^{p} m_{k}^{j}p_{\mbox{{\footnotesize\boldmath$m$ }}^{j}}$. Assume that

$$\min_{1\leq k\leq N}p_{k}>z.$$

Remark 4.6   Assumption 4.4 is not needed in the discounted case. It is clear that this assumption is necessary for the finiteness of the long-run average cost in the case when $G(\cdot,\cdot)$ goes to $+\infty$ as $x_{N}\rightarrow-\infty$.As in Section 2.2, we use ${\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ to denote the set of all admissible controls with respect to ${\mbox{\boldmath$x$ }}\in S$ and ${\mbox{\boldmath$m$ }}(0)={\mbox{\boldmath$m$ }}$. Let $\lambda ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ denote the minimal expected cost, i.e.,

$$\lambda ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\in......h$m$ }})}J({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}).$$ (4.18)

For writing the HJBDD equation for our problem, we first introduce some notation. Let ${\cal G}$ denote the family of real-valued functions $f(\cdot,\cdot)$ defined on $S\times {\cal M}$ such that (i) $f(\cdot ,{\mbox{\boldmath$m$ }})$ is convex for any ${\mbox{\boldmath$m$ }}\in {\cal M}$; (ii) there exists a function $C_4({\mbox{\boldmath$x$ })}$ such that for any ${\mbox{\boldmath$m$ }}\in {\cal M}$ and any ${\mbox{\boldmath$x$ }, \\mbox{\boldmath$x$ }}^{\prime }{\in }S$, $$\vert f({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-f({\......\mbox{\boldmath$x$ }}-{\mbox{\boldmath$x$ }}^{\prime }\vert.$$

Consider now the following equation:

$$\lambda =\inf_{{\footnotesize\mbox{\boldmath$u$ }}\in U({\f......{\mbox{\boldmath$x$ }},\cdot )({\mbox{\boldmath$m$ }}),$$ (4.19)

where $\lambda$ is a constant, $f(\cdot ,\cdot )\in {\cal G},$ and $\partial _{\mbox{{\footnotesize\boldmath$r$ }}}g({\mbox{\boldmath$x$ }})$ denotes the directional derivative of function $g({\mbox{\boldmath$x$ }})$ along the direction ${\mbox{\boldmath$r$ }}\in R^{N}$. For the definition of the directional derivatives, see Section 2.2.

Presman, Sethi, and Zhang (1999a) prove the following verification theorem.

Theorem 4.8   Assume (i) $(\lambda ,f(\cdot ,\cdot ))$with $f(\cdot ,\cdot )\in$${\cal G}$satisfies (4.19); (ii) there exists a constant function$\mbox{\boldmath$u$ }^{\ast }(\mbox{\boldmath$x$ },\mbox{\boldmath$m$ })$for which

$$\inf_{{\footnotesize\mbox{\boldmath$u$ }}\in U({\footnotesi......u$ }}^{\ast }({\mbox{\boldmath$x$ },\mbox{\boldmath$m$ }})),$$ (4.20)

and the equation$\dot{\mbox{\boldmath$x$ }}(t)=A{\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$m$ }}(t))(t)+Bz$, has for any initial condition (${\mbox{\boldmath$x$ }}^{\ast}(0),\mbox{\boldmath$m$ }(0))=({\mbox{\boldmath$x$ }}^{0},\mbox{\boldmath$m$ }^{0})$, a solution ${\mbox{\boldmath$x$ }}^{\ast }(t)$such that

$$\lim_{T\rightarrow \infty }\frac{Ef({\mbox{\boldmath$x$ }}^{\ast }(T),{\mbox{\boldmath$m$ }}(T))}{T}=0.$$ (4.21)

Then$\mbox{\boldmath$u$ }^{\ast }(t)=\mbox{\boldmath$u$ }^{\ast }( \mbox{\boldmath$x$ }^{\ast }(t),\mbox{\boldmath$m$ }(t))$ is an optimal control. Furthermore,$\lambda (\mbox{\boldmath$x$ }^{0},\mbox{\boldmath$m$ } ^{0})$does not depend on$\mbox{\boldmath$x$ }^{0}$and${\mbox{\boldmath$m$ }}^{0}$and it coincides with $\lambda$. Moreover, for any T>0,

$$f({\mbox{\boldmath$x$ }}^{0},{\mbox{\boldmath$m$ }}^{0}) \inf_{{\footnotesize\mbox{\boldmath$u$ }}(\cdot )\in {\cal A}({\......ambda \right) dt+f({\mbox{\boldmath$x$ }}(T),{\mbox{\boldmath$m$ }}(T))\right]$$ =

$$E\left[ \int_{0}^{T}\left( G({\mbox{\boldmath$x$ }}^{\ast }(t),{......ht) dt+f({\mbox{\boldmath$x$ }}^{\ast }(T),{\mbox{\boldmath$m$ }}(T))\right] .$$ = (4.22)

Note that Theorem 4.8 explains why equation (4.19) is the Hamilton-Jacobi-Bellman equation for our problem and why the function$f(\cdot,\cdot)$ from Theorem 4.8 is called a potential function.

The next question is the existence of a solution to (4.19), that is, is there a pair $(\lambda, W(\cdot,\cdot))$ that satisfies (4.19)? To get the existence, we use the vanishing discount approach. Consider the corresponding control problem with the cost discounted at the rate $\rho$. For ${\mbox{\boldmath$u$ }}(\cdot )\in {\cal A}({ \mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$, we define the expected discounted cost as

$$J^{\rho }({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }},{......t}G({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$u$ }}(t))dt.$$

Define the value function of the discounted cost problem as

$$V^{\rho }({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\i...... }},{\mbox{\boldmath$m$ }},{\mbox{\boldmath$u$ }}(\cdot )).$$

Just as in Section 4.1, we need a technical lemma that states the finiteness of the rth moment of the time from any given state to any other state.

Lemma 4.2   For any $(\mbox{\boldmath$x$ }^{0},\mbox{\boldmath$m$ }^{0})\in S\times {\cal M}$ and $(\mbox{\boldmath$y$ },\mbox{\boldmath$m$ }^{\prime })\in S\times {\cal M}$, there exists a control policy${\mbox{\boldmath$u$ }}(t), t\geq 0$, such that for any$r\geq 1$,

$$E\eta ^{r}\leq C_{1}(r)\left( 1+\sum_{k=1}^{N-1}\vert x_{k}^{0}-y_{k}\vert^{r}\right),$$ (4.23)

where $$\eta =\inf \{t\geq 0: \ ({\mbox{\boldmath$x$ }}(t),{\mbox{\......m$ }}(t))=({\mbox{\boldmath$y$ }},{\mbox{\boldmath$m$ }}')\},$$

and $\mbox{\boldmath$x$ }(t),t\geq 0,$is the surplus process corresponding to the control policy ${\mbox{\boldmath$u$ }}(t)$and the initial condition $({\mbox{\boldmath$x$ }}(0),{\mbox{\boldmath$m$ }}(0))=({\mbox{\boldmath$x$ }}^{0},{\mbox{\boldmath$m$ }}^{0})$.
 

Because it is very tricky to construct the desired control, we give here only the outline of the construction procedure. We begin by modifying the process ${\mbox{\boldmath$m$ }}(t)$ in such a way that the modified average capacity of any machine is larger than the modified average capacity of the machine that follows it, and that the modified average capacity of the last machine is larger than z. Then we alternate between these two policies described below. In the first policy, the production rate at each machine is the maximum admissible modified capacity. In the second policy, we stop producing at the first machine and have the maximum possible production rate at the other machines under the restriction that the content of each buffer k, $1\leq k\leq N-1$, is not less than y_k. The first policy is used until such time when the content of the first buffer exceeds the value y₁ and the content of each buffer k,$2\leq k\leq N$, exceeds the value a+y_k for some a>0. At that time we switch to the second policy. We use the second policy until such time when the content of the last buffer drops to the level y_N. After that we revert to the first policy, and so on. Using this alternating procedure, it is possible to specify $\eta$ and provide an estimate for it. For a complete proof, see Presman, Sethi, and Zhang (1999a).

Based on this lemma, Presman, Sethi, and Zhang (1999a) give the next two theorems which are concerned with the solution of (4.19).

Theorem 4.9   There exists a sequence $\{\rho_{k}:k\geq 1\}$ with $\rho _{k}\rightarrow 0$ as$k\rightarrow \infty$ such that for $(\mbox{\boldmath$x$ },\mbox{\boldmath$m$ })\in S\times {\cal M}$:

$$\begin{eqnarray*}&&\lim_{k\rightarrow \infty }\rho _{k}V^{\rho _{k}}({\mbox{\b......m$ }}^{0})]=W({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}),\end{eqnarray*}$$ where$W(\mbox{\boldmath$x$ },\mbox{\boldmath$m$ })\in {\cal G}$.

Let $\bigtriangledown (V^{\rho _{k}}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-V^{\rho _{k}}(0,{\mbox{\boldmath$m$ }}^{0}))$ be the derivative of$V^{\rho _{k}}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-V^{\rho _{k}}(0,{\mbox{\boldmath$m$ }}^{0}))$ at the point ${\mbox{\boldmath$x$ }}$ where the derivative exists.

Theorem 4.10   In our problem, (i) $\lambda (\mbox{\boldmath$x$ }^{0},\mbox{\boldmath$m$ } ^{0})$ does not depend on $( \mbox{\boldmath$x$ }^{0},\mbox{\boldmath$m$ }^{0})$. (ii) The pair$(\lambda, W(\cdot,\cdot))$defined in Theorem 4.9 satisfies (4.19) on S^o, where S^o is the interior of the setS. (iii) If there exists an open subset $\hat S$ of S such that $S^b \subseteq \hat S^b$, where $\hat S^b$ is the boundary of $\hat S$, and$\{\bigtriangledown (V^{\rho _{k}}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-V^{\rho _{k}}(0,{\mbox{\boldmath$m$ }}^{0})):k \geq 1\}$ is uniformly equi-Lipschitzian on $\hat S$, then the pair$(\lambda, W(\cdot,\cdot))$defined in Theorem 4.9 is a solution to (4.19).

Remark 4.7   Note that the statement (i) of Theorem 4.10 follows from Theorem 4.9. The statement (ii) of Theorem 4.10 follows from Theorem 4.9 and a simple limiting procedure.