3.2 Hierarchical controls for flowshops

For manufacturing systems with N machines in tandem, Sethi, Zhang, and Zhou (1992a) obtain a limiting problem. Then they use a near-optimal control of the limiting problem to construct an open-loop control for the original problem, which is asymptotically optimal as the rate of fluctuation in the machine states goes to infinity. To illustrate, let us consider a two-machine flowshop treated in Sethi, Yan, Zhang, and Zhou (1993). Let the Markov process${\mbox{\boldmath$m$ }}(\varepsilon,t)=(m_1(\varepsilon,t), m_2(\varepsilon,t))$ generated by an irreducible generator ${\varepsilon}^{-1}Q$ denote the machine capacity process. Here we assume that ${\mbox{\boldmath$m$ }}(\varepsilon, t)$ is a finite state Markov process with the state space ${\cal M}=({\mbox{\boldmath$m$ }}^1,...,{\mbox{\boldmath$m$ }}^p)$. Furthermore, we assume that Q is weakly irreducible with the stationary distribution$\nu=(\nu_1,..., \nu_p)$.

We denote the number of parts in the buffer between the first and the second machine called work-in-process as $x_1^{\varepsilon}(t)\geq 0$ and the difference of the real and planned cumulative productions called surplus at the second machine as $x_2^{\varepsilon}(t)$. Let$S=[0,\infty)\times R^1$ denote the state constraint domain and let z denote the constant demand rate. Then,

$$\begin{eqnarray*}\left\{\begin{array}{ll}&\dotx_1^{\varepsilon}(t)=u^{\v......silon}_2(t)-z,x^{\varepsilon}_2(0)=x_2.\end{array}\right.\end{eqnarray*}$$
Definition 3.2   We say that a control${\mbox{\boldmath$u$ }}^{\varepsilon}(t)=(u^{\varepsilon}_1(t),u^{\varepsilon}_2(t))$ is admissible with respect to ${\mbox{\boldmath$x$ }}\in S$ if:

(i)

${\mbox{\boldmath$u$ }}(\cdot)$is adapted to $\sigma \{{\mbox{\boldmath$m$ }}(\varepsilon,s):0\leq s\leq t\}$;

(ii)

$0\leq u_i^{\varepsilon}(t)\leqm_i(\varepsilon,t)$;

(iii)

${\mbox{\boldmath$x$ }}^{\varepsilon}(t)\in S$ for all$t\geq 0$.

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

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

Remark 3.5   The case of a finite capacity internal buffer, in which the state constraint domain is S=[0,M] x R¹ for some finite number M, is treated in Sethi, Zhang, and Zhou (1992b) and  Sethi, Zhang, and Zhou (1997). Recently, based on the Lipschitz continuity of the value function given by Presman, Sethi, and Suo (1997),  Sethi, Zhang and Zhang (1999c) give the hierarchical control for the N-machine flowshop with limited buffers.

For ${\mbox{\boldmath$x$ }}\in S$, let ${\cal A}^0({\mbox{\boldmath$x$ }})$ denote the set of the deterministic measurable controls

$$\begin{eqnarray*}U(\cdot)=({\mbox{\boldmath$u$ }}^1(\cdot),\cdots,{\mbox{\bold......u^1_1(\cdot),u^1_2(\cdot)),\cdots,(u^p_1(\cdot),u^p_2(\cdot))),\end{eqnarray*}$$ such that $0\leq u^j_i(t)\leq m^j_i$ for all $t\geq 0$, i=1,2 and j=1,2,...,p. We define the limiting problem $$\begin{eqnarray*}{\cal P}^0 :\left\{\begin{array}{cl} \mbox{ minimize}&J({\m......x$ }})}J({\mbox{\boldmath$x$ }}, U(\cdot)),\end{array}\right.\end{eqnarray*}$$ where $\nu=(\nu_1,\cdots,\nu_p)>0$ is the equilibrium distribution of Q.

It can be shown that there exists an$\varepsilon_0$, such that for all $0<\varepsilon\leq\varepsilon_0$ and ${\mbox{\boldmath$x$ }}\in S$, we have

$$\left\vert v^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmat...... }})-v({\mbox{\boldmath$x$ }})\right\vert=O(\varepsilon^{\frac{1}{2}-\delta}).$$ (3.9)

Similar to Theorem 3.1, for a given ${\mbox{\boldmath$x$ }}\in S$, we describe the procedure of constructing an asymptotic optimal control${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\in{\calA}^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ of the original problem ${\cal P}^{\varepsilon}$ beginning with any near-optimal control $\barU(\cdot)\in {\cal A}^0({\mbox{\boldmath$x$ }})$ of the limiting problem ${\cal P}^0$. First we focus on the open-loop control. Let us fix an initial state ${\mbox{\boldmath$x$ }}\in S$. Let $\barU(\cdot)=(\bar {\mbox{\boldmath$u$ }}^1(\cdot),\cdots,\bar {\mbox{\boldmath$u$ }} ^p(\cdot))\in{\cal A}^0$, where $\bar {\mbox{\boldmath$u$ }}^j(t)=(\bar u^j_1(t),\baru^j_2(t))$ is an $\varepsilon^{\frac{1}{2}-\delta}$-optimal control for ${\cal P}^0$, i.e., $$\begin{eqnarray*}\vert J({\mbox{\boldmath$x$ }},\bar U(\cdot))-v({\mbox{\boldmath$x$ }})\vert\leq\varepsilon^{\frac{1}{2}-\delta}.\end{eqnarray*}$$ Because the work-in-process level must be nonnegative, unlike in the case of parallel machine systems, the control $$\sum_{i=1}^p I_{\{{\mbox{\boldmath$m$ }}(\varepsilon, t)={\mbox{\boldmath$m$ }}^i\}}\bar{\mbox{\boldmath$u$ }}^i(t)$$

may not be admissible. Thus, we need to modify the process given in Section 2.1. Let us define a time $t^*\leq\infty$ as follows:

$$\begin{eqnarray*}t^*=\inf\left\{t:\int^t_0[\sum_{j=1}^p (m^j_1-\nu_j \bar u^j_......aru^j_2(s))]ds\geq \varepsilon^{\frac{1}{2}-\delta} \right\}.\end{eqnarray*}$$ We define another control process $\tilde U(t)=({\tilde{\mbox{\boldmath$u$ }}}^1(\cdot),\cdots,{\tilde{\mbox{\boldmath$u$ }}}^p (\cdot))$ as follows: For $j=1,\cdots,p$,

$${\tilde {\mbox{\boldmath$u$ }}}^j(t)=({\tilde u}^j_1(t),{\tilde u......*,\\(\bar u^j_1(t),\bar u^j_2(t))&\mbox{if} \ \ t\geq t^*.\end{array}\right.$$ (3.10)

It is easy to check that $\tilde U(\cdot)\in {\cal A}^0({\mbox{\boldmath$x$ }})$. Let

$${\mbox{\boldmath$w$ }}^{\varepsilon}(t)=(w_1^{\varepsilon}(t),w_2^{\varepsilon}(t)) \sum_{j=1}^p(\tilde u^j_1(t),\tildeu^j_2(t))\nu_jI_{\{{\mbox{\boldmath$m$ }}(\varepsilon, t)={\mbox{\boldmath$m$ }}^j\}}$$ =

$$\sum_{j=1}^p\nu_j{\tilde {\mbox{\boldmath$u$ }}}^j(t)I_{\{{\mbox{\boldmath$m$ }}(\varepsilon, t)={\mbox{\boldmath$m$ }}^j\}},$$ = (3.11)

and let ${\mbox{\boldmath$y$ }}^{\varepsilon}(t)=(y^{\varepsilon}_1(t),y^{\varepsilon}_2(t))$ be the corresponding trajectory defined as $$\begin{eqnarray*}\left\{\begin{array}{ll}&y_1^{\varepsilon}(t)=x_1+\int_0^t(......)=x_2+\int_0^t(w^{\varepsilon}_2(s)-z)ds.\end{array}\right.\end{eqnarray*}$$ Note that $E\vert{\mbox{\boldmath$y$ }}^{\varepsilon}(t)-\tilde{\mbox{\boldmath$x$ }}(t)\vert^2\leqC(1+t^2)\varepsilon$. However, ${\mbox{\boldmath$y$ }}^{\varepsilon}(t)$ may not be in S for some $t\geq 0$. To obtain an admissible control for ${\cal P}^{\varepsilon}$, we need to modify ${\mbox{\boldmath$w$ }}^{\varepsilon}(t)$ so that the state trajectory stays in S. This is done as follows. Let

$${\mbox{\boldmath$u$ }}^{\varepsilon}(t)=(u_1^{\varepsilon}(t),u_2......t)):={\mbox{\boldmath$w$ }}^{\varepsilon}(t)I_{\{y^{\varepsilon}_1(t)\geq0\}}.$$ (3.12)

Then, for the control ${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\in{\calA}^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ constructed (3.10)-(3.12) above, it is shown in  Sethi, Yan, Zhang, and Zhou (1993) that

$$\left\vert J^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmat......h$x$ }},{\mbox{\boldmath$m$ }})\right\vert=O(\varepsilon^{\frac{1}{2}-\delta}).$$ (3.13)

Moreover, the case of more than two machines is treated in Sethi, Zhang, and Zhou (1992a).

Next we consider a construction of asymptotically optimal feedback controls. The problem is addressed by Sethi, and Zhou (1996a), Sethi, and Zhou (1996b). They construct such controls for ${\cal P}^{\varepsilon}$ in (3.8) with

$$c({\mbox{\boldmath$u$ }})=0 \ \mbox{and} \ h({\mbox{\boldmath$x$ }})=c_1x_1+c_2^+x_2^++c_2^-x_2^-,$$ (3.14)

where c₁, c₁⁺ and c₁^- are given nonnegative cost coefficients and$x_2^+=\max\{x_2,0\}$ and $x_2^-=-\min\{x_2,0\}$. In order to illustrate their results, we choose a simple situation in which each of the two machines has a capacity m when up and 0 when down, and has a breakdown rate $\lambda>0$ and the repair rate $\mu>0$. Furthermore, we shall assume that the average capacity$\bar m=\frac{m\mu}{\lambda+\mu}$ of each machine is strictly larger than the demand z. It is easy to see that the optimal control of the corresponding limiting (deterministic) problem ${\cal P}^0$ is:

$${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }})=\left\{\begin{arr......box{if} \ \ x_1=0,x_2<0,\\(z,z)&\mbox{if} \ \x_1=0,x_2=0.\end{array}\right.$$ (3.15)

From this, Sethi, and Zhou (1996a), Sethi, and Zhou (1996b) construct the following asymptotically optimal feedback control:

$${\mbox{\boldmath$u$ }}^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbo......,\\(k_1,\min\{k_1,k_2\}),&x_1=0,x_2<\theta_2(\varepsilon),\end{array}\right.$$ (3.16)

where $(\theta_1(\varepsilon),\theta_2(\varepsilon))\rightarrow(0,0)$ as $\varepsilon\rightarrow0$; see Figure 3.1.

Note that the optimal control (3.15) of ${\cal P}^0$ uses the obvious bang-bang and singular controls to go to (0,0) and then stay there. In the same spirit, the control in (3.16) uses bang-bang and singular controls to approach$(\theta_1(\varepsilon),\theta_2(\varepsilon))$. For a detailed heuristic explanation of asymptotic optimality, see Samaratunga, Sethi, and Zhou (1997); for a rigorous proof, see Sethi, and Zhou (1996a), Sethi, and Zhou (1996b).

Remark 3.6   The policy in Figure 3.1 cannot be termed a threshold-type policy, since there is no maximum tendency to go to $x_1 = \theta_1 (\varepsilon),$ when the inventory level x₁ (t) is below $\theta_1 (\varepsilon)$ and $x_2 (t) >\theta_2 (\varepsilon).$ In fact, Sethi, and Zhou (1996a), Sethi, and Zhou (1996b) show that a threshold-type policy, known also as a Kanban policy (see also Section 7), is not even asymptotically optimal when c₁ > c₂⁺. Also, it is known that the optimal feedback policy for two-machine flowshops involve switching manifolds that are much more complicated than the manifolds $x_1 = \theta_1$ and $x_2 =\theta_2$ required to specify a threshold-type policy. This implies that in the discounted flowshop problems, one cannot find an optimal feedback policy within the class of threshold-type policies. While $\theta_1$ and $\theta_2$ could still be called hedging points, there is no notion of optimal hedging points insofar as they are used to specify a feedback policy. See Samaratunga, Sethi, and Zhou (1997) for a further discussion on this point.

Remark 3.7   Fong and Zhou (1997) study the hierarchical production policies in stochastic two-machine flowshop with finite buffers. Using a constraint domain approximation approach developed by Fong and Zhou (1996), they construct controls for the original problem from an optimal control of the limiting problem in a way similar to (3.15)-(3.16). Finally, they show that the constructed controls are asymptotically optimal. When $c({\mbox{\boldmath$u$ }})\neq 0$ in the two-machine case, and in one general N-machine flowshop case, the problem of how to construct near-optimal feedback controls remain open.