2.2 Optimal control of dynamic flowshops

We consider a manufacturing system producing a single finished product using N machines in tandem that are subject to breakdown and repair. We are given a Markov chain${\mbox{\boldmath$m$ }}(t)=(m_1(t),...,m_N(t))$, where m_j(t), j=1,...,N, is the capacity of the jth machine at time t. We use u_i(t) to denote the input rate to the jth machine, j=1,...,N, and x_j(t) to denote the number of parts in the buffer between the jth and (j+1)th machines, j=1,...,N-1. Finally, the surplus is denoted by x_N(t). The dynamics of the system can then be written as follows:

$$\dot {\mbox{\boldmath$x$ }}(t)=A{\mbox{\boldmath$u$ }}(t)+Bz, \ {\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }},$$ (2.5)

where $$\begin{eqnarray*}A=\left(\begin{array}{ccccc}1&-1&0&...&0\\0&1&-1&...&0......gin{array}{c}0\\0\\\vdots\\-1\end{array}\right).\end{eqnarray*}$$ Since the number of parts in the internal buffers cannot be negative, we impose the state constraints $x_j(t)\geq 0$, j=1,...,N-1. To formulate the problem precisely, let$S=[0,\infty)^{N-1}\times (-\infty, \infty)$ denote the state constraint domain, and let ${\mbox{\boldmath$m$ }}(t)$ be a finite Markov chain with the state space ${\cal M}=({\mbox{\boldmath$m$ }}^1,...,{\mbox{\boldmath$m$ }}^p)$, where${\mbox{\boldmath$m$ }}^{\ell}=(m_1^{\ell},...,m_N^{\ell})$($\ell=1,...,p$). For${\mbox{\boldmath$m$ }}=(m_1,...,m_N)\in {\cal M}$,$m_j\geq 0$, j=1,...,N, let

$$U({\mbox{\boldmath$m$ }})=\{{\mbox{\boldmath$u$ }}=(u_1,...,u_N): 0\leq u_j \leq m_j, \ j=1,...,N\},$$ (2.6)

and for ${\mbox{\boldmath$x$ }}\in S$, let

$$U({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}) \{{\mbox{\boldmath$u$ }}: {\mbox{\boldmath$u$ }}\in U({\mbox{\boldmath$m$ }}) \\mbox{and}$$ =

$$\ \ \ \ x_i=0 \Rightarrow u_j-u_{j+1}\geq0, \ j=1,...,N-1\}.$$ (2.7)

The matrix A has an inverse denoted as A^-1. Let the$\sigma$-field ${\cal F}_t=\{{\mbox{\boldmath$m$ }}(s): \ 0 \leq s \leq t\}$.

Definition 2.6   We say that a control ${\mbox{\boldmath$u$ }}(\cdot)$ is admissible with respect to the initial value ${\mbox{\boldmath$x$ }}\in S$ and${\mbox{\boldmath$m$ }}\in {\cal M}$ if

(i)

${\mbox{\boldmath$u$ }}(\cdot)$ is an ${\cal F}_t$-adapted process;

(ii)

${\mbox{\boldmath$u$ }}(t) \in U({\mbox{\boldmath$m$ }}(t))$ for all $t\geq 0$;

(iii)

the corresponding state process${\mbox{\boldmath$x$ }}(t)=(x_1(t),...,x_N(t))\in S$ with ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$ for all $t\geq 0$.

Let ${\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ denote the set of all admissible controls.

Definition 2.7   A function ${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ is call an admissible feedback control, or simply feedback control, if

(i)

for any given initial ${\mbox{\boldmath$x$ }}$, the equation

$$\dot {\mbox{\boldmath$x$ }}(t)=A{\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$m$ }}(t))+Bz$$

has a unique solution with ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$ and${\mbox{\boldmath$m$ }}(0)={\mbox{\boldmath$m$ }}$;

(ii)

${\mbox{\boldmath$u$ }}(\cdot)=\{{\mbox{\boldmath$u$ }}(t)={\mbox{\boldmath$u$ }......}}(t)), \t\geq 0\}\in {\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$.

The problem is to find an admissible control ${\mbox{\boldmath$u$ }}(\cdot)$ that minimizes the cost function

$$J({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }},{\mbox{\boldmath$......^{\infty}_0e^{-\rhot}G({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$u$ }}(t))dt,$$ (2.8)

where $G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ defines the cost function of surplus${\mbox{\boldmath$x$ }}$ and production rate ${\mbox{\boldmath$u$ }}$,${\mbox{\boldmath$m$ }}$ is the initial value of ${\mbox{\boldmath$m$ }}(t)$, and $\rho>0$ is the discount rate. The value function is then defined as

$$v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\inf_{{\mbox{\bo......J({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }},{\mbox{\boldmath$u$ }}(\cdot)).$$ (2.9)

We impose the following assumptions on the Markov process${\mbox{\boldmath$m$ }}(t)=(m_1(t),...,m_N(t))$ and the cost function$G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$:

Assumption 2.4$G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$u$ }})$ is a nonnegative jointly convex function that is strictly convex in either ${\mbox{\boldmath$x$ }}$ or ${\mbox{\boldmath$u$ }}$ or both. For all ${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}' \in S$ and ${\mbox{\boldmath$u$ }},{\mbox{\boldmath$u$ }}' \inU({\mbox{\boldmath$m$ }}^j)$, j=1,...,p, there exist constants C₂₈ and$\kappa_{24}$ such that

$$\vert G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$u$ }})-G({\......+\vert{\mbox{\boldmath$u$ }}-{\mbox{\boldmath$u$ }}'\vert].$$
Assumption 2.5   The capacity process ${\mbox{\boldmath$m$ }}(t)\in {\cal M}$ is a finite state Markov chain with the following infinitesimal generator Q: $$Qf(\cdot)({\mbox{\boldmath$m$ }})=\sum_{{\mbox{\boldmath$m$...... }}'}[f({\mbox{\boldmath$m$ }}')-f({\mbox{\boldmath$m$ }})]$$ for some $q_{{\mbox{\boldmath$m$ }}{\mbox{\boldmath$m$ }}'}\geq 0$ and any function $f(\cdot)$ on${\cal M}$.

The problem of the flowshop with internal buffers and the resulting state constraints is much more complicated. Certain boundary conditions need to be taken into account for the associated HJB equation. Optimal control policy can no longer be described simply in terms of some hedging points.

Lou, Sethi, and Zhang (1994) show that the optimal control policy for a two-machine flowshop with linear costs of production can be given in terms of two switching manifolds. However, the switching manifolds are not easy to obtain. One way to compute them is to approximate them by continuous piecewise-linear functions as done by Van Ryzin, Lou, and Gershwin (1993) in the absence of production costs.

To rigorously deal with the general flowshop problem under consideration, we write the HJB equation in terms of the Directional Derivatives (HJBDD) at inner and boundary points. So, we first give the notion of these derivatives and some related properties of convex functions.

Definition 2.8   A function $f({\mbox{\boldmath$x$ }})$,${\mbox{\boldmath$x$ }}\in R^N$ is said to have a directional derivative$\frac{\partialf({\mbox{\boldmath$x$ }})}{\partial {\mbox{\boldmath$n$ }}}$ along the direction ${\mbox{\boldmath$n$ }}\in R^N$ if the following limit exists, i.e.,

$$\frac{\partialf({\mbox{\boldmath$x$ }})}{\partial {\mbox{......eta{\mbox{\boldmath$n$ }})-f({\mbox{\boldmath$x$ }})}{\beta}.$$ If a function $f({\mbox{\boldmath$x$ }})$ is differentiable at ${\mbox{\boldmath$x$ }}$, then$\frac{\partialf({\mbox{\boldmath$x$ }})}{\partial {\mbox{\boldmath$n$ }}}$ exists for every${\mbox{\boldmath$n$ }}$ and $$\frac{\partial f({\mbox{\boldmath$x$ }})}{\partial {\mbox{\......$x$ }}}({\mbox{\boldmath$x$ }})\cdot{\mbox{\boldmath$n$ }}.$$

A continuous convex function defined on a convex domain $\sum$ is differentiable almost everywhere and has a directional derivative both along any direction at any inner point of $\sum$ and along any admissible direction (i.e., such direction ${\mbox{\boldmath$n$ }}$ that${\mbox{\boldmath$x$ }}+\beta{\mbox{\boldmath$n$ }}\in \sum$ for some $\beta>0$) at any boundary point of $\sum$. Note that $\{A{\mbox{\boldmath$u$ }}+Bz:{\mbox{\boldmath$u$ }}\inU({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})\}$ is the set of admissible directions at${\mbox{\boldmath$x$ }}$. We can formally write the HJB equation in terms of directional derivative (HJBDD) for the problem as

$$\rho v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\inf_{{\mbo......dmath$u$ }})\right\}+ Qv({\mbox{\boldmath$x$ }},\cdot)({\mbox{\boldmath$m$ }}).$$ (2.10)

Similar to Theorem 2.1, Presman, Sethi, and Zhang (1995) prove the following theorem.

Theorem 2.6 (i)   The value function $v(\cdot,\cdot)$ is convex and continuous on S and satisfies the condition

$$\vert v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-v({\mbox{\......}'\vert^{\kappa_{24}})\vert{\mbox{\boldmath$x$ }}-{\mbox{\boldmath$x$ }}'\vert$$ (2.11)

for some positive constant C₂₉ and all${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}' \in S$.
(ii) The value function $v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ satisfies the HJBDD equation (2.10) for all${\mbox{\boldmath$x$ }}\in S$.

Furthermore, by introducing an equivalent deterministic problem to the stochastic problem, Presman, Sethi, and Zhang (1995) give the verification theorem along with the existence of the optimal control.

Theorem 2.7 (i)   The optimal control${\mbox{\boldmath$u$ }}^*(\cdot)\in {\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$exists, is unique, and can be represented as a feedback control, i.e., there exists a function ${\mbox{\boldmath$u$ }}(\cdot,\cdot)$such that for any${\mbox{\boldmath$x$ }}$, we have

$${\mbox{\boldmath$u$ }}^*(t)={\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }}^*(t),{\mbox{\boldmath$m$ }}(t)), \ \ t\geq 0,$$ where ${\mbox{\boldmath$x$ }}^*(\cdot)$is the optimal state process, the solution of (2.5) for${\mbox{\boldmath$u$ }}^*(\cdot)$, with${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$.
(ii) If some continuous convex function $\tildev({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$satisfies (2.10) and the growth condition (2.11) with ${\mbox{\boldmath$x$ }}'=0$, then$\tildev({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})\leq v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$. Moreover, if there is a feedback control${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$providing the infimum in (2.10) for$\tildev({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$, then$\tilde v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$, and${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$is an optimal feedback control.

(iii) Assume that $G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ is strictly convex in${\mbox{\boldmath$u$ }}$ for each fixed ${\mbox{\boldmath$x$ }}$. Let ${\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$denote the minimizer function of the right-hand side of (2.10). Then,

$$\dot {\mbox{\boldmath$x$ }}(t)=A{\mbox{\boldmath$u$ }}^*({\......(t))+Bz, \{\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }},$$ has a solution ${\mbox{\boldmath$x$ }}^*(t)$, and${\mbox{\boldmath$u$ }}(t)={\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }}^*(t),{\mbox{\boldmath$m$ }}(t))$ is the optimal control.
Remark 2.2   The method of dynamic programming plays an important role in solving Markovian stochastic optimal control problems. A typical approach for treating a dynamic programming equation is to use the notion of viscosity solutions introduced in Section 2.1. The viscosity solution approach is used in the case of the two-machine flowshop analyzed by Lou, Sethi, and Zhang (1994). Since the inventory in the internal buffers between the two machines is required to be nonnegative, the technique of the viscosity solution with state space constraints developed by Soner (1986) is needed in their case.

Remark 2.3   Presman, Sethi, and Suo (1997) study the N-machine flowshop with limited buffers. They show that Theorem 2.6 and Theorem 2.7 also hold in the limited buffer case.