3.3 Hierarchical controls for jobshops

 Sethi, and Zhou (1994) consider hierarchical production planning in a general manufacturing system given in Section 2.3. For the jobshop $(\Delta,\Pi,{\cal K})$, let$u_{ij}^{\varepsilon}(t)$ be the control at time t associated with arc (i,j), $(i,j)\in \Pi$. Suppose we are given a stochastic process${\mbox{\boldmath$m$ }}(\varepsilon, t)=(m_1(\varepsilon, t),...,m_{N}(\varepsilon,t))$ on the standard probability space $(\Omega, {\cal F}, P)$ with$m_n(\varepsilon, t)$ representing the capacity of the nth machine at time t, n=1,...,N, where $\varepsilon$ is a small parameter to be precisely specified later. The controls$u_{ij}^{\varepsilon}(t)$ with $(i,j)\in K_n$, n=1,...,N,$t\geq 0$, should satisfy the following constraints:

$$0 \leq \sum_{(i,j)\in K_n}u^{\varepsilon} _{ij}(t) \leqm_n(\varepsilon, t) \ \mbox{for all} \ t\geq 0, \ n=1,...,N,$$ (3.17)

where we have assumed that the required machine capacity p_ij (for unit production rate of type j from part type i) equals 1, for convenience in exposition. The analysis in this paper can be readily extended to the case when the required machine capacity for the unit production rate of part j from part i is any given positive constant.

We denote the surplus at time t in buffer i by$x_i^{\varepsilon}(t)$,$i \in \Delta\setminus \{0,N_{b}+1\}$. Note that if $x_i^{\varepsilon}(t)>0$, i=1,...,N_b, we have an inventory in buffer i, and if $x_i^{\varepsilon}(t)<0$, i=m+1,...,N_b, we have a shortage of finished product i. The dynamics of the system are therefore

$$\left\{\begin{array}{lll}&\dot x_i^{\varepsilon}(t)= \left(\sum......{\elli}^{\varepsilon}(t)-z_i\right),\ m+1 \leq i \leq N_b,\end{array}\right.$$ (3.18)

with${\mbox{\boldmath$x$ }}^{\varepsilon}(0):=(x_1^{\varepsilon}(0),...,x_{N_b}^{\varepsilon}(0))=(x_1,...,x_{N_b})={\mbox{\boldmath$x$ }}$.
Let $${\mbox{\boldmath$u$ }}_{\ell}^{\varepsilon}(t)=(u^{\varepsi......1}(t),...,u^{\varepsilon}_{\ell, N_b}(t))', \ \ell=0,...,m,$$

and

$${\mbox{\boldmath$u$ }}_{m+1}^{\varepsilon}(t)=(z_{m+1},...,z_{N_b})'.$$

Similar to Section 2.3, we write the relation (3.18) in the following vector form:

$$\dot{{\mbox{\boldmath$x$ }}}^{\varepsilon}(t)=(\dot{x}^{\varepsil.........,\dot{x}_{N_b}^{\varepsilon}(t))'=D{\mbox{\boldmath$u$ }}^{\varepsilon}(t).$$ (3.19)

Definition 3.3   We say that a control${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)\in {\cal U}$ is admissible with respect to the initial state vector ${\mbox{\boldmath$x$ }}=(x_{1},\cdots ,x_{N_b})\in S$ and ${\mbox{\boldmath$m$ }}\in {\cal M}$, if

(i)

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

(ii)

${\mbox{\boldmath$u$ }}^{\varepsilon}(t) \inU({\mbox{\boldmath$m$ }}(\varepsilon,t))$ for all $t\geq 0$;

(iii)

the corresponding state process ${\mbox{\boldmath$x$ }}^{\varepsilon}(t)= (x_{1}^{\varepsilon}(t),\cdots,x_{N_b}^{\varepsilon}(t))\in {\cal S}$ for all $t\geq 0$.

Remark 3.8   The condition (iii) is equivalent to${\mbox{\boldmath$u$ }}^{\varepsilon}(t) \in U({\mbox{\boldmath$x$ }} ^{\varepsilon}(t), {\mbox{\boldmath$m$ }}^{\varepsilon}(t))$,$t\geq 0$.Let ${\cal A}^{\varepsilon} ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ denote the set of all admissible control with respect to ${\mbox{\boldmath$x$ }}\in {\cal S}$ and the machine capacity vector ${\mbox{\boldmath$m$ }}$. The problem is to find an admissible control${\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot )$ that minimize the cost function

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

where $h(\cdot)$ defines the cost of inventory/shortage,$c(\cdot)$ is the production cost, ${\mbox{\boldmath$x$ }}$ is the initial state, and ${\mbox{\boldmath$m$ }}$ is the initial value of ${\mbox{\boldmath$m$ }}(\varepsilon, t)$.

The value function is then defined as

$$v^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}) =\......ath$x$ }},{\mbox{\boldmath$m$ }},{\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)).$$ (3.21)

We impose the following assumptions on the random capacity process${\mbox{\boldmath$m$ }}(\varepsilon, t)=(m_1(\varepsilon, t),...,m_{N}(\varepsilon,t))$ and the cost functions $h(\cdot)$ and$c(\cdot)$ throughout this section.

Assumption 3.4   Let ${\cal M}=\{{\mbox{\boldmath$m$ }}^1,...,{\mbox{\boldmath$m$ }}^p\}$ for some given integer$p\geq1$, where ${\mbox{\boldmath$m$ }}^j=(m_1^j,...,m^j_{N})$, with m^j_k, k=1,...,N denoting the capacity of the kth machine, j=1,...,p. The capacity process ${\mbox{\boldmath$m$ }}^{\varepsilon}(t)\in{\cal M}$ is a finite state Markov chain with the infinitesimal generator $Q=Q^{(1)}+\varepsilon^{-1}Q^{(2)}$, whereQ⁽¹⁾=(q_ij⁽¹⁾) and Q⁽²⁾=(q_ij⁽²⁾) are matrices such that $q_{ij}^{(r)}\geq 0$ if $j \neq i$, and$q_{ii}^{(r)}=-\sum_{j \neq i}q_{ij}^{(r)}$ for r=1,2. Moreover, Q⁽²⁾ is irreducible and, without any loss of generality, it is taken to be the one that satisfies

$$\min_{ij}\{\vert q^{(2)}_{ij}\vert: q_{ij}^{(2)}\neq 0\}=1.$$ Assumption 3.5   Assume that Q⁽²⁾ is weakly irreducible. Let $\nu=(\nu_1,..., \nu_p)$ denote the equilibrium distribution of Q⁽²⁾, that is,$\nu$ is the only nonnegative solution to the equations

$$\nu Q^{(2)}=0 \ \mbox{and} \ \sum_{i=1} ^p \nu_i =1.$$ (3.22)

Assumption 3.6$h(\cdot)$ and $c(\cdot)$ are convex functions. For all ${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}'\in {\cal S}$ and ${\mbox{\boldmath$u$ }},{\mbox{\boldmath$u$ }}'$, there exist constants C₃₄ and$\kappa_{32}\geq 0$ such that $$\begin{eqnarray*}&&0 \leq h({\mbox{\boldmath$x$ }})\leq C_{34}(1+\vert{\mbox{\......C_{34}\vert{\mbox{\boldmath$u$ }}-{\mbox{\boldmath$u$ }}'\vert.\end{eqnarray*}$$

We use ${\cal P}^{\varepsilon}$ to denote our control problem

$${\cal P}^{\varepsilon}:\left\{\begin{array}{lll}\mbox{min}&J^{\......boldmath$m$ }},{\mbox{\boldmath$u$ }}^{\varepsilon}(\cdot)).\end{array}\right.$$ (3.23)

In order to obtain the limiting problem, we consider the class of deterministic controls defined below.

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

$$\begin{eqnarray*}U(\cdot)&=&({\mbox{\boldmath$u$ }}^{1,0}(\cdot),...,{\mbox{\b......^{p,0}_0(\cdot),...,{\mbox{\boldmath$u$ }}^{p,0}_{m+1}(\cdot)))\end{eqnarray*}$$ with $\sum_{(i,j)\in K_n}u^{\ell,0}_{ij}(t)\leq m_n^{\ell}$,$\ell=1,...,p$, n=1,...,N, and the corresponding solution${\mbox{\boldmath$x$ }}(\cdot)$ of the system

$$\left\{\begin{array}{ll}&\dot x_{j}(t)=\sum_{\ell=0}^{j-1}\sum_......u^{i,0}_{\ellj}(t)-z_j, \ x_j(0)=x_j, \ m+1\leq j \leq N_b,\end{array}\right.$$ (3.24)

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

The object of the limiting problem is to choose a control$U(\cdot)\in {\cal A}^0$ that minimizes

$$\begin{eqnarray*}J^0({\mbox{\boldmath$x$ }},U(\cdot))=\int^{\infty}_0 e^{- \rh......1}^p\nu_{\ell}c({\mbox{\boldmath$u$ }}^{\ell,0}(t))\right]dt.\end{eqnarray*}$$ We write (3.24) in the vector form $$\dot {\mbox{\boldmath$x$ }}(t)=D\sum_{\ell=1}^p\nu_{\ell}{\......l,0}(t), \{\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}.$$

We use ${\cal P}^0$ to denote the limiting problem and derive it as follows:

$$\begin{eqnarray*}{\cal P}^0:\left\{\begin{array}{lll}\mbox{min}&J^0({\mbox......})} J^0({\mbox{\boldmath$x$ }},U(\cdot)).\end{array}\right.\end{eqnarray*}$$

Based on the Lipschitz continuity of the value function given in Section 2.3, Sethi, and Zhou (1994) prove the following theorem, which says that the problem ${\cal P}^0$ is indeed a limiting problem in the sense that the value function$v^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ of ${\cal P}^{\varepsilon}$ converges to the value function $v({\mbox{\boldmath$x$ }})$ of ${\cal P}^0$. Furthermore, the theorem also gives the corresponding convergence rate.

Theorem 3.2   For each $\delta \in (0,\frac{1}{2})$, there exists a positive constant C₃₅ such that for all ${\mbox{\boldmath$x$ }}\in {\cal S}$ and sufficiently small $\varepsilon$, we have

$$\vert v^{\varepsilon}({\mbox{\boldmath$x$ }},{\mbox{\boldma......th$x$ }}\vert^{\kappa_{32}})\varepsilon^{\frac{1}{2}-\delta}.$$

Based on Presman, Sethi, and Suo (1997a), which is related to the Lipschitz continuity of the value function for the general jobshop subject to lower and upper bound constraints on work-in-process, Sethi, Zhang and Zhang (1999d) also show that Theorem 3.2 is true for a general jobshop system with limited buffers.