Performance optimization for a class of generalized stochastic Petri nets

Motivated by the current scheduling needs of complex resource allocation systems, this paper introduces a novel methodology for performance optimization in DES applications that evolve over very large and complex state spaces and the main objective is expressed as the long-run maximization of some reward rate. The proposed methodology leverages the Generalized Stochastic Petri Net (GSPN) modeling framework in order to effect the seamless integration of the logical and performance-oriented control of the aforementioned applications, define a pertinent policy space, and (re-)cast the performance optimization problem into a mathematical programming formulation that is eventually solved through sensitivity analysis of Markov reward processes and stochastic approximation algorithms. An important attribute of the proposed methodology is that it facilitates an explicit control of the existing trade-off between the computational tractability of the employed formulation and the performance of the derived policies. Furthermore, by posing the eventually defined problem as a constrained nonlinear programming formulation, the presented methodology inherits all the analytical tools and insights that are offered by that vast area of optimization theory. In the current manuscript, all these possibilities are demonstrated through the application of the proposed approach to the throughput maximization of a capacitated re-entrant line abstracting the operation of an automated manufacturing cell.

1. Also, we should notice, for completeness, that according to standard PN notation, the other three elements in the net-defining tuple are the place set P, the flow relation W that defines the connectivity of the net, and the net initial marking m ₀.

2. As remarked in Section 2, the restriction of the GSPN timed dynamics to Markovian behavior does not restrict substantially its modeling power, since (i) more generally distributed firing times can be approximated to any desired degree of accuracy by phase-type distributions, and (ii) the latter can be modeled by appropriately structured GSPN subnets (Cassandras and Lafortune 2008).

3. For notational economy, in the following we shall use \(\mathcal {N}\) to refer to the controlled net, as well.

4. Besides its mathematical necessity for the well-posedness of the proposed optimization problem, the randomization in the decision-making process introduced by δ will also be a useful “exploration” mechanism in the solution of the proposed formulation through the sample-path-based techniques that are pursued in this work.

5. On the other hand, random switches that depend also on the marking m are characterized as dynamic.

6. The last remarks are further exemplified through the case study that is presented in Section 6.

7. The reader should also notice that the “unfolding” nature of the construction of \(\mathcal {G}_{v}(\mathcal {N}; m)\) implies that it is possible that \(m\in \bar {M}\). In fact, this will be the case for the “fictitious” transitions in \(\mathcal {U}(\mathcal {N})\) that are introduced by the uniformization.

8. However, this increase can take place in an arbitrarily slow rate.

9. Thus, the characterization “capacitated re-entrant line”.

10. As already mentioned, more general distributions can be effectively approximated by phase-type distributions (Cassandras and Lafortune 2008). Hence, the restriction of this example to exponentially distributed processing times does not compromise its generality. We also notice that the cluster tools that are used in the contemporary semiconductor manufacturing industry are miniaturized versions of the robotic cells that are considered in this example (Singer 1995; Weiss 1996).

11. More formally, from the standpoint of the PN-based supervisory control theory, P _SCP is a “monitor” place that enforces the aforementioned inequality by introducing an appropriate p-semiflow in the net dynamics (Giua et al. 1992). The theory of imposing constraints on the PN behavior that are expressed as linear inequalities in the net marking, is pretty well developed (Moody and Antsaklis 1998; Iordache and Antsaklis 2006), and in the particular context of the liveness-enforcing supervision of complex RAS, it can support the implementation of the maximally permissive LES or of some pretty tight approximations of that policy Reveliotis (2005, 2007).

12. We should also notice, for completeness, that the optimal scheduling policy for capacitated re-entrant lines might involve deliberate idleness. The possibility of modeling such deliberate idleness in the GSPN framework has been demonstrated in Choi and Reveliotis (2003). In this work, we have opted to ignore this behavioral element in order to maintain the presentational tractability of the considered example. Furthermore, it can be verified that for the considered example, the optimal scheduling policy does not involve any deliberate idleness.

13. We opted for a fairly large N ₁, especially when compared to N ₂, since (i) the analysis of Section 5 has revealed the criticality of the size of N ₁ for controlling the bias in the observations Y _n w.r.t. the actual direction of the gradient \(\nabla _{\bar {\xi }}(\bar {\xi }_{n})\), and furthermore, (ii) the computational cost of the replications that provide the throughput estimates are significantly lower than the computational cost of the replications that provide the Y _n -values.

This work was partially supported by NSF grant CMMI-0928231.

Authors and Affiliations

1. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA

   Ran Li & Spyros Reveliotis

Corresponding author

Correspondence to Spyros Reveliotis.

Appendix: The generic SA algorithm that is employed in this work

Consider the recursion

that is further specified by the following assumptions:

1. I.

   {Y _n } is a stochastic process such that E _n [Y _n ]≡E[Y _n |𝜃 ₀, Y _i , i< n]=∇ _𝜃 g(𝜃 _n ) + β _n where g(⋅) is a continuously differentiable real-valued function, and β _n → 0 w.p. 1.

2. II.

   supnE[|Y _n |²] < ∞.

3. III.

   \(\epsilon _{n} \geq 0;\ \epsilon _{n} \rightarrow 0;\ \sum _{n=0}^{\infty } \epsilon _{n} = \infty ;\ \sum _{n=0}^{\infty } {\epsilon _{n}^{2}} < \infty\).

4. IV.

   H ≡ {𝜃:ψ _i (𝜃) ≤ 0, i = 1, …, c}, where ψ _i (⋅), i = 1, …, c, are continuously differentiable real-valued functions. It is further assumed that ∀i, ∇ _𝜃 ψ _i (𝜃) ≠ 0 if ψ _i (𝜃) = 0. Furthermore, the set H is assumed to be connected, compact and non-empty. Finally, the operator π _H [⋅] projects any given 𝜃 upon the set H, i.e., it returns a point 𝜃′ ∈ H such that 𝜃′ ∈ argmin{|𝜃−𝜃″|²: 𝜃″ ∈ H} and the considered norm is the Euclidean norm.

It is clear from the above description that the sequence {𝜃 _n } generated by the recursion of Eq. 21 is constrained to evolve in H. For any point 𝜃 ∈ H, let A(𝜃) = {i:ψ _i (𝜃) = 0}. The set A(𝜃) is the set of the active constraints at 𝜃. Furthermore, consider the set Ω(𝜃) = {∇ _𝜃 ψ _i (𝜃):i ∈ A(𝜃)}, i.e., the set containing the outward normals of the active constraints at 𝜃, and let C(𝜃) denote the convex cone that is generated by the elements of Ω(𝜃). For the particular case where A(𝜃) = ∅, C(𝜃) will contain only the zero element. On the other hand, for A(𝜃) ≠ ∅, and under the further assumption that the elements of Ω(𝜃) are linearly independent, the recursion of Eq. 21 can be rewritten as follows:

where Z _n is a vector belonging in −C(𝜃 _n+1). Finally, let

We shall refer to S _H as the (set containing the) “stationary” points of H. S _H can be divided into disjoint compact and connected subsets S _j , j = 0, … The next theorem characterizes the limiting behavior of the recursion of Eq. 21 under the further structure that is defined in the above discussion.

Theorem 2

(Kushner and Yin 2003 ) Consider the recursion of Eq. 21 under Assumptions I-IV, and further suppose that the underlying function g(⋅) is constant on each subset S _i of the set S _H . Then, the sequence {𝜃 _n } that is generated by this recursion converges to a unique subset S _i w.p. 1.

Reprints and permissions