2.3 Optimal control of dynamic jobshops

We consider a manufacturing system producing a variety of products in demand using machines in a general network configuration, which generalizes both the parallel and the tandem machine models. Each product follows a process plan--possibly from a number of alternative process plans--that specifies the sequence of machines it must visit and the operations performed by them. A process plan may call for multiple visits to a given machine, as is the case in semiconductor manufacturing. See Lou and Kager (1989) , Srivatsan, Bai, and Gershwin (1994),  Uzsoy, Lee, and Martin-Vega (1996), and Yan, Lou, Sethi, Gardel, and Deosthali (1996). Often the machines are unreliable. Over time they break down and must be repaired. A manufacturing system so described will be termed a dynamic jobshop.

Now we give the mathematically precise description of a jobshop suggested by Presman, Sethi, and Suo (1997a) as a revision of the description by Sethi and Zhang (1994a). First we give some definitions.

Definition 2.9   A manufacturing diagraph is a graph$(\Delta,\Pi)$, where $\Delta$ is a set of $N_b+2\geq 3$, vertices, and $\Pi$ is a set of ordered pairs called arcs, satisfying the following properties:

(i)

There is only one source, labeled 0, and only one sink, labeled N_b+1, in the digraph.

(ii)

No vertex in the graph is isolated.

(iii)

The digraph does not contain any cycle.

Remark 2.4   Condition (ii) is not an essential restriction. Inclusion of isolated vertices is merely a nuisance. This is because an isolated vertex is like a warehouse that can only ship out parts of a particular type to meet their demand. Since no machine (or production) is involved, its inclusion or exclusion does not affect the optimization problem under consideration. Condition (iii) is imposed to rule out the following two trivial situations: (a) a part of type i in buffer i gets processed on a machine without any transformation and returns to buffer i, and (b) a part of type i is processed and converted back into a part of type j, $j \neq i$, and is then processed further on a number of machines to
be converted back into a part of type i. Moreover, if we had included any cycle in our manufacturing system, the flow of parts that leave buffer i only to return to buffer i would be zero in any optimal solution. It is unnecessary, therefore, to complicate the problem by including cycles.

Definition 2.10   In a manufacturing digraph, the source is called the supply node and the sink represents the customers. Vertices immediately preceding the sink are called external buffers, and all others are called internal buffers.

In order to obtain the system dynamics from a given manufacturing digraph, a systematic procedure is required to label the state and control variables. For this purpose, note that our manufacturing digraph $(\Delta,\Pi)$ contains a total of N_b+2 vertices including the source, the sink, m internal buffers, and N_b-m external buffers for some integer m and N_b, $0 \leq m \leqN_b-1$,$N_b\geq 1$.

Theorem 2.8   We can label all the vertices from 0 to N_b+1 in a way so that the label numbers of the vertices along every path are in a strictly increasing order, the source is labeled 0, the sink is labeled N_b+1, and the external buffers are labeled m+1, m+2,...,N_b.

The proof is similar to Theorem 2.2 in Sethi, and Zhou (1994).

With the help of Theorem 2.8, one is able to formally write the dynamics and the state constraints associated with a given manufacturing digraph. To do this, we require the following definitions.

Definition 2.11   For each arc (i,j), $j \neq N_b+1$, in a manufacturing digraph, the rate at which parts in buffer i are converted to parts in buffer j is labeled as controlu_ij. Moreover, the control u_ij associated with the arc (i,j) is called an output of i and an input to j. In particular, outputs of the source are called primary controls of the digraph. For each arc (i, N_b+1), i=m+1,...,N_b, the demand for products in buffer i is denoted by z_i.

In what follows, we shall also set

$$\begin{eqnarray*}u_{i, N_b+1}&=&z_i, \ i=m+1,...,N_b,\\ u_{i,j}&=&0, \ \mbox{f......\in \Pi, \ 0 \leq i \leq N_b \ \mbox{and} \ 1\leq j \leq N_b+1,\end{eqnarray*}$$ for a unified notation suggested in Presman, Sethi, and Suo (1997a). While z_i and u_i,j for $(i,j)\not\in \Pi$ are not controls, we shall for convenience refer to u_i,j, $0 \leq i\leq N_b$,$0 \leq j \leq N_b+1$, as controls. In this way, we can consider the controls as an (N_b+1) x (N_b+1) matrix${\mbox{\boldmath$u$ }}=(u_{ij})$ of the following form. $$\begin{eqnarray*}\begin{array}{cccccccccccc}u_{0,1}&u_{0,2}&...&u_{0,i}&u_{0......&...\\0&0&...&0&0&...&0&0&...&0&0&u_{N_b,N_b+1}\end{array}\end{eqnarray*}$$ The set of all such controls is written as ${\cal U}$, i.e., $${\cal U}= \{ {\mbox{\boldmath$u$ }}=(u_{ij}): 0 \leq i \leq......eq j \leqN_b+1, u_{ij}=0 \ \mbox{for} \ (i,j)\not\in \Pi\}.$$ Before writing the dynamics and the state constraints corresponding to the manufacturing digraph $(\Delta,\Pi)$ containing N_b+2 vertices consisting of a source, a sink, m internal buffers, and N_b-m external buffers associated with the N_b-m distinct final products to be manufactured (or characterizing a jobshop), we give the description of the control constraints. We label all the vertices according to Theorem 2.8. For simplicity in the sequel, we shall call the buffer whose label is i as buffer i, i=1,2,...,N_b. The control constraints depend on the placement of the machines, and the different placements on the same digraph will give rise to different jobshops. In other words, a jobshop corresponds to a unique digraph, whereas a digraph may correspond to many different jobshops. Therefore, to uniquely characterize a jobshop using graph theory, we need to introduce the concept of a placement of machines, or simply a placement. Let$N_b \leq \pi-N_b+m$, where $\pi$ denotes the total number of arcs in $\Pi$.

Definition 2.12   In a manufacturing digraph $(\Delta,\Pi)$, a set${\cal K}=\{K_1,K_2,...,K_{N}\}$ is called a placement of machines 1,2,...,N, if ${\cal K}$ is a partition of $\hat\Pi=\{(i,j)\in \Pi: j \neq N_b+1\}$, namely, $\emptyset \neq K_n\subset\hat \Pi$,$K_n \cap K_{\ell}=\emptyset$ for $n \neq \ell$, and $\cup_{k=1}^{N}K_k=\hat \Pi$.
A dynamic jobshop can be uniquely specified by a triple$(\Delta,\Pi,{\cal K})$, which denotes a manufacturing system that corresponds to a manufacturing digraph $(\Delta,\Pi)$ along with a placement of machines ${\cal K}=(K_1,K_2,...,K_{N})$.

Consider a jobshop $(\Delta,\Pi,{\cal K})$, let u_ij(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$ }}(t)=(m_1(t),...,m_N(t))$ on the standard probability space $(\Omega, {\cal F}, P)$ with m_n( t) representing the capacity of the nth machine at time t, n=1,...,N. The controls u_ij(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_{ij}(t) \leqm_n(t) \ \mbox{for all} \ t\geq 0, \ n=1,...,N,$$ (2.12)

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(t), $i \in \Delta\setminus \{0,N_{b}+1\}$. Note that if x_i(t)>0, i=1,...,N_b, we have an inventory in buffer i, and if x_i(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}{{ll}}&\dot x_i(t)= \left(\sum_{\ell=0}^{i-......_{\ell=0}^m u_{\elli}(t)-z_i\right),\ m+1 \leq i \leq N_b,\end{array}\right.$$ (2.13)

with${\mbox{\boldmath$x$ }}(0):=(x_1(0),...,x_{N_b}(0))=(x_1,...,x_{N_b})={\mbox{\boldmath$x$ }}$. Since internal buffers provide inputs to machines, a fundamental physical fact about them is that they must not have shortages. In other words, we must have

$$\left\{\begin{array}{{ll}}& x_i(t) \geq 0, \ t\geq 0, \ i=1,...,m, \\& -\infty <x_i <+\infty, \ t\geq 0, \i=m+1,...,N_b.\end{array}\right.$$ (2.14)

Let $${\mbox{\boldmath$u$ }}_{\ell}(t)=(u_{\ell,\ell+1}(t),...,u_{\ell, N_b}(t))', \ \ell=0,...,m,$$ and $${\mbox{\boldmath$u$ }}_{m+1}(t)=(z_{m+1},...,z_{N_b})'.$$ The relation (2.13) can be written in the following vector form:

$$\dot{{\mbox{\boldmath$x$ }}}(t)=(\dot{x}_1(t),...,\dot{x}_{N_b}(t))'=D{\mbox{\boldmath$u$ }}(t),$$ (2.15)

where $D: R^J \rightarrow R^{N_b}$ is the corresponding linear operator with $J=(N_b-m)+\sum_{\ell=0}^m(N_b-\ell)$, and${\mbox{\boldmath$u$ }}(t)=({\mbox{\boldmath$u$ }}_0(t),...,{\mbox{\boldmath$u$ }}_{m+1}(t))'$. Let ${\cal S}=R^m_+\times R^{N_b-m}$. Furthermore, let ${\cal S}^b$ be the boundary of ${\cal S}$, and the interior${\cal S}^o={\cal S}\setminus{\cal S}^b$.

Let us illustrate a jobshop by the following simple example.

Example 2.1. In Figure 2.1, we have four machines $M_1,\cdots,M_4$, two distinct products, and five buffers. Each machine $M_i,\; i=1,2,3,4,$ has capacity m_i(t) at time t, and each product j=1,2 has demand z_j. As indicated in the figure, $x_i,\; i=1,2,\cdots,5,$ known as the state variables are associated with the buffers. More specifically, x_i denotes the inventory/backlog of part type$i,\; i=1,2,\cdots,5$. Control variables $u_i,\; i=1,2\cdots,6,$ represent production rates. More specifically, u ₁ and u₂ are the rates at which raw parts coming from outside are converted to part types 1 and 5, respectively, and u₃, u₄, u₅ and u₆ are the rates of conversion from part types 3,1,1, and 2 to part types 4, 2, 4 and 3, respectively. Thus,

$$\begin{eqnarray*}&&\Delta=\{0,1,2,3,4,5,6\},\\&&\Pi=\{(0,1),(0,5),(1,2),(1,4),(2,3),(3,4)\},\\&&m=3, \ N=4, \ N_b=5.\end{eqnarray*}$$ Therefore, the system dynamics associated with Figure 2.1 is

$$\begin{array}{lll}\dotx_1(t)=u_{01}(t)-u_{12}(t)-u_{14}(t),&\d......\dotx_4(t)=u_{14}(t)+u_{34}(t)-z_4,\\\dotx_5(t)=u_{05}(t)-z_5,&\end{array}$$ (2.16)

and the process$U(t)=(u_{01}(t),\cdots,u_{34}(t))$ must satisfy the capacity constraints

$$u_{01}(t)\leqm_1(t),u_{05}(t)+u_{14}(t)\leqm_4(t),$$

$$u_{12}(t)+u_{34}(t)\leqm_3(t),u_{23}(t)\leq m_2(t).$$ (2.17)

For i=1,2,3, buffer i is between two machines and is known as an internal buffer, the state constraints are

$$x_i(t)\geq 0,\; i=1,2,3,$$ (2.18)

for our example. The remaining buffers 4 and 5 are external buffers. x₄(t) and x₅ (t) are called surpluses with positive values meaning inventories and negative values meaning backlogs.

We are now in the position to formulate our stochastic optimal control problem for the jobshop defined by (2.13)-(2.15). For ${\mbox{\boldmath$m$ }}=(m_1,...,m_{N})$, let

$$\begin{eqnarray*}U({\mbox{\boldmath$m$ }})&=&\big\{{\mbox{\boldmath$u$ }}=(u_{......\ \ \ \ \ \ \ \ \ \u_{i,N_b+1}=z_i, m+1\leq i \leq N_b\big\},\end{eqnarray*}$$ and for ${\mbox{\boldmath$x$ }}\in {\cal S}$ and ${\mbox{\boldmath$m$ }}$, $$\begin{eqnarray*}U({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})=\Big\{{\mbox......0}^{n-1}u_{in}-\sum_{i=n+1}^{N_b}u_{ni}\geq0,n=1,...,m\Big\}.\end{eqnarray*}$$ Definition 2.13   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},\cdots ,x_{N_b})\in S$ and ${\mbox{\boldmath$m$ }}\in {\cal M}$, if

(i)

${\mbox{\boldmath$u$ }}(\cdot)$ is an${\cal F}_t$-adapted measurable 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))$ for all $t\geq 0$;

(iii)

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

Remark 2.5   The condition (iii) is equivalent to${\mbox{\boldmath$u$ }}(t) \in U({\mbox{\boldmath$x$ }}(t), {\mbox{\boldmath$m$ }}(t))$,$t\geq 0$.

Let ${\cal A}({\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$ }}(\cdot)$ that minimizes the cost function

$$J({\mbox{\boldmath$x$ }}, {\mbox{\boldmath$m$ }},{\mbox{\boldmath......\infty}_0 e^{-\rho t}H({\mbox{\boldmath$x$ }}(t),{\mbox{\boldmath$u$ }}(t))dt,$$ (2.19)

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

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

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

Assumption 2.6$H(\cdot,\cdot)$ is a nonnegative and convex function. Further, for all ${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}'\in {\cal S}$ and ${\mbox{\boldmath$u$ }},{\mbox{\boldmath$u$ }}'$, there exist constants $\hat C_{20}$ and $\kappa_{25}\geq 0$ such that

$$\vert H({\mbox{\boldmath$x$ }}, {\mbox{\boldmath$u$ }})-H({......rt+\vert{\mbox{\boldmath$u$ }}-{\mbox{\boldmath$u$ }}'\vert).$$

Assumption 2.7   Let ${\cal M}=\{{\mbox{\boldmath$m$ }}^1,\ldots,{\mbox{\boldmath$m$ }}^p\}$ for some given integer $p\geq1$. The capacity process${\mbox{\boldmath$m$ }}(t)\in {\cal M}$,$t\geq 0$, is a finite state Markov chain with generator Q=(q_kk') such that $q_{kk'}\geq0$ if $k\neq k'$ and$q_{kk}=-\sum_{k'\neq k}q_{kk'}$. Moreover, Q is irreducible.

We use ${\cal P}$ to denote our control problem. Presman, Sethi, and Suo (1997a) prove the following theorem.

Theorem 2.9   The optimal control ${\mbox{\boldmath$u$ }}^*(\cdot)\in {\cal A}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ exists, 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)), \quad t\geq 0,$$ where ${\mbox{\boldmath$x$ }}^*(\cdot)$ is the optimal state process--the solution for (2.15) for ${\mbox{\boldmath$u$ }}(t)={\mbox{\boldmath$u$ }}^*({\mbox{\boldmath$x$ }}(t), {\mbox{\boldmath$m$ }}(t))$ with ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}$. However, if $H({\mbox{\boldmath$x$ }}, {\mbox{\boldmath$u$ }})$ is strictly convex in ${\mbox{\boldmath$u$ }}$, then the optimal feedback control ${\mbox{\boldmath$u$ }}^*(\cdot,\cdot)$ is unique.

Now we consider the Lipschitz property of the value function. It should be noted that unlike in the case without state constraints, the Lipschitz property in our case does not follow directly. The reason for this is that in the presence of state constraints, a control which is admissible with respect to ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}\in {\cal S}$ is not necessarily admissible for ${\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}'$ when${\mbox{\boldmath$x$ }}'\neq {\mbox{\boldmath$x$ }}$.

Theorem 2.10   The value function is convex and continuous, and satisfies the condition

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

for some positive constant $\hat C_{21}$ and all ${\mbox{\boldmath$x$ }},{\mbox{\boldmath$x$ }}'\in {\cal S}$.

Because the problem of the jobshop involves state constraints, we can write the HJBDD for the problem as in Section 2.2:

$$\rho v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}) = \inf_{{\m......\mbox{\boldmath$u$ }}) \} + Q v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }}).$$ (2.22)

Theorem 2.11 (Verification Theorem)   (i) The value function$v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ satisfies equation (2.22) for all${\mbox{\boldmath$x$ }}\in {\cal S}$. (ii) If some continuous convex function $\tildev({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ satisfies (2.22) and the growth condition (2.21) with ${\mbox{\boldmath$x$ }}'=0$, then $\tildev({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})\leq v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$. Moreover, if there exists a feedback control ${\mbox{\boldmath$u$ }}({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ providing the infimum in (2.22) 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 $H({\mbox{\boldmath$x$ }}, {\mbox{\boldmath$u$ }})$ 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.22). Then,

$$\begin{eqnarray*}\dot {\mbox{\boldmath$x$ }}(t)=D{\mbox{\boldmath$u$ }}^*({\mb......th$m$ }}(t)),\;{\mbox{\boldmath$x$ }}(0)={\mbox{\boldmath$x$ }}\end{eqnarray*}$$ 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.6   The HJBDD (2.22) coincides at inner points of ${\cal S}$ with the usual dynamic programming equation for convex PDP problems. Here PDP is the abbreviation of piecewise deterministic processes introduced by Vermes (1985) and Davis (1993). The HJBDD gives at boundary points of ${\cal S}$, a boundary condition in the following sense. Let the restriction of $v({\mbox{\boldmath$x$ }},{\mbox{\boldmath$m$ }})$ on some l-dimensional face, 0<l<N, of the boundary of S be differentiable at an inner point ${\mbox{\boldmath$x$ }}$ of this face. Note that this restriction is convex and is differentiable almost everywhere on this face. Then there is a vector $\tilde \nabla v ({\mbox{\boldmath$x$ }}_0, {\mbox{\boldmath$m$ }})$ such that $v'_{\mbox{\boldmath$m$ }} ({\mbox{\boldmath$x$ }}_0,{\mbox{\boldmath$m$ }}) =...... ({\mbox{\boldmath$x$ }}_0, {\mbox{\boldmath$m$ }})\cdot {\mbox{\boldmath$p$ }}$ for any admissible direction at ${\mbox{\boldmath$x$ }}$. It follows from the continuity of the value function that

$$\min_{{\mbox{\boldmath$u$ }} \in U({\mbox{\boldmath$x$ }}_0,{\mbo......x{\boldmath$x$ }}_0,{\mbox{\boldmath$m$ }})\cdotD{\mbox{\boldmath$u$ }}\right. \left. H({\mbox{\boldmath$x$ }}_0,{\mbox{\boldmath$u$ }})\right\}$$ +

$$\min_{{\mbox{\boldmath$u$ }} \in U({\mbox{\boldmath$m$ }})}\left......x{\boldmath$u$ }}+ H({\mbox{\boldmath$x$ }}_0,{\mbox{\boldmath$u$ }})\right\}.$$ = (2.23)

The boundary condition on $v(\cdot,\cdot)$ given by (2.23) can now be interpreted as follows. First, the optimal control policy on the boundary has the same intuitive explanation as in the interior. The important difference is that we now have to worry about the feasibility of the policy. What the boundary condition accomplishes is to shape the value function on the boundary of ${\cal S}$ in such a way that the unconstrained optimal policy is also feasible.

According to (2.22), optimal feedback control policies are obtained in terms of the directional derivatives of the value function.

Note now that the uniqueness of the optimal control follows directly from the strict convexity of function $H(\cdot,\cdot)$in ${\mbox{\boldmath$u$ }}$ and the fact that any convex combination of admissible controls for any given ${\mbox{\boldmath$x$ }}$ is also admissible. For proving the remaining statements of Theorem 2.10 and Theorem 2.11, see Presman, Sethi, and Suo (1997a).

Remark 2.7   Presman, Sethi, and Suo (1997a) show that Theorem 2.9, Theorem 2.10, and Theorem 2.11 also hold when the systems are subject to lower and upper bound constraints on work-in-process.