Sage Journals: Discover world-class research

Abstract

Under the stochastic production environment of uncertain job arrival, processing times and product demands, the deadlock-free scheduling is studied for a kind of knowledgeable manufacturing cell with multiple machines and products. First, the expected cost objective function is established based on continuous Markov chain with a discount factor, and a stochastic dynamic programming model is obtained by the virtual self-transfer method. Then, the properties of optimal objective function are analyzed and proved, and a heuristics approximate dynamic programming algorithm is proposed, which can effectively overcome the curse of dimensionality problem in the process of solving the dynamic programming model. With the above settled as premises, the deadlock-free scheduling strategy for knowledgeable manufacturing cell is proposed to control the processing rate and avoid system deadlock simultaneously. Finally, a case study is conducted to demonstrate and validate the effectiveness of the deadlock-free scheduling approach.

Keywords

Deadlock-free scheduling dynamic programming Markov chain stochastic production environment

Introduction

With the rapid development of advanced management and information technologies, the manufacturing industry is booming, and various advanced manufacturing modes and new conceptions have sprung up.^1–4 Most of them, capable of meeting certain demands of the manufacturing system, still have limitations of their application scope due to the multiple demands of various enterprises. Therefore, knowledgeable manufacturing, a new manufacturing idea brought forward by Yan and Liu,⁵ is being given more and more attention. The technique takes an advanced manufacturing mode as advanced manufacturing knowledge, so that all kinds of complementary advanced manufacturing modes can be transformed into their corresponding advanced manufacturing knowledge in the advanced manufacturing system. On the basis of one-to-one isomorphic mapping between agent mesh and knowledgeable mesh (KM), the existing advanced manufacturing mode can be incorporated into the knowledgeable manufacturing system (KMS) to meet different demands from different enterprises.⁶ The KMS, a highly intelligent manufacturing system characterized by self-adaptation, self-learning, self-evolution, self-reconfiguration, self-training and self-maintenance, can constantly adapt to environmental changes by self-learning and self-evolution. Knowledgeable manufacturing cells (KMCs), which include processing agents, transport agents, decision-scheduling modules and testing devices such as radio frequency identification (RFID) devices and raster, constitute the KMS, capable of real-time monitoring, acquiring data, processing information and making decisions. In order to realize self-adaptation, self-learning, self-evolution, self-reconfiguration and so on, KMC includes more advanced hardware and software architecture compared to the general manufacturing systems. Throughout the production process, the real-time production state data can be tracked, acquired, transferred and processed in time and accurately, including the random disturbance, state of buffers, state of machines and current operation of jobs, and rapid responses to production states are also provided for scheduling decision-making by KMC. Therefore, it is not difficult to see that compared with the general manufacturing systems, KMC is easier to realize intelligent scheduling with fewer people or no people.

In recent years, most approaches to scheduling and sequencing of jobs focus on deterministic production parameters.^7–12 However, the incidents in manufacturing cells, such as the arrival rate of jobs, product demands, machine failure and repair, which usually have a stochastic and uncertain characteristic, are subject to certain random distribution. The dynamic scheduling and controlling of manufacturing system under stochastic environment are attracting more and more attention. Considering constant product demand rate and fault repair following exponential distribution, Akella and Kumar¹³ studied the problem of controlling the production rate of a failure-prone manufacturing system with single machine and single product, and an optimal hedging-point production strategy was obtained. Having further studied hedging-point strategy, Kenne and Gharbi¹⁴ pointed out that the manufacturing systems of single machine and two kinds of products, which have constant product demand rate and repair time following exponential distribution, could also obtain the optimal hedging-point production control strategy. Liefooghe et al.¹⁵ studied a multi-objective scheduling problem in uncertain environments with uncertain processing times and proposed an indicator-based evolutionary algorithm to optimize the makespan and the total tardiness concurrently. Combined with Lagrangian relaxation and stochastic dynamic programming method, Luh et al.¹⁶ studied the issue of minimizing expected penalty cost of part tardiness and earliness in cases of uncertain job arrival, processing times and due dates. Boukas and Liu¹⁷ researched the single-machine and single-product machine faults and optimized the rate of processing and maintenance by means of stochastic dynamic programming. Considering the performance measure of total flow-time, a constraint-based $β$ -robust schedule was applied for scheduling of jobs in two-machine flow-shop with uncertain processing times by Ullah et al.¹⁸ Xia et al.¹⁹ considered due date assignment and sequencing for multiple jobs in a single-machine shop; a heuristic procedure was developed to minimize a linear combination of three penalties. Yang and Geunes²⁰ considered the scheduling problem with one uncertain job and multiple uncertain jobs on a single machine, and predictive–reactive scheduling is addressed to minimize total expected cost, which is composed of the cost of unused idle time, the disruption cost and weighted tardiness costs. Sethi et al.²¹ investigated the problem of hierarchical production control in a stochastic manufacturing system producing a single product. Kouvelis et al.²² investigated the problem of optimization of makespan in a two-machine flow-shop with fuzzy processing times. Focus of existing literature is the stochastic scheduling research on single machine and single/two type(s) of product, and unfortunately, few addresses the problem of stochastic scheduling of multiple machines and products.

On the other hand, various types of jobs in actual production may share some resources in the manufacturing system. Lack of effective controlling strategy may lead to deadlock state and finally result in partial or complete collapse of KMC, which would severely lower the production efficiency of enterprises. Issues of deadlock are generally analyzed and modeled by means of Petri nets, automata and so on.^23–28 Petri net and automata are two effective modeling tools for discrete-event dynamic systems (DEDS) and can be employed to analyze the dynamics of DEDS such as dynamic scheduling and deadlock. Compared to automata, Petri net is more suitable for complex systems with concurrency relations, and the system studied in this article does not have concurrency relations; automata can be used to effectively solve the problem in the study. On the other hand, this article is based on the research results of previous work²⁷ in which automata are adopted to obtain very good results. Therefore, automata are used for modeling tools of the system herein.

For most of scheduling problems, we do not consider the existence of deadlock, meaning deadlock and scheduling are often taken under advisement separately, which will negatively affect the performance of systems. Therefore, we should not only prevent deadlock but also develop some algorithms which can effectively improve and optimize system performance.²⁹ In the past decade, some researchers have addressed the deadlock-free scheduling problem. Yoon and Lee³⁰ introduced a resource request matrix to represent operational states and then proposed a deadlock-free scheduling approach that can perform scheduling and deadlock management in semiconductor fabrication. Abdallah et al.³¹ used timed Petri nets to find the optimal or near-optimal deadlock-free schedule for the Systems of Sequential Systems with Shared Resources (S⁴R). Wu and Zhou³² used a two-layer structure to schedule semiconductor track systems and avoided deadlock, which was modeled with a colored timed resource-oriented Petri net. Golmakani et al.³³ employed Ramadge–Wonham (R-W) theory to construct a deadlock-free search space to be utilized by A* search algorithm to obtain deadlock-free schedules. Based on a job insertion algorithm, Fahmy et al.²⁹ proposed a generic deadlock-free reactive scheduling approach for flexible job shops. However, little work is reported on the deadlock-free scheduling problem with stochastic job arrival, processing times and product demands.

This article focuses on the cost of work-in-process (WIP) inventory and backlog in KMC composed of multiple machines and products. The main contribution of this work is the combination of deadlock control and production scheduling under stochastic production environments with multiple machines and products, and the deadlock-free scheduling strategy (DFSS) is proposed and developed. With the help of KMC’s advanced hardware and software architecture, according to the real-time status of the system, the job type and processing speed can be automatically selected and controlled in real time on the basis of the proposed DFSS, which only contributes to the improvement of the self-adaptation capacity for KMC. Based on the finite automaton (FA) theory, a concept of cost automata (CA) is put forward and the deadlock supervisor was structured (section “KMC deadlock supervisor”). After discretization of the objective function by uniformization technique, a stochastic dynamic programming model on expected cost objective function of KMC is established, and the character of optimal objective function is analyzed. Based on all the above, a heuristics approximate dynamic programming (HADP) algorithm is developed to solve the aforementioned stochastic dynamic programming model. Consequently, an effective KMC DFSS is proposed to meet the enterprises’ needs of minimizing operating costs of KMC (section “KMC scheduling strategy”). Finally, a case study is presented to demonstrate the effectiveness of the DFSS (section “Simulation experiments and analysis”).

Problem formulation and objective function

Problem formulation

Assuming there are m manufacturing agents $(Ag = {A g_{1}, \dots, A g_{i}, \dots, A g_{m}})$ processing n types of jobs $(P = {p_{1}, \dots, p_{j}, \dots, p_{n}})$ in a KMC, different types of jobs have different processing paths, and the processed jobs are turned into finished products in this cell. There are h buffers divided into three types: input buffers, medium buffers and output buffers, namely, $Buf = {B^{i}; B^{m}; B^{o}} = {b_{1}^{i}, \dots, b_{h_{i}}^{i}; b_{1}^{m}, \dots, b_{h_{m}}^{m} {; b}_{1}^{o}, \dots, b_{h_{o}}^{o}}$ . Buffer $B^{i}$ stores blanks that have been just inputted and wait for being processed, $B^{m}$ stores semi-finished jobs in the cell and $B^{o}$ stores finished products outputted from the cell. The buffer numbers in the sets $B^{i}$ , $B^{m}$ and $B^{o}$ are h _i, h _m and h _o, respectively. $B^{i}$ and $B^{o}$ are unlimited buffers, which are material exchange channels between KMC and external environment; $B^{m}$ is a limited buffer, which is exclusive for the cell, with no interaction with the outside world, and its storage capacity is limited.

In order to describe the problem clearly, a KMC is shown in Figure 1, with m = 3, n = 3, h _i = 1, h _m = 1 and h _o = 1. There are three agents $(A g_{1}, A g_{2}, A g_{3})$ , three buffers $(b^{i}, b^{m}, b^{o})$ and three types of jobs $(p_{1}, p_{2}, p_{3})$ ; the processing paths of the jobs are denoted by the arrow lines in Figure 1. For example, $p_{1}$ enters into $b_{1}^{i}$ waiting to be processed. When $A g_{1}$ is free, the job is selected for processing. After the processing is finished, $p_{1}$ is inputted into $b_{1}^{m}$ and processed by $A g_{2}$ ; then it goes into $b_{1}^{o}$ . Finally, the finished job leaves $b_{1}^{o}$ when product demands for this kind of job arrive. Other types of jobs have a similar description.

Figure 1.

Knowledgeable manufacturing cell.

As shown in Figure 1, when $b_{1}^{m}$ is full of $p_{1}$ and reaches its maximum capacity, and in the meanwhile, $A g_{2}$ is being occupied by $p_{3}$ , KMC will not be able to continue to carry out processing on $p_{1}$ and $p_{3}$ , which leads to deadlock of KMC. Therefore, monitoring KMC to avoid deadlock state is necessary. At the same time, we should minimize the cost function caused by the expense of job processing and inventory, product inventory and backlog. Based on the characteristics of material flow in production systems, $p_{j}$ shows Poisson distribution with the input rate of $ω_{j}$ . The processing time of $p_{j}$ by $A g_{i}$ follows negative exponential distribution with the parameter $μ_{ij}$ which is controllable and can be adjusted in $[0, {\bar{μ}}_{i}]$ . Demands for the product j are random and the arrivals of these demands are subject to Poisson distribution with the parameter $λ_{j}$ for $i = 1, 2, \dots, m$ and $j = 1, 2, \dots, n$ . In addition, agents cannot be interrupted during processing, and at any time, an agent can only process one job.

Objective function

Taking into account costs of processing, inventory and backlog, the objective function can be expressed by Markov Chain Model with a discount factor in infinite horizon. The objective function of the KMC is thus defined as follows

min_{u} J = E {\int_{0}^{\infty} e^{- β t} g [X (t), u (t)] dt}

(1)

where $g$ is the given cost function; $X (t)$ and $u (t)$ denote the state and control of KMC at the moment of $t$ , respectively; $X (t) = (x_{1}^{i} (t), \dots, x_{n}^{i} (t), x_{1}^{m} (t), \dots, x_{n}^{m} (t), x_{1}^{o} (t), \dots, x_{n}^{o} (t), α_{1, 1} (t), \dots, α_{i, j} (t), \dots, α_{m, n} (t {))}^{T}$ ; $x_{j}^{i} (t)$ and $x_{j}^{m} (t)$ are the amount of workpieces waiting for processing in input and output buffers at the moment of t, respectively; $x_{j}^{i} (t), x_{j}^{m} (t) \in Z^{+} \cup {0}$ ( $Z^{+}$ is a set of all positive integers); $x_{j}^{o} (t)$ is the inventory amount of finished products in output buffer; $x_{j}^{o} (t) \in Z$ ( $Z$ is a set of all integers), a positive or negative value of $x_{j}^{o} (t)$ means the surplus or shortage number of finished products, $j = 1, 2, \dots, n$ ; $α_{i, j} (t)$ describes the state of $A g_{i}$ at the moment of t, $α_{i, j} (t) \in {0, 1}$ , 0 means it is free, while 1 indicates $A g_{i}$ is occupied by the jth class of workpieces, $i = 1, 2, \dots, m$ , $j = 1, 2, \dots, n$ ; $β$ is the Markov discount factor, $0 < β \leq 1$ ; $c_{j, k_{i}}^{i}, c_{j, k_{m}}^{m}$ denote the inventory cost of the jth class of workpieces in buffer $b_{k_{i}}^{i}$ and $b_{k_{m}}^{m}$ , respectively; $c_{j, k_{o}}^{+ o}, c_{j, k_{o}}^{- o}$ represent punishment factors on inventory or backlog of the jth class of products in $b_{k_{o}}^{o}$ ; $c_{A g_{i}}$ denotes the processing cost of $A g_{i}$ , $i = 1, \dots, m$ ; $j = 1, \dots, n$ ; $k_{i} = 1, \dots, h_{i}$ ; $k_{m} = 1, \dots, h_{m}$ ; and $k_{o} = 1, \dots, h_{o}$ . Therefore, the cost function of KMC in Figure 1 can be expressed as

g [X (t), u (t)] = \sum_{j = 1}^{3} c_{j, 1}^{i} x_{j}^{i} (t) + \sum_{j = 1}^{3} c_{j, 1}^{m} x_{j}^{m} (t) + \sum_{j = 1}^{3} [c_{j, k_{o}}^{+ o} x_{j}^{+ m} (t) + c_{j, k_{o}}^{- o} x_{j}^{- m} (t)] + \sum_{i = 1}^{3} \sum_{j = 1}^{3} c_{A g_{i}} α_{i, j} (t)

(2)

where $x_{j}^{+ m} (t) = max {0, x_{j}^{m}}$ and $x_{j}^{- m} (t) = max {0, - x_{j}^{m}}$ , which calculates the total cost caused by job inventory in buffers, product inventory or backlog and processing.

KMC deadlock supervisor

Let $Σ_{r}$ be a limited input alphabet and each letter stand for an event. $Q_{r}$ stands for a limited state set, $q_{0_{r}}$ for initial state and $q_{0_{r}} \in Q_{r}$ . $δ_{r}$ is state transition function defined as $δ_{r} : Q_{r} \times Σ_{r} \to Q_{r}$ . $σ \in Σ_{r}$ is a element or symbol in the input alphabet, that is, an event. $Q_{mk}^{r}$ is state set for mark or end. Thus, the five-tuple ${Σ_{r}, Q_{r}, q_{0_{r}}, δ_{r} (q, σ), Q_{mk}^{r}}$ is used to describe a FA, that is

F A_{r} = {Σ_{r}, Q_{r}, q_{0_{r}}, δ_{r} (q, σ), Q_{mk}^{r}}

(3)

where the subscript $r$ in the equation denotes a specific automaton and its elements, $r = 1, 2, \dots, \infty$ . Since automata are used to describe only the logical relation of event occurrence and state transfer, it lacks the ability to describe quantitative indicators such as cost. To make automata a basic modeling tool for the supervising and scheduling of KMC, it is necessary to consider the costs associated with scheduling during modeling with automata. Thus, based on the FA in equation (3), the CA is defined as

C A_{r} = {Σ_{r}, Q_{r}, q_{0_{r}}, δ_{r} (q, σ), Q_{mk}^{r}, g_{t_{e}}}

(4)

where $g_{t_{e}}$ is the cost function of unit time after feasible events occur at the moment $t$ , $g : X (t) \to R^{+}$ , $X (t)$ is the cell state after the event $e$ and other variables are similar to corresponding variables in finite automata. In order to describe the complicated DEDS with several simple automata, it is necessary to define some logic operations for the interchangeable relations between automata. Shuffle operation is defined to describe asynchronous behavior relationship between the automata $C A_{1}$ and $C A_{2}$ , and meet operation is defined for synchronized behavior relationship description. So, based on the R-W controlled-automata theory,^34,35 the shuffle operation between automaton $C A_{1}$ and $C A_{2}$ is defined as follows

\begin{matrix} C A_{1 \otimes 2} & = C A_{1} \otimes C A_{2} \\ = {⋃_{r = 1, 2} Σ_{r}, Q, q_{0}, δ (q, σ), Q_{mk}, g_{t_{e}}} \end{matrix}

(5)

where $⋃_{r = 1, 2} Σ_{r}$ is the union set of input event sets in $C A_{1}$ and $C A_{2}$ , namely, $⋃_{r = 1, 2} Σ_{r} = Σ_{1} \cup Σ_{2}$ . $Q$ stands for the global state set composed of two automata. For the global state $q \in Q$ , there is $q \in (q_{u_{1}} \in Q_{1}, q_{u_{2}} \in Q_{2})$ . Similarly, for the initial state $q_{0}$ in equation (5), $q_{0} = (q_{0_{1}} \in Q_{1}, q_{0_{2}} \in Q_{2})$ . $σ \in ⋃_{r = 1, 2} Σ_{r}$ is the event in the automaton $C A_{1}$ or $C A_{2}$ . $δ$ is the state transition function, that is, $δ : Q \times ⋃_{r = 1, 2} Σ_{r} \to Q$ , and it can be defined herein as

\begin{matrix} δ ((q_{u_{1}}, q_{u_{2}}), σ) \\ = {\begin{matrix} (δ_{1} (q_{u_{1}}, σ), q_{u_{2}}) & if δ_{1} (q_{u_{1}}, σ)! \land δ_{2} (q_{u_{2}}, σ) \\ (q_{u_{1}}, δ_{2} (q_{u_{2}}, σ)) & if δ_{1} (q_{u_{1}}, σ) \land δ_{2} (q_{u_{2}}, σ)! \\ ϕ & otherwise \end{matrix} \end{matrix}

(6)

where $δ_{1} (q_{u_{1}}, σ)!$ denotes that there is a definition for $δ_{1} (q_{u_{1}}, σ)$ and so is for $δ_{2} (q_{u_{2}}, σ)!$ . $Q_{mk}$ stands for the set of global end state, namely, $Q_{mk} = {(q_{mk}^{1} \in Q_{mk}^{1}, q_{mk}^{2} \in Q_{mk}^{2})}$ . Accordingly, the meet operation of the two automata $C A_{1}$ and $C A_{2}$ is

\begin{matrix} C A_{1 \oplus 2} & = C A_{1} \oplus C A_{2} \\ = {⋂_{r = 1, 2} Σ_{r}, Q, q_{0}, δ (q, σ), Q_{mk}, g_{t_{e}}} \end{matrix}

(7)

where $Q$ , $q_{0}$ , $q$ , $σ$ and $Q_{mk}$ denote the same meaning as those in meet operation. $⋂_{r = 1, 2} Σ_{r}$ is the intersection set of input event set of $C A_{1}$ and $C A_{2}$ , that is, $⋂_{r = 1, 2} Σ_{r} = Σ_{1} \cap Σ_{2}$ . The state transition function $δ (q, σ)$ is defined as follows

\begin{matrix} δ ((q_{u_{1}}, q_{u_{2}}), σ) \\ = {\begin{matrix} (δ_{1} (q_{u_{1}}, σ), δ_{2} (q_{u_{2}}, σ)) if δ_{1} (q_{u_{1}}, σ)! \land δ_{2} (q_{u_{2}}, σ)! \\ ϕ otherwise \end{matrix} \end{matrix}

(8)

With shuffle and meet operations defined as above, logic operation can be performed on several automata to describe complicated DEDS. It is worth noting that $g_{t_{e}}$ is invariable in automata during performing shuffle and meet operations. For the detailed build of deadlock supervisor for KMC, refer to the literature by Yang and Yan.²⁷

KMC scheduling strategy

Discretization of objective function

Manufacturing cell described by automata is essentially a DEDS, which, only at certain discrete moments, for instance, only when the agent accomplishes a working operation, will select an appropriate job in buffer to process by control strategy, that is, control is imposed at discrete time. Therefore, we should discretize the objective function to get a discrete-time Markov model.

To realize the independence of time intervals of the state transfer of cells, that is, the transfer rate is independent of the state and control of system, the uniform technology is used, and the uniform occurrence probability is set as $ν$ , that is

ν = \sum_{j = 1}^{n} ω_{j} + \sum_{j = 1}^{n} λ_{j} + 2 \sum_{i = 1}^{m} {\bar{μ}}_{i}

(9)

The possible event set of system is expressed as $Σ = {a_{j}, d_{j}, b_{ij}, c_{ij}, e_{self}}$ , where the event $a_{j}$ denotes the arrival of the jth workpiece, $d_{j}$ indicates the demand arrival of the jth product, $b_{ij}$ means $A g_{i}$ begins to process the jth workpiece, $c_{ij}$ means the processing of the jth workpiece is accomplished by $A g_{i}$ and $e_{self}$ is the virtual self-transfer event of states. The possible incidents can be divided into the controllable event set $Σ_{c}$ and uncontrollable event set $Σ_{u}$ and further $Σ_{c} = {b_{ij}}$ and $Σ_{u} = {a_{j}, d_{j}, c_{ij}, e_{self}}$ . Taking the job $p_{1}$ in Figure 1 for an instance, the mapping relations between events and changes of cell state are

\begin{matrix} a_{1} (X (t)) = & (x_{1}^{i} (t) + 1, x_{2}^{i} (t), x_{3}^{i} (t), x_{1}^{m} (t), x_{2}^{m} (t), \\ x_{3}^{m} (t), x_{1}^{o} (t), x_{2}^{o} (t), x_{3}^{o} (t), α_{1, 1}, α_{1, 2}, α_{1, 3}, \\ {α_{2, 1}, α_{2, 2}, α_{2, 3}, α_{3, 1}, α_{3, 2}, α_{3, 3})}^{T} \\ d_{1} (X (t)) = & (x_{1}^{i} (t), x_{2}^{i} (t), x_{3}^{i} (t), x_{1}^{m} (t), x_{2}^{m} (t), \\ x_{3}^{m} (t), x_{1}^{o} (t) - 1, x_{2}^{o} (t), x_{3}^{o} (t), α_{1, 1}, α_{1, 2}, α_{1, 3}, \\ {α_{2, 1}, α_{2, 2}, α_{2, 3}, α_{3, 1}, α_{3, 2}, α_{3, 3})}^{T} \\ b_{11} (X (t)) = & (x_{1}^{i} (t) - 1, x_{2}^{i} (t), x_{3}^{i} (t), x_{1}^{m} (t), \\ x_{2}^{m} (t), x_{3}^{m} (t), x_{1}^{o} (t), x_{2}^{o} (t), x_{3}^{o} (t), 1, α_{1, 2}, α_{1, 3}, \\ {α_{2, 1}, α_{2, 2}, α_{2, 3}, α_{3, 1}, α_{3, 2}, α_{3, 3})}^{T} \\ c_{11} (X (t)) = & (x_{1}^{i} (t), x_{2}^{i} (t), x_{3}^{i} (t), x_{1}^{m} (t) + 1, x_{2}^{m} (t), \\ x_{3}^{m} (t), x_{1}^{o} (t), x_{2}^{o} (t), x_{3}^{o} (t), 0, α_{1, 2}, α_{1, 3}, \\ {α_{2, 1}, α_{2, 2}, α_{2, 3}, α_{3, 1}, α_{3, 2}, α_{3, 3})}^{T} \\ e_{self} (X (t)) = & (x_{1}^{i} (t), x_{2}^{i} (t), x_{3}^{i} (t), x_{1}^{m} (t), x_{2}^{m} (t), \\ x_{3}^{m} (t), x_{1}^{o} (t), x_{2}^{o} (t), x_{3}^{o} (t), α_{1, 1}, α_{1, 2}, \\ {α_{1, 3}, α_{2, 1}, α_{2, 2}, α_{2, 3}, α_{3, 1}, α_{3, 2}, α_{3, 3})}^{T} \end{matrix}

The mapping relations on the other job $p_{j}$ are similar to the above. As revealed by the above, the virtual self-transfer event makes the state of the system divert to itself, namely, $e_{self} (X (t)) = X (t)$ ; its physical meaning indicates that the system leaves the state $X$ by the uniform occurrence probability $ν$ and returns $X$ at the transfer rate less than $ν$ . The state transfer is driven by the system events, and the probability of states transfer is shown in Figure 2. The status step transfer probability function is as follows

\begin{matrix} \Pr (a_{j} (X) | X) = \frac{{\bar{ω}}_{j}}{v} \\ \Pr (d_{j} (X) | X) = \frac{λ_{j}}{v} \\ \Pr (b_{ij} (X) | X) = \Pr (c_{ij} (X) | X) = \frac{μ_{ij}}{v} \\ \Pr (e_{self} (X) | X) = \frac{(2 \sum_{i = 1}^{m} {\bar{μ}}_{i} - 2 \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij})}{v} \end{matrix}

Figure 2.

Schema of state transition of KMC.

Set $t_{k}$ as the time of the kth state change of cell, $0 = t_{0} < \dots < t_{k} < \dots$ ; $τ_{k} = t_{k} - t_{k - 1}$ as the time interval of transfer between the (k − 1)th and the kth states; let $X_{k} = X (t_{k})$ be the cell state after the kth state change, for $t_{k} \leq t < t_{k + 1}$ , $X (t) = X_{k}$ ; let $u_{k} = u (t_{k})$ be the control put on the system after the kth state change, for $t_{k} \leq t < t_{k + 1}$ , $u (t) = u_{k}$ . Thus, the discretization of the objective function of the system is

J = E {\int_{0}^{\infty} e^{- β t} g (X (t), u (t)) dt} = \sum_{k = 0}^{\infty} E {\int_{t_{k}}^{t_{k + 1}} e^{- β t} g (X (t), u (t)) dt} = \sum_{k = 0}^{\infty} E {\int_{t_{k}}^{t_{k + 1}} e^{- β t} dt} E {g (X_{k}, u_{k})}

(10)

In light of the independence of time intervals of state changes, we have

E (\int_{t_{k}}^{t_{k + 1}} e^{- β t} dt) = \frac{E (e^{- β t_{k}}) (1 - E (e^{- β (t_{k + 1} - t_{k})}))}{β} = \frac{E (e^{- β t_{k}}) (1 - E (e^{- β (τ_{k + 1})}))}{β}

(11)

E (e^{- β τ}) = \int_{0}^{\infty} e^{- β τ} v e^{- v τ} d τ = \frac{v}{(β + v)}

(12)

\begin{matrix} E (e^{- β t_{k}}) & = E {e^{- β ((t_{1} - t_{0}) + \dots + (t_{k} - t_{k - 1}))}} \\ = E (e^{- β τ_{1}}) \dots E (e^{- β τ_{k}}) \end{matrix}

(13)

Letting $θ = v / (β + v)$ , we obtain from formulas (10)–(13)

J = E {\int_{0}^{\infty} e^{- β t} g (X (t), u (t)) dt} = \frac{1}{β + v} \sum_{k = 0}^{\infty} θ^{k} E {g (X_{k}, u_{k})}

(14)

Thus, the original problem is converted to an equivalent discrete-time Markov problem in an infinite domain with the discount factor $θ$ ; in other words, the continuous infinite horizon objective function is converted to the sum of multi-stage cost function, which can be solved by the corresponding Markov decision-making optimization theory.

Property analysis of objective function

Based on discrete stochastic dynamic programming,³⁶ the infinite horizon problem can be cut and translated into a N-phase issue. Assuming $J_{0} (X, u) = 0, X \in X_{s}$ , and based on the status step transfer probability function and formula (14), the Bellman equation of cost on KMC can be written as

J_{k + 1} (X, u) = \frac{1}{β + v} min_{u} {g (X) + \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X)) + \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) + \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} J_{k} (b_{ij} (X)) + \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} J_{k} (c_{ij} (X)) + (2 \sum_{i = 1}^{m} {\bar{μ}}_{i} - 2 \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij}) J_{k} (_{self} (X))}, X \in X_{s}, k = 0, 1, \dots, N - 1

(15)

where $X_{s}$ is the set of KMC states and $J_{k} (X)$ represents the optimal value of objective function in k phases starting from a random state $X$ . The Bellman equation of cost function in equation (15) has the following properties.

Theorem 1

Let $J_{0} (X, u) = 0$ , if $J (X, u)$ is a bounded function for any state $X$ , then we have $lim_{k \to + \infty} J_{k} (X, u) = J (X, u)$ .

Proof

Let $g (X, u) \leq φ$ and $φ$ be a large positive number. By equation (14), we obtain

\begin{matrix} lim_{N \to \infty} {\frac{1}{β + v} \sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})}} \leq \frac{1}{β + v} \\ \sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})} + \frac{1}{β + v} \sum_{k = N}^{\infty} θ^{k} φ \\ = \frac{1}{β + v} \sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})} + \frac{φ}{β + v} \cdot \frac{θ^{k}}{1 - θ} \end{matrix}

(16)

Supposing Markov process follows the optimal schedule policy, from equation (16) we get

\begin{matrix} J (X, u) = min_{u_{k}} {lim_{N \to \infty} {\frac{1}{β + v} \sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})}}} \\ \leq min_{u_{k}} {\frac{1}{β + υ} \sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})}} + \frac{φ}{β + v} \cdot \frac{θ^{N}}{1 - θ} \\ = J_{N} (X, u) + \frac{φ}{β + v} \cdot \frac{θ^{N}}{1 - θ} \end{matrix}

(17)

Taking the limit on both sides of formula (17), from $lim_{N \to \infty} φ / (β + v) \cdot θ^{N} / (1 - θ) = 0$ we have $J (X, u) \leq lim_{N \to \infty} J_{N} (X, u)$ . On the other hand, since the cost function $g (X, u) \geq 0$ , by the definition of the objective function $J (X, u)$ , we get

J (X, u) = \frac{1}{β + v} {\sum_{k = 0}^{N - 1} θ^{k} E {g (X_{k}, u_{k})} + \sum_{k = N}^{\infty} θ^{k} E {g (X_{k}, u_{k})}} = J_{N} (X, u) + \frac{1}{β + v} \sum_{k = N}^{\infty} θ^{k} E {g (X_{k}, u_{k})}

so, we obtain $J (X, u) \geq lim_{N \to \infty} J_{N} (X, u)$ , and therefore, $J (X, u) = lim_{N \to \infty} J_{N} (X, u)$ for all states. This completes the proof.

With Theorem 1 and formula (15), we can secure the optimal scheduling strategy of KMC.

Theorem 2

When KMC is in the state $X$ , its optimal scheduling strategy can be expressed as

μ_{ij} = {\begin{matrix} {\bar{μ}}_{i} & if J (b_{ij} (X)) + J (c_{ij} (X)) \leq 2 J (X) \\ 0 & otherwise \end{matrix}, i = 1, 2, \dots, m, j = 1, 2, \dots, n

Proof

From Bellman equation of the objective function in equation (15), we get

\begin{matrix} J_{k + 1} (X, u) = & \tilde{g} (X) + \frac{1}{β + v} min_{u} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) + 2 \sum_{i = 1}^{m} {\bar{μ}}_{i} J_{k} (X) + \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X)) \\ + \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} {J_{k} (b_{ij} (X)) + J_{k} (c_{ij} (X)) - 2 J_{k} (X)}} \\ = & \tilde{g} (X) + \frac{1}{β + v} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) + 2 \sum_{i = 1}^{m} {\bar{μ}}_{i} J_{k} (X) + \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X)) \\ + min_{u} {\sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} {J_{k} (b_{ij} (X)) + J_{k} (c_{ij} (X)) - 2 J_{k} (X)}}} \end{matrix}

(18)

where $\tilde{g} (X) = (1 / (β + v)) g (X)$ . Taking the limit $k$ on the sides of equation (18), we can use Theorem 1 to obtain the optimal scheduling strategy in Theorem 2.

The above optimal scheduling strategy of KMC is specified as follows. When some $A g_{i}$ is idle and there exist many jobs to be processed, calculate $j' = \arg min_{j} {J_{k} (b_{ij} (X)) + J_{k} (c_{ij} (X)) - 2 J_{k} (X)}$ ; hence, the job $p_{j'}$ is selected by $A g_{i}$ and the processing rate of $p_{j'}$ is determined by the optimal scheduling strategy in Theorem 2. The related properties of the optimal objective function $J (X, u)$ are discussed below.

Definition 1

When KMC passes through the event sequence $e_{l} \dots e_{1}$ from the state $X$ , it can be transferred to the state $e_{l} \dots e_{1} X$ , which is a safe one, and then, $e_{l} \dots e_{1}$ is defined as the safe event sequence of state $X$ .

According to Definition 1, if $e_{l} \dots e_{1}$ is the safe event sequence of $X$ , the same is true of its subset of event sequence $e_{l'} \dots e_{1}$ .

Lemma 1

If the relation $g (c_{ij} (b_{ij} (X))) \leq g (b_{ij} (X))$ holds in the state $X$ for KMC, we have $g (c_{ij} (b_{ij} (e_{l} \dots e_{1} X))) \leq g (b_{ij} (e_{l} \dots e_{1} X))$ for cost function, where $c_{ij} b_{ij} e_{l} \dots e_{1}$ is the safe event sequence of state $X$ .

Proof

By the definition of cost function, if there exists no job $p_{j}$ to be processed or the job processing on $A g_{i}$ is not $p_{j}$ in the state $e_{l} \dots e_{1} X$ , it follows that $g (c_{ij} (b_{ij} (e_{l} \dots e_{1} X))) = g (b_{ij} (e_{l} \dots e_{1} X))$ ; in other cases, $g (c_{ij} (b_{ij} (e_{l} \dots e_{1} X))) - g (b_{ij} (e_{l} \dots e_{1} X)) = g (c_{ij} (b_{ij} (X))) - g (b_{ij} (X))$ holds. Therefore, we have $g (c_{ij} (b_{ij} (e_{l} \dots e_{1} X))) \leq g (b_{ij} (e_{l} \dots e_{1} X))$ .

Lemma 2

If the relation $g (b_{ij} (X)) \leq g (X)$ holds in the state $X$ for KMC, we have $g (b_{ij} (e_{l} \dots e_{1} X)) \leq g (e_{l} \dots e_{1} X)$ for cost function, where $e_{l} \in Σ$ and $e_{l} \dots e_{1} X$ is deadlock-free state of KMC.

Proof

Similar to the proof of Lemma 1, if there exists no job $p_{j}$ to be processed or the job processing on $A g_{i}$ is not $p_{j}$ in $e_{l} \dots e_{1} X$ , then we have $g (b_{ij} (e_{l} \dots e_{1} X)) = g (e_{l} \dots e_{1} X)$ ; considering other cases, it is easy to obtain $g (b_{ij} (e_{l} \dots e_{1} X)) - g (e_{l} \dots e_{1} X) = g (b_{ij} (X)) - g (X)$ . So, $g (b_{ij} (e_{l} \dots e_{1} X)) \leq g (e_{l} \dots e_{1} X)$ holds.

Lemma 3

Let $Σ_{X}$ be a possible event set in the state $X$ , and there exists the event $e_{u} \in Σ_{X} \cap Σ_{u} - c_{ij}$ . If there exists event $b_{ij} \in E_{X}$ as well, then $b_{ij} \in E_{e_{u} X}$ holds, where $E_{X}$ and $E_{e_{u} X}$ are the feasible event sets of $X$ and $e_{u} X$ , respectively.

Proof

Suppose $b_{ij} \notin E_{e_{u} X}$ , that is to say, $b_{ij}$ is a prohibitive event in the state $e_{u} X$ . Since $b_{ij} \in E_{X}$ , $b_{ij}$ occurs in $X$ , while $e_{u}$ is uncontrollable event, if the event $e_{u}$ occurs before event $c_{ij}$ , then the KMC will fall into deadlock state in accordance with supposition $b_{ij} \notin E_{e_{u} X}$ . This completes the proof to Lemma 3.

Based on the above lemmas, the properties of the optimal objective function $J (X, u)$ can be acquired as follows.

Theorem 3

If $g (c_{i' j'} (b_{i' j'} (X))) \leq g (b_{i' j'} (X))$ holds for the state $X$ of KMC ( $i \in {1, \dots, m}$ , $j \in {1, \dots, n}$ ), then we have $J (c_{i' j'} (b_{i' j'} (X))) \leq J (b_{i' j'} (X))$ for the optimal objective function $J (X, u)$ .

Proof

For the last item in equation (18), since each machine can only process one job at one moment, we have

{\begin{matrix} μ_{ij'} = {\bar{μ}}_{i}, if J (b_{ij'} (X)) + J (c_{ij'} (X)) - 2 J (X) \leq 0 \\ μ_{ij} = 0, j = 1, \dots, n, and j \neq j' \end{matrix}

(19)

Or else, if $J (b_{ij} (X)) + J (c_{ij} (X)) - 2 J (X) > 0$ , we obtain

μ_{ij} = 0, j = 1, \dots, n

(20)

Based on equations (19) and (20), we have

\begin{matrix} J_{k + 1} (X, u) = {\tilde{g}}_{1} (x) + \frac{1}{β + v} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) + \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X)) \\ + \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (X)) + J_{k} (c_{ij} (X)), 2 J_{k} (X)}} \end{matrix}

(21)

The mathematical induction is adopted to prove the Theorem herein. With $k = 0$ , we have $J_{0} (c_{i' j'} (b_{i' j'} (X))) \leq J_{0} (b_{i' j'} (X))$ . Supposing that $J_{k} (c_{i' j'} (b_{i' j'} (X))) \leq J_{k} (b_{i' j'} (X))$ holds, we get the following for $k + 1$ step by formula (21)

\begin{matrix} J_{k + 1} (c_{i' j'} (b_{i' j'} (X))) - J_{k + 1} (b_{i' j'} (X)) = {\tilde{g} (c_{i' j'} (b_{i' j'} (X))) - {\tilde{g}}_{1} (b_{i' j'} (X))} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (c_{i' j'} (b_{i' j'} (X)))) - \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (b_{i' j'} (X)))} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (c_{i' j'} (b_{i' j'} (X)))) - \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (b_{i' j'} (X)))} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) + J_{k} (c_{ij} (c_{i' j'} (b_{i' j'} (X)))), 2 J_{k} (c_{i' j'} (b_{i' j'} (X)))} \\ - \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X))), 2 J_{k} (b_{i' j'} (X))}} \end{matrix}

(22)

By Lemma 1 and the condition of Theorem 3, the first item of right side of equation (22) is less than or equal to zero, that is

\tilde{g} (c_{i' j'} (b_{i' j'} (X))) - {\tilde{g}}_{1} (b_{i' j'} (X)) \leq 0

(23)

From the aforementioned mapping relation between event and state change, $d_{j} (c_{i' j'} (b_{i' j'} (X)))$ and $c_{i' j'} (b_{i' j'} (d_{j} (X)))$ are of the same state of KMC, and therefore, we have $J_{k} (d_{j} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (b_{i' j'} (d_{j} (X))))$ . Similarly, $J_{k} (d_{j} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (d_{j} (X)))$ holds. Thus, we can use the induction hypothesis of $k$ step and Lemma 1 to obtain

\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (c_{i' j'} (b_{i' j'} (X)))) - \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (b_{i' j'} (X))) \leq 0

(24)

The following two cases are discussed for the third item of right side of equation (22):

Case 1. If $j \neq j'$ , then $J_{k} (a_{j} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (b_{i' j'} (a_{j} (X))))$ and $J_{k} (a_{j} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (a_{j} (X)))$ . By the induction hypothesis of $k$ step and Lemma 1, we have

\sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (c_{i' j'} (b_{i' j'} (X)))) - \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (b_{i' j'} (X))) \leq 0

(25)

Case 2. If $j = j'$ , there exists the job $p_{j'}$ to be processed or the job being processed on machine $A g_{i'}$ is $p_{j'}$ in the state $X$ , then similar to the previous case (Case 1), formula (25) is true; if there is no job $p_{j'}$ to be processed by $A g_{i'}$ in state $X$ , then the states $a_{j} (c_{i' j'} (b_{i' j'} (X)))$ and $a_{j} (X)$ are of the same state of KMC, thus $J_{k} (a_{j} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (a_{j} (X))$ . As the event $b_{i' j'}$ cannot occur in $X$ , that is to say, $a_{j} (b_{i' j'} (X))$ and $a_{j} (X)$ are of the same state of KMC, formula (25) is true; similarly, if the job being processed on $A g_{i'}$ is not $p_{j'}$ , then we have $J_{k} (a_{j} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (a_{j} (X))$ , that is, formula (25) is true.

To prove that the last item of equation (22) is less than or equal to zero, the following cases are studied:

Case 1. If $i \neq i'$ , $j \neq j'$ and $b_{ij} \in E_{b_{i' j'} (X)}$ , by Lemma 3, there is $b_{ij} \in E_{c_{i' j'} (b_{i' j'} (X))}$ , hence we have $b_{ij} (c_{i' j'} (b_{i' j'} (X))) = c_{i' j'} (b_{ij} (b_{i' j'} (X)))$ and $c_{ij} (c_{i' j'} (b_{i' j'} (X))) = c_{i' j'} (c_{ij} (b_{i' j'} (X)))$ , that is, $J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) + J_{k} (c_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (b_{ij} (b_{i' j'} (X)))) + J_{k} (c_{i' j'} (c_{ij} (b_{i' j'} (X))))$ . As $g (c_{i' j'} (b_{i' j'} (X))) \leq g (b_{i' j'} (X))$ and by Lemma 1, $g (c_{i' j'} (b_{ij} (b_{i' j'} (X)))) \leq g (b_{ij} (b_{i' j'} (X)))$ . By the induction hypothesis of $k$ step, we obtain

\begin{matrix} \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) + J_{k} (c_{ij} (c_{i' j'} (b_{i' j'} (X)))), 2 J_{k} (c_{i' j'} (b_{i' j'} (X)))} \\ - \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X))), 2 J_{k} (b_{i' j'} (X))} \leq 0 \end{matrix}

(26)

If $b_{ij} \notin E_{b_{i' j'} (X)}$ and $b_{ij} \notin E_{c_{i' j'} (b_{i' j'} (X))}$ , then $b_{ij} (c_{i' j'} (b_{i' j'} (X))) = c_{i' j'} (b_{i' j'} (X))$ and $b_{ij} (b_{i' j'} (X)) = b_{i' j'} (X)$ , that is, $J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (b_{i' j'} (X)))$ and $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ ; if $b_{ij} \notin E_{b_{i' j'} (X)}$ and $b_{ij} \in E_{c_{i' j'} (b_{i' j'} (X))}$ , then $b_{ij} (b_{i' j'} (X)) = b_{i' j'} (X)$ and $c_{ij} (b_{i' j'} (X)) = b_{i' j'} (X)$ , that is, $J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X))) = 2 J_{k} (b_{i' j'} (X))$ . Hence, formula (26) proves to be true.

Case 2. If $i = i'$ and $j = j'$ , then $b_{ij} (b_{i' j'} (X)) = b_{i' j'} (X)$ . By the induction hypothesis of $k$ step and Lemma 1, we have $2 J_{k} (c_{i' j'} (b_{i' j'} (X))) \leq J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X)))$ , namely, formula (26) holds.

Case 3. If $i = i'$ and $j \neq j'$ , when machine $A g_{i'}$ is idle and there exists job $p_{j'}$ to be processed or job $p_{j'}$ being processed on $A g_{i'}$ in the state $X$ , then $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ and $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ ; otherwise, we have $J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (b_{ij} (X))$ , $J_{k} (c_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{ij} (X))$ , $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{ij} (X))$ and $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (c_{ij} (X))$ . Thus, equation (26) holds in terms of the induction hypothesis of $k$ step.

Case 4. If $i \neq i'$ and $j = j'$ , when $A g_{i}$ is idle and no $p_{j}$ is to be processed in $X$ , then $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ and $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ ; otherwise, if $b_{ij} \in E_{b_{i' j'} (X)}$ , from Lemma 3, we know that $b_{ij} \in E_{c_{i' j'} (b_{i' j'} (X))}$ , thus we have $J_{k} (b_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (b_{ij} (b_{i' j'} (X))))$ and $J_{k} (c_{ij} (c_{i' j'} (b_{i' j'} (X)))) = J_{k} (c_{i' j'} (c_{ij} (b_{i' j'} (X))))$ . So, equation (26) is true in terms of the induction hypothesis of $k$ step and Lemma 1.

From equations (23) to (26), we obtain $J (c_{i' j'} (b_{i' j'} (X))) \leq J (b_{i' j'} (X))$ . This completes the proof of Theorem 3.

According to the above Theorem 3, the properties of the optimal objective function $J (X, u)$ can be determined by the following.

Theorem 4

If $g (b_{i' j'} (X)) \leq g (X)$ and $g (c_{i' j'} (b_{i' j'} (X))) \leq g (b_{i' j'} (X))$ in state $X$ ( $i \in {1, \dots, m}$ and $j \in {1, \dots, n}$ ), then optimal objective function $J (X, u)$ satisfies $J (b_{i' j'} (X)) \leq J (X)$ .

Proof

The mathematical induction is used to prove the Theorem. For $k = 0$ , we have $J_{0} (b_{i' j'} (X)) \leq J_{0} (X)$ . Suppose $J_{k} (b_{i' j'} (X)) \leq J_{k} (X)$ , and from equation (21), we obtain the relation of value function $J (b_{i' j'} (X))$ for $k + 1$ step as follows

\begin{matrix} J_{k + 1} (b_{i' j'} (X), u) = \tilde{g} (b_{i' j'} (x)) \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (b_{i' j'} (X))) + \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (b_{i' j'} (X))) \\ + \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} min {J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X))), 2 J_{k} (b_{i' j'} (X))}} \end{matrix}

(27)

From equations (21) and (27), we get

\begin{array}{l} J_{k + 1} (b_{i^{'} j^{'}} (X)) - J_{k + 1} (X) = {\tilde{g} (b_{i^{'} j^{'}} (X)) - {\tilde{g}}_{1} (X)} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (b_{i^{'} j^{'}} (X))) - \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X))} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (b_{i^{'} j^{'}} (X))) - \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X))} \\ + \frac{1}{β + v} {\sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} \min {J_{k} (b_{i j} (b_{i^{'} j^{'}} (X))) + J_{k} (c_{i j} (b_{i^{'} j^{'}} (X))), 2 J_{k} (b_{i^{'} j^{'}} (X))} \\ - \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} \min {J_{k} (b_{i j} (X)) + J_{k} (c_{i j} (X)), 2 J_{k} (X)}} \end{array}

(28)

Since $g (c_{i' j'} (b_{i' j'} (X))) \leq g (b_{i' j'} (X))$ , it follows that

\tilde{g} (b_{i' j'} (X)) - \tilde{g} (X) \leq 0

(29)

As $J_{k} (d_{j} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (d_{j} (X)))$ , we obtain equation (30) for the second-right item of equation (28) by the induction hypothesis of $k$ step and Lemma 2

\begin{matrix} \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (b_{i^{'} j^{'}} (X))) - \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) = \sum_{j = 1}^{n} λ_{j} J_{k} (b_{i' j'} (d_{j} (X))) - \sum_{j = 1}^{n} λ_{j} J_{k} (d_{j} (X)) \leq 0 \end{matrix}

(30)

The third-right item of equation (28) is discussed in the following cases.

Case 1. If $j \neq j'$ , then $J_{k} (a_{j} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (a_{j} (X)))$ holds. Hence, by the induction hypothesis of $k$ step and Lemma 2, we have

\sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (b_{i' j'} (X))) - \sum_{j = 1}^{n} ω_{j} J_{k} (a_{j} (X)) \leq 0

(31)

Case 2. If $j = j'$ , job $p_{j'}$ is to be processed by $A g_{i'}$ or $A g_{i'}$ is not free in $X$ , then $J_{k} (a_{j} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (a_{j} (X)))$ . Similar to Case 1, inequality (31) holds.

Case 3. If $j = j'$ and there exists no job $p_{j'}$ to be processed by $A g_{i'}$ for $X$ , then $J_{k} (a_{j} (b_{i' j'} (X))) = J_{k} (a_{j} (X))$ , which proves equation (31) to be true.

Now, let us make an analysis on the last item in equation (28), four cases studied below:

Case 1: $i \neq i^{'}$ and $j \neq j'$ . If $b_{ij} \in E_{X}$ and $b_{ij} \in E_{b_{i' j'} (X)}$ , then we have $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (c_{ij} (X)))$ . As each type of job has only a fixed processing route, so $J_{k} (b_{i j} (b_{i^{'} j^{'}} (X))) = J_{k} (b_{i^{'} j^{'}} (b_{i j} (X)))$ . In terms of the induction hypothesis of $k$ step and Lemma 2, the last item of equation (28) is less than or equal to zero, that is

\begin{array}{l} \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} \min {J_{k} (b_{i j} (b_{i^{'} j^{'}} (X))) + J_{k} (c_{i j} (b_{i^{'} j^{'}} (X))), 2 J_{k} (b_{i^{'} j^{'}} (X))} \\ - \sum_{j = 1}^{n} \sum_{i = 1}^{m} {\bar{μ}}_{i} \min {J_{k} (b_{i j} (X)) + J_{k} (c_{i j} (X)), 2 J_{k} (X)} \leq 0 \end{array}

(32)

If $b_{ij} \notin E_{X}$ , then $J_{k} (b_{ij} (X)) + J_{k} (c_{ij} (X)) = 2 J_{k} (X)$ , thus inequality (32) also holds; if $b_{ij} \in E_{X}$ and $b_{ij} \notin E_{b_{i' j'} (X)}$ , then $J_{k} (b_{ij} (b_{i' j'} (X))) + J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X)) + J_{k} (b_{i' j'} (X))$ . Suppose that $p_{j'}$ is selected to be processed by $A g_{i'}$ in $X$ by the optimal scheduling strategy, then $J_{k} (b_{i' j'} (X)) \leq J_{k} (b_{ij} (X))$ ; otherwise, $J (b_{i' j'} (X)) = J (X)$ , so inequality (32) holds.

Case 2: $i \neq i'$ and $j = j'$ . $A g_{i'}$ is idle and has no job $p_{j'}$ to be process in state $X$ , then $J (b_{i' j'} (X)) = J (X)$ ; otherwise, if $b_{ij} \in E_{X}$ and $b_{ij} \in E_{b_{i' j'} (X)}$ , then $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (c_{ij} (X)))$ . Since each type of job has only fixed processing route, we have $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (b_{ij} (X)))$ , which also verifies the validity of equation (32); if $b_{ij}$ is a prohibitive event for $X$ or $b_{i' j'} (X)$ , the analysis will be similar to Case 1.

Case 3: $i = i'$ and $j \neq j'$ . If no $p_{j'}$ is to be processed by idle $A g_{i'}$ in $X$ or $b_{i' j'}$ is a prohibitive event for $X$ , then $J (b_{i' j'} (X)) = J (X)$ ; if there is $p_{j'}$ to be processed by idle $A g_{i'}$ in $X$ , then $J_{k} (c_{ij} (X)) = J_{k} (X)$ , $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ and $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ ; if $A g_{i'}$ is not idle in $X$ , the event $b_{i' j'}$ cannot occur, so we have $J_{k} (c_{ij} (X)) = J_{k} (X)$ , $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{ij} (X))$ and $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (c_{ij} (X))$ . Therefore, in terms of the induction hypothesis, the last item in equation (32) is less than or equal to zero for the above cases.

Case 4. If $i = i'$ and $j = j'$ , then $J_{k} (b_{ij} (b_{i' j'} (X))) = J_{k} (b_{i' j'} (X))$ . By Theorems 3 and 4, we have $J_{k} (c_{i' j'} (b_{i' j'} (X))) \leq J_{k} (b_{i' j'} (X))$ . And if $p_{j'}$ is processed on $A g_{i'}$ in $X$ , then $J_{k} (c_{ij} (b_{i' j'} (X))) = J_{k} (c_{ij} (X))$ ; otherwise, we have $J_{k} (c_{ij} (X)) = J_{k} (X)$ . So, inequality (32) is proved to hold.

By the above equations (29)–(32), we obtain $J (b_{i' j'} (X)) \leq J (X)$ . This completes the proof.

In proving Theorems 3 and 4, the effect of job/order arrival events on deadlock is not taken into account, as input and output buffers are unlimited so that events $a_{j}$ and $d_{j}$ will not lead to the occurrence of deadlock. In terms of the above Theorems, if the capacity of medium buffer is unlimited in KMC, namely, deadlock will never occur, the aforementioned conclusions of the optimal objective function apparently hold. By Theorem 2, if ${Ag}_{i}$ is idle in X, then $J (b_{ij} (X)) + J (c_{ij} (X)) \leq 2 J (X)$ in Theorem 2 is equivalent to $J (b_{ij} (X)) \leq J (X)$ . If there is $p_{j}$ waiting to be processed in the front buffer of $A g_{i}$ , namely, $g (c_{ij} (b_{ij} (X))) \leq g (b_{ij} (X))$ , then $p_{j}$ will be the next candidate to be processed by $A g_{i}$ .

Scheduling strategy of KMC

The physical structure of automata-based DFSS, as shown in Figure 3, is composed of deadlock supervisor module, KMC module and KMC scheduling decision-maker module. DFSS consists of the following major steps:

Step 1. At the running time t, if KMC is required to schedule, the deadlock supervisor and KMC scheduling decision-maker will read the state $X$ at the very moment.

Step 2. The KMC scheduling decision-maker sets state $X$ as the initial state and selects an algorithm to solve the dynamic programming equation; at the same time, it sends $X$ to the deadlock supervisor $SUP V_{KMC}$ and receives the safe event set $E_{X'}$ from deadlock supervisor. After the interactions between the KMC scheduling decision-maker and deadlock supervisor, the objective value function is obtained.

Step 3. With the objective value function and the safe event set $E_{X}$ , KMC in the state of $X$ is scheduled in light of Theorem 2.

Figure 3.

Diagram of deadlock-free scheduling strategy.

It is worth noting that the DFSS can be implemented automatically in real-world KMC. During the manufacturing process, KMC real-time state data can be acquired by RFID device, and the deadlock supervisor software and scheduling decision-maker one are embedded in the host computer. A programmable logic controller is used to collect real-time data from the RFID devices and to transfer data to a host computer via Transmission Control Protocol (TCP)/Internet Protocol (IP) network or industrial field bus, which are stored in a database and employed by deadlock supervisor and scheduling decision-maker.

In the above DFSS steps, the choice of algorithm to solve dynamic programming equation is critical. As we all know, dynamic programming in practical applications is often confronted with “curse of dimensionality,” which is usually triggered by state space, output space or action space, exerting a strong negative impact on the dynamic programming applied to practical engineering. Traditional algorithms, such as Over-Relaxation, pre-Jacobi iteration, Gauss–Seidel method and policy iteration algorithm, all require to traverse all the system states, which gives rise to heavy burden of calculation and storage. However, the approximate dynamic programming (ADP) algorithm can be used to overcome the “curse of dimensionality.” As ADP algorithm mainly employs simulation and function approximation to eliminate or minimize the impact of “curse of dimensionality,” it is good at solving problems of large scale, in the absence of standard model or state-transfer function. Therefore, in recent years, the ADP algorithm has attracted more and more concern from scholars and has been successfully applied in the field of production control and operation management.^37,38 Combined with the aforementioned properties of optimal objective function, a HADP algorithm was proposed in this article; the detailed steps of the algorithm are described as follows:

Step 1. Initialize all $J_{o} (X), X \in X_{s}$ . Set N as the maximum number of stages and let the initial number of stages $k = 0$ .

Step 2. If the state of stage $k$ is $X_{k}$ for KMC, and $A g_{i}$ is idle, then judge whether $P_{X_{k}}^{i}$ is a null set, where $P_{X_{k}}^{i}$ is the set of job types, which is stored in the front buffer and can be processed by $A g_{i}$ in state $X_{k}$ , $i \in {1, \dots, m}$ .

Step 3. If $P_{X_{k}}^{i} \neq ϕ$ , then calculate and obtain the jobs, which satisfy $g (b_{ij} (X)) \leq g (X)$ and $g (c_{ij} (b_{ij} (X))) \leq g (b_{ij} (X))$ . Let $P_{X_{k}}^{i_{1}}$ be the set of the jobs, $p_{j} \in P_{X_{k}}^{i}$ , $j \in {1, 2, \dots, n}$ .

Step 4. Calculate and get the jobs, which satisfy $J_{k - 1} (b_{ij} (X_{k})) + J_{k - 1} (c_{ij} (X_{k})) - 2 J_{k - 1} (X_{k}) \leq 0$ , and let $P_{X_{k}}^{i_{2}}$ be the set of the jobs and $P_{X_{k}}^{i_{2}} \subseteq P_{X_{k}}^{i}$ .

Step 5. If $P_{X_{k}}^{i_{1}} \cup P_{X_{k}}^{i_{2}} \neq ϕ$ , then calculate and get $j' = \arg min_{j} {J_{k - 1} (b_{ij} (X)) + J_{k - 1} (c_{ij} (X)) - 2 J_{k - 1} (X)}$ , $p_{j} \in P_{X_{k}}^{i_{1}} \cup P_{X_{k}}^{i_{2}}$ ; otherwise, $A g_{i}$ selects no job to process, that is, $μ_{ij} = 0$ and $p_{j} \in P_{X_{k}}^{i}$ , then go to Step 9.

Step 6. Apply the $ε - greedy$ policy for job selection, that is, $p_{j'}$ is selected to be processed by $A g_{i}$ with the probability $(1 - ε)$ , and select other jobs $p_{j}$ with the probability $ε$ , $p_{j} \in (P_{X_{k}}^{i_{1}} \cup P_{X_{k}}^{i_{2}} - p_{j'})$ , let $p_{j^{*}}$ be the selected job, $p_{j^{*}} \in {p_{j'} \in p_{j}}$ .

Step 7. Judge whether $b_{i j^{*}}$ is a feasible event in the state $X_{k}$ . If $b_{i j^{*}} \in E_{X_{k}}$ , then set the processing rate $μ_{i j^{*}} = {\bar{μ}}_{i}$ , $μ_{ij} = 0$ and $P_{} j \in (P_{X_{k}}^{i} - P_{j}^{*})$ ; otherwise, set $P_{X_{k}}^{i_{1}} = P_{X_{k}}^{i_{1}} - p_{j^{*}}$ and $P_{X_{k}}^{i_{2}} = P_{X_{k}}^{i_{2}} - p_{j^{*}}$ , and go back to Step 5.

Step 8. If $P_{X_{k}}^{i} = ϕ$ , $A g_{i}$ selects no job to process.

Step 9. Update the objective value function using the following equation

\begin{matrix} J_{k} (X, u) = & \frac{1}{β + v} min_{u} {g (X, u) + \sum_{j = 1}^{n} ω_{j} J_{k - 1} (a_{j} (X)) + \sum_{j = 1}^{n} λ_{j} J_{k - 1} (d_{j} (X)) + \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} J_{k - 1} (b_{ij} (X)) \\ + \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij} J_{k - 1} (c_{ij} (X)) + (2 \sum_{i = 1}^{m} {\bar{μ}}_{i} - 2 \sum_{j = 1}^{n} \sum_{i = 1}^{m} μ_{ij}) J_{k - 1} (e_{self} (X))} \end{matrix}

Set $k = k + 1$ .

Step 10. Determine the next state $X_{k + 1}$ of KMC by probability distribution and set $X_{k} = X_{k + 1}$ . Repeat Steps 2–10 until $k \geq N$ .

For the job set $P_{X_{k}}^{i_{1}}$ obtained by Step 3, by Theorems 3 and 4, if $p_{j} \in P_{X_{k}}^{i_{1}}$ , then $J (b_{ij} (X_{k})) + J (c_{ij} (X_{k})) - 2 J (X_{k}) \leq 0)$ , meaning by Step 3, we can get partial exact solutions (heuristic knowledge), which can improve the search efficiency of the algorithm. Therefore, the HADP algorithm can be employed for dynamic programming equation, and we can obtain the optimal objective value function $J (X, u)$ offline or calculate the approximate optimal objective value function $J_{k} (X, u)$ online by HADP algorithm. Combining with Theorem 2, the optimal scheduling strategy can thus be obtained for KMC.

Simulation experiments and analysis

As mentioned before, the KMC is composed of three agents with three types of jobs $(p_{1}, p_{2}, p_{3})$ ; the processing paths of which are shown in Figure 1. In order to test the sensitivity of the parameters in the proposed algorithm, we consider three values of the Markov discount factor $β$ corresponding to 0.010, 0.015 and 0.020; the demand arrival rates of all kinds of products $λ_{j}$ $(j = 1, 2, 3)$ , as presented in Table 1; and the arrival rates for all blanks $ω_{j}$ $(j = 1, 2, 3)$ and the maximum processing rates ${\bar{μ}}_{i}$ $(i = 1, 2, 3)$ , as listed in Tables 2 and 3, respectively. Table 4 shows the unit processing costs of all machine agents. Tables 5 and 6 give the punishment coefficients of inventory and backlog in buffers, respectively. Set the maximum capacity of the medium buffer to 1 in KMC.

Table 1.

Demand rate $λ_{j}$ of each product.

$λ_{1}$	$λ_{2}$	$λ_{3}$
0.020	0.015	0.010

Table 2.

Arrival rate $ω_{j}$ of each job.

$ω_{1}$	$ω_{2}$	$ω_{3}$
0.015	0.010	0.015

Table 3.

Maximal processing rate ${\bar{μ}}_{i}$ of each agent.

${\bar{μ}}_{1}$	${\bar{μ}}_{2}$	${\bar{μ}}_{3}$
0.090	0.080	0.090

Table 4.

Cost coefficients of processing each agent.

$c_{A g_{1}}$	$c_{A g_{2}}$	$c_{A g_{3}}$
0.85	1.40	0.65

Table 5.

Penalty coefficients of inventory for parts in $b_{k_{i}}^{i}$ and $b_{k_{m}}^{m}$ .

$c_{1, 1}^{i}$	$c_{2, 1}^{i}$	$c_{3, 1}^{i}$	$c_{1, 1}^{m}$	$c_{2, 1}^{m}$	$c_{3, 1}^{m}$
1.15	1.45	1.00	0.90	0.75	1.25

Table 6.

Penalty coefficients of inventory and backlog for finished products in $b_{k_{o}}^{o}$ .

$c_{1, 1}^{+ o}$	$c_{2, 1}^{+ o}$	$c_{3, 1}^{+ o}$	$c_{1, 1}^{- o}$	$c_{2, 1}^{- o}$	$c_{3, 1}^{- o}$
0.45	0.25	0.75	0.95	1.10	0.85

Set the initial state $X_{0} = {(4, 3, 5, 0, 1, 0, - 4, 5, - 3, 0, 0, 0, 0, 0, 1, 0, 0, 0)}^{T}$ for KMC, with Pentium-2.8G personal computer, MATLAB 7 as programming language is used to carry out the simulation experiments and the approximate optimal objective function $J (X)$ is computed online. The iteration steps are set to 180. For $β = 0.015$ , the program runs a total of 0.85 s. Then, we obtain the objective value $J_{N} (X_{0}) = 1164.4$ by the DFSS strategy and the final state $X_{N} = {(0, 0, 4, 0, 0, 0, 3, 5, 8, 0, 1, 0, 0, 0, 0, 0, 0, 0)}^{T}$ . The iterative processes of objective function are illustrated in Figure 4 for $β$ values of 0.010, 0.015 and 0.020, the changing rate of objective functions of which is less than 0.1% when iterative steps are 155, 124 and 108, respectively. To find out whether different initial states have an impact on the DFSS strategy, we set the initial state $X'_{0} = {(3, 8, 9, 0, 1, 0, - 8, - 9, - 5, 0, 0, 0, 0, 0, 0, 0, 0, 0)}^{T}$ . For $β = 0.015$ , KMC starts running from the initial state, and after 180 times of iteration, we get the final state $X'_{N} = {(1, 0, 1, 0, 0, 0, - 7, - 5, 4, 0, 0, 0, 1, 0, 0, 0, 0, 0)}^{T}$ , with the objective function eventually stabilized at 1869.4. The iterative processes are presented in Figure 5 with $β$ of 0.010, 0.015 and 0.020. According to Figures 4 and 5, for different initial states and $β$ , the objective function gradually stabilizes with the increase in step K. The simulation experiments are conducted by DFSS and random control principle for three values of $β$ separately. The latter means when the KMC needs to be controlled, on the premise of no deadlock, one type of jobs is randomly selected for processing. After each of the test problems is solved 12 times, 10 simulative objective function values, the highest and lowest of which are removed to minimize the impact of stochastic factors, are obtained as shown in Table 7. As can be seen from Table 7, the average objective function values by DFSS are 22.72%, 21.79% and 21.18% better than those from the random control principle for $β$ values of 0.010, 0.015 and 0.020, respectively, which confirms the validity and robustness of the DFSS strategy.

Figure 4.

Objective function value of initial state $X_{0}$ .

Figure 5.

Objective function value of initial state $X_{0}^{'}$ .

Table 7.

Objective function values of the two control strategies.

$β$	Scheduling strategy	Objective function value										Average value
		1	2	3	4	5	6	7	8	9	10
0.010	DFSS	1480.8	1648.7	1787.0	1623.9	1680.3	1514.7	1520.9	1754.9	1550.6	1735.9	1629.8
	Rand	1908.2	2202.5	2232.3	2160.4	2187.9	2014.6	2018.4	2153.5	2245.1	1965.9	2108.9
0.015	DFSS	1217.8	1210.9	1134.9	1041.1	1078.5	1253.6	1164.4	1292.2	1166.8	1057.3	1161.3
	Rand	1508.4	1443.5	1524.9	1405.3	1439.6	1504.5	1541.8	1628.7	1402.8	1448.4	1484.8
0.020	DFSS	895.3	803.6	935.7	893.7	962.8	878.8	1046.3	911.9	903.4	851.1	908.3
	Rand	1036.9	1294.2	1172.7	1254.7	1102.2	1043.5	1155.3	1051.4	1167.1	1101.0	1137.9

DFSS: deadlock-free scheduling strategy.

Conclusion

As there are few researches on the integration of deadlock control and production scheduling under stochastic manufacturing environments, in this article, the deadlock-free scheduling problem of KMC composed of multiple machines and products with limited buffers has been studied under the production environment with uncertain job arrival, processing times and product demands. A stochastic dynamic programming model on the expected cost objective function of KMC was established. The properties of optimal value function of the model were obtained by analysis and proof, which has a certain degree of universality. To overcome the curse of dimensionality arising from the combination of discrete state space, a HADP algorithm was proposed to solve the model via simulation and function approximation.

Based on the proposed HADP algorithm, the DFSS for KMC was obtained. The interactions between the automata deadlock supervisor and scheduling decision-maker realized the real-time selection of jobs in buffers and processing rate control, which did help to avoid deadlock state and optimize the performance of KMC simultaneously, thus ensuring its smooth running. And the validity and feasibility of the DFSS were verified by the case study presented in this article.

It should be noted that our study is based on the assumption that the processing time of workpieces follows negative exponential distribution. However, in actual production, the processing time of some types of jobs is sometimes subject to normal distribution. This presents an interesting direction for future research.

Footnotes

Appendix 1 Acknowledgements

We thank the two reviewers and Professor Li Lu for their valuable comments and suggestions.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported in part by the National Natural Science Foundation of China under Grants 60934008, 50875046 and 51005160 and by the High School Natural Science Foundation of Jiangsu Province under Grant 13KJB460005.

References

Gunasekaran

Agile manufacturing: enablers and an implementation framework. Int J Prod Res 1998; 36: 1223–1247.

Selladurai

RS.

Mass customization in operations management: oxymoron or reality?

Omega 2004; 32: 295–300.

Aulakh

Gill

JS.

Lean manufacturing—a practitioner’s perspective. In: Proceedings of IEEE international conference on industrial engineering and engineering management, Singapore, 8–11 December 2008, pp.1184–1188. Piscataway: IEEE Computer Society.

Maropoulos

Bramall

Chapman

. Digital enterprise technology in production networks. Int J Adv Manuf Tech 2006; 30: 911–916.

Yan

Liu

Knowledgeable manufacturing system—a new kind of advanced manufacturing system. Comput Integr Manuf 2001; 7: 7–11 (in Chinese).

Yan

HS.

A new complicated-knowledge representation approach based on knowledge meshes. IEEE T Knowl Data En 2006; 18: 47–62.

Jolai

Sangari

Babaie

Pareto simulated annealing and colonial competitive algorithm to solve an offline scheduling problem with rejection. Proc IMechE, Part B: J Engineering Manufacture 2010; 224: 1119–1131.

Yang

Geunes

O’Brien

WJ.

A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling. Comput Oper Res 2004; 31: 1273–1301.

Yang

Geunes

A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Comput Ind Eng 2007; 53: 420–432.

10.

Briskorn

Jaehn

Pesch

Exact algorithms for inventory constrained scheduling on a single machine. J Sched 2013; 16: 105–115.

11.

Pesch

Sterna

Late work minimization in flow shops by a genetic algorithm. Comput Ind Eng 2009; 57: 1202–1209.

12.

Kim

Lee

DH.

Heuristic algorithms for re-entrant hybrid flow shop scheduling with unrelated parallel machines. Proc IMechE, Part B: J Engineering Manufacture 2009; 223: 433–442.

13.

Akella

Kumar

PR.

Optimal control of production rate in a failure-prone manufacturing system. IEEE T Automat Contr 1986; 31: 116–126.

14.

Kenne

Gharbi

A simulation optimization based control policy for failure prone one-machine, two-product manufacturing systems. Comput Ind Eng 2004; 46: 285–292.

15.

Liefooghe

Basseur

Humeau

. On optimizing a bi-objective flowshop scheduling problem in an uncertain environment. Comput Math Appl 2012; 64: 3747–3762.

16.

Luh

Chen

Thakur

LS.

An effective approach for job-shop scheduling with uncertain processing requirements. IEEE T Robotic Autom 1999; 15: 328–339.

17.

Boukas

Liu

ZK.

Production and maintenance control for manufacturing systems. IEEE T Automat Contr 2001; 46: 1455–1460.

18.

Ullah

Liu

Zhang

. Scheduling with uncertain processing times: applying β-robust scheduling on two-machine flow-shop with constraints. In: Proceedings of IEEE international conference on industrial engineering and engineering management, Hong Kong, 8–11 December 2009, pp.1946–1950. New York: IEEE.

19.

Xia

Chen

Yue

JF.

Job sequencing and due date assignment in a single machine shop with uncertain processing times. Eur J Oper Res 2008; 184: 63–75.

20.

Yang

Geunes

Predictive–reactive scheduling on a single resource with uncertain future jobs. Eur J Oper Res 2008; 189: 1267–1283.

21.

Sethi

Zhang

Hierarchical production control in a stochastic N-machine flow shop with limited buffers. J Math Anal Appl 2000; 246: 28–57.

22.

Kouvelis

Daniels

Vairaktarakis

Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans 2000; 32: 421–432.

23.

Park

Kim

Lee

Ubiquitous software controller to prevent deadlocks for automated guided vehicles systems in a container port terminal environment. J Intell Manuf 2009; 20: 321–325.

24.

Yoon

HJ.

Scheduling for deadlock avoidance operation in robotic manufacturing cells. Proc IMechE, Part B: J Engineering Manufacture 2010; 224: 329–340.

25.

Kobetski

Fabian

Time-optimal coordination of flexible manufacturing systems using deterministic finite automata and mixed integer linear programming. Discrete Event Dyn S 2009; 19: 287–315.

26.

Fanti

Zhou

MC.

Deadlock control methods in automated manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 5–21.

27.

Yang

Yan

HS.

A deadlock avoidance strategy for knowledgeable manufacturing systems. Proc IMechE, Part B: J Engineering Manufacture 2009; 223: 195–205.

28.

Moody

Antsaklis

PJ.

Petri net supervisors for DES with uncontrollable and unobservable transitions. IEEE T Automat Contr 2000; 45: 462–476.

29.

Fahmy

Balakrishnan

Elmekkawy

A generic deadlock-free reactive scheduling approach. Int J Prod Res 2009; 47: 5657–5676.

30.

Yoon

Lee

DY.

Deadlock-free scheduling of photolithography equipment in semiconductor fabrication. IEEE T Semiconduct M 2004; 17: 42–54.

31.

Abdallah

Elmaraghy

Elmekkawy

Deadlock-free scheduling in flexible manufacturing systems using Petri nets. Int J Prod Res 2002; 40: 2733–2756.

32.

Zhou

MC.

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets. OR Spectrum 2007; 29: 421–443.

33.

Golmakani

Mills

Benhabib

Deadlock-free scheduling and control of flexible manufacturing cells using automata theory. IEEE T Syst Man Cy A 2006; 36: 327–337.

34.

Ramirez-Serrano

Zhu

Benhabib

Moore automata for the supervisory control of robotic manufacturing workcells. Auton Robot 2009; 9: 59–69.

35.

Ramage

PJG

Wonham

. Supervisory control of a class of discrete event systems. SIAM J Control Optim 1987; 25: 206–230.

36.

Bertsekas

DP.

Dynamic programming: deterministic and stochastic models. Englewood Cliffs, NJ: Prentice Hall, 1987.

37.

De Farias

Van

. The linear programming approach to approximate dynamic programming. Oper Res 2003; 51: 850–865.

38.

Lee

JM.

Approximate dynamic programming based approach to process control and scheduling. Comput Chem Eng 2006; 30: 1603–1618.

Deadlock-free scheduling of knowledgeable manufacturing cell with multiple machines and products

Abstract

Keywords

Introduction

Problem formulation and objective function

Problem formulation

Objective function

KMC deadlock supervisor

KMC scheduling strategy

Discretization of objective function

Property analysis of objective function

Theorem 1

Proof

Theorem 2

Proof

Definition 1

Lemma 1

Proof

Lemma 2

Proof

Lemma 3

Proof

Theorem 3

Proof

Theorem 4

Proof

Scheduling strategy of KMC

Simulation experiments and analysis

Conclusion

Footnotes

Appendix 1

Acknowledgements

Declaration of Conflicting Interests

Funding

References