4.3 Optimal control of dynamic jobshops

We consider the dynamic jobshop given by (2.13)-(2.15) in Section 3.3, but the Markov process modeling the machine capacities is denoted by${\mbox{\boldmath$m$ }}(t)$ without parameter $\varepsilon$. Correspondingly, the concept of the admissible control is modified as follows.

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

(i)

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

(ii)

${\mbox{\boldmath$u$ }}(t) \in U({\mbox{\boldmath$m$ }}(t))$;

(iii)

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

$$\left\{\begin{array}{ll}&\dot x_j(t)=\sum_{\ell=0}^{j-1}u_{\ell......_j(t)=\sum_{\ell=0}^mu_{\ell j}(t)-z_j, \ m+1\leq j \leqN_b\end{array}\right.$$ (4.24)

with the initial condition ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}.$

Let ${\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ denote the set of all admissible controls with initial conditions ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$, and${\mbox{\boldmath$m$ }}(t)={\mbox{\boldmath$m$ }}$. Here our problem is to find an admissible control${\mbox{\boldmath$u$ }}(\cdot)$ that minimizes the long-run average cost function

$$J({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }},{\mbox{\bol......({ \mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$u$ }}(t))dt,$$ (4.25)

where $G(\cdot,\cdot)$ defines the cost of surplus and production and ${\mbox{\boldmath$m$ }}$ is the initial value of${\mbox{\boldmath$m$ }}(t)$.

We impose the following assumptions on the process${\mbox{\boldmath$m$ }}(t)=(m_{1}(t),\cdots ,m_{N}(t))$ and the cost function $h(\cdot ,\cdot)$ throughout this section.

Assumption 4.5   Let ${\cal M}=\{{\mbox{\boldmath$m$ }}^{1},\cdots ,{ \mbox{\boldmath$m$ }}^{p}\}$ for some integer$p\geq1$, where ${\mbox{\boldmath$m$ }} ^{j}=(m_{1}^{j},\cdots,m_{N}^{j})$. The machine capacity process ${\mbox{\boldmath$m$ }}(t)\in {\cal M}$ is a finite state Markov chain with the following infinitesimal generator Q:

$$Qf({\mbox{\boldmath$m$ }})=\sum_{{\footnotesize\mbox{\boldm......({\mbox{\boldmath$m$ }}^{\prime })-f({\mbox{\boldmath$m$ }})]$$

for some $q_{\mbox{{\footnotesize\boldmath$m$ }}^{\prime }\mbox{{\footnotesize\boldmath$m$ }}}\geq 0$ and any function $f(\cdot)$ on${\cal M}$. Moreover, the Markov process is strongly irreducible and has the stationary distribution $p_{\mbox{{\footnotesize\boldmath$m$ }}^{j}}$,$j=1,\cdots,p$.

Assumption 4.6   Let $p_{n}=\sum_{j=1}^{p}m_{n}^{j}p_{\mbox{{\footnotesize\boldmath$m$ }}^{j}}$ and$n(i,j)=\mbox{arg}\{(i,j)\in K_n\}$ for $(i,j)\in \Pi$. Here p_n represents the average capacity of the machine n, and n(i,j) is the number of machine placed on the arc (i,j). Assume that there exist $\{p_{ij}>0: (i,j)\in K_n\}(n=1,...,N)$ such that

$$\sum_{(i,j)\in K_n}p_{ij}\leq 1,$$ (4.26)

$$\sum_{\ell=0}^m p_{\ell i}p_{n(\ell,i)}>d_i, \ i=m+1,...,N_b,$$ (4.27)

and

$$\sum_{\ell=0}^{i-1}p_{\ell i}p_{n(\ell,i)}>\sum_{\ell=i+1}^{N_b}p_{i \ell}p_{n(i,\ell)}, \ i=1,...,m.$$ (4.28)

Assumption 4.7$G(\cdot,\cdot)$ is a non-negative, 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$ }} ^{\prime }\in{\cal S}$ and ${\mbox{\boldmath$u$ }},{\mbox{\boldmath$u$ }}^{\prime }\in U({\mbox{\boldmath$m$ }}^{j}),j=1,\cdots ,p$, there exist constants C and $\kappa_{43}\geq 1$ such that $$\vert G({\mbox{\boldmath$x$ }},{\mbox{\boldmath$u$ }})-G......mbox{\boldmath$u$ }}-{ \mbox{\boldmath$u$ }}^{\prime }\vert).$$ Let $\lambda ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ denote the minimal expected cost, i.e.,

$$\lambda ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\in......({ \mbox{\boldmath$x$ }}^{0},{\mbox{\boldmath$m$ }}^{0}).$$ (4.29)

In order to get the Hamilton-Jacobi-Bellman equation for our problem, similar to Section 4.2, we introduce some notation. Let ${\cal G}$ denote the family of real-valued functions $f(\cdot,\cdot)$ defined on ${\cal 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 $\hat 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{\cal S}$ $$\vert f({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})-f({\......\mbox{\boldmath$x$ }}-{\mbox{\boldmath$x$ }}^{\prime }\vert.$$

Write (4.24) in the vector form

$$\dot {\mbox{\boldmath$x$ }}(t)=D{\mbox{\boldmath$u$ }}(t), \ {\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$$

with ${\mbox{\boldmath$u$ }}(t)=({\mbox{\boldmath$u$ }}_1(t),...,{\mbox{\boldmath$u$ }}_m(t),{\mbox{\boldmath$u$ }}_{m+1}(t))$. Consider now the following equation:

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

where $\lambda$ is a constant, $f(\cdot ,\cdot )\in {\cal G}$. We have the following verification theorem due to Presman, Sethi, and Zhang (1999b).

Theorem 4.11   Assume (i) $(\lambda ,f(\cdot ,\cdot ))$with $f(\cdot ,\cdot )\in$${\cal G}$satisfies (4.30); (ii) there exists$\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.31)

and the equation$\dot{\mbox{\boldmath$x$ }}(t)=D\mbox{\boldmath$u$ }^{\ast }(\mbox{\boldmath$x$ }(t),\mbox{\boldmath$m$ }(t))$, 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.32)

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.33)

Next we try to construct a pair of $(\lambda, W(\cdot,\cdot))$ which satisfies (4.30). To get this pair, we use the vanishing discount approach. Consider a 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 )).$$

Theorem 4.12   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 {\cal 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}$.

Theorem 4.13 (i)   In our problem, $\lambda ({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ does not depend on $( \mbox{\boldmath$x$ },\mbox{\boldmath$m$ })$, and (ii) the pair$(\lambda, W(\cdot,\cdot))$defined in Theorem4.12 is a solution to (4.19).

Remark 4.8   Assumption 4.6 is not needed in the discounted case. It is clear that this condition is necessary for the finiteness of the long-run average cost in the case when $h(\cdot ,\cdot)$ tends to $+\infty$ as $x_{N}\rightarrow-\infty$. Theorem 4.13 states in particular that this condition is also sufficient.The proof of Theorems 4.12 and 4.13 is based on the following lemma obtained in Presman, Sethi, and Zhang (1999b).

Lemma 4.3   For any $(\mbox{\boldmath$x$ }^{0},\mbox{\boldmath$m$ }^{0})\in {\cal S}\times {\cal M}$ and$(\mbox{\boldmath$y$ },\mbox{\boldmath$m$ }^{\prime })\in {\calS}\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 \bar C_{1}(r)\left( 1+\sum_{k=1}^{N}\vert x_{k}^{0}-y_{k}\vert^{r}\right),$$ (4.34)

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})$.