Optimal Control Problems in a Class of Queueing Systems
Abstract Generated abstract
This paper formulates an optimal control approach for a class of queueing systems in which the service discipline is selected according to an unobserved random parameter of the request flow. Using monitored auxiliary data, conditional probabilities are computed and statistical simulation is used to estimate the expected value of a service-quality criterion for each admissible operating mode, with the mode chosen by minimizing this expectation. The paper derives a multinomial decision framework for identifying the relevant parameter region from repeated observations, gives a simplified binomial solution for two modes including a confidence-based minimum sample size, and discusses the reliability of control when the parameter region changes over time. It also proposes an expression for evaluating control effectiveness as a function of the observation interval and the frequency of changes in the request-flow parameter.
Full Text
PROCEEDINGS
of the Tomsk Order of the October Revolution
and Order of the Red Banner of Labor
Polytechnic Institute named after S. M. Kirov
Vol. 290 1974
OPTIMAL CONTROL ISSUES IN A CLASS OF QUEUEING SYSTEMS
L. V. PERFIL'EV
(Presented by the scientific and technical seminar of the Department of Automated Control Systems
and the Control Laboratory)
The use of control of the service discipline in queueing systems substantially increases the efficiency of their operation. The variety of existing systems and methods for controlling them largely determines the possibility and effectiveness of implementing optimal control in queueing systems belonging to a certain type. This paper considers one of the possible approaches to solving the problem of optimal control of a disordered queueing system with a random flow of requests, belonging to a certain class of systems. In such a system the service discipline is determined by technological requirements formulated by operating practice. The quality indicators of system operation are calculated by the method of statistical simulation, which makes it possible to take into account all imposed constraints [1]. Depending on the value of the random variable \(b\)—some parameter of the request flow, taking its values from a continuous domain \(B\)—a certain service discipline \(R_j,\ j = 1, 2, \ldots, n\), called the \(R\)-mode of system operation, is established. Consequently, to each value \(R_j\) there corresponds a certain region \(B_j \subset B\) of values of \(b\). If the value \(b\) lies in the region \(B_j\), this means that the system must be switched to the operating mode \(R_j\).
The probability that \(b\) lies in the region \(B_j\) is computed on the basis of monitoring some continuous parameter \(\gamma \in \Gamma\) by the expression
\[ P(B_j;\gamma)=\int_{B_j} p(b;\gamma)\,db, \tag{1} \]
where \(P(B_j;\gamma)\) is the conditional probability;
\(P(b;\gamma)\) is the conditional probability density of the parameter \(b\).
From the results of measuring the quantity \(\gamma\), using a model of the system operation process, the values \(P(b/\gamma)\) can be computed, and then the values \(M(\Phi)\), the mathematical expectation of \(\Phi\)—the service-quality indicator—for each \(R_j\).
In this case the operating mode \(R\) is assigned such a value \(R_j\) at which the minimum of \(M(\Phi)\) is attained. For each value of \(\gamma\) and \(R_j\), a certain quantity \(U_\gamma\) is computed as follows: \(U_\gamma = 1\) if the minimum of \(M(\Phi)\) occurs under the mode \(R_j\), and \(U_\gamma = 0\) otherwise.
As a result of \(\kappa\) measurements, the value \(m_j\) is recorded—the number of times when \(R=R_j\). The frequencies \(m_j\) \((j=1,n)\) are realizations of dependent random integer-valued quantities that have the joint distribution (2)
\[ P(m_j/B_i)=\frac{\kappa!}{\prod_{j=1}^{n} m_j!}\prod_{j=1}^{n}[P(R_j/B_i)]^{m_j} \tag{2} \]
\[ i=1,2,\ldots,n;\quad j=1,2,\ldots,n;\quad B_i=B_j \]
\[ \sum_{j=1}^{n} m_j=\kappa;\quad m_j\geqslant 0, \]
where \(P(R_j/B_i)\) is the probability of assigning the value \(R_j\) to the operating regime \(R\), under the condition that the values of the parameter \(b\) lie in the region \(B_i\). Below are the expressions by which the indicated probability is calculated.
\[ P(R_j/B_i)=\int P(\gamma/B_i)\cdot U_\gamma\,d\gamma; \tag{3} \]
\[ P(\gamma/B_j)=\frac{P(\gamma)\cdot P(B_j/\gamma)}{\int P(\gamma)\cdot P(B_j/\gamma)\,d\gamma}; \tag{4} \]
\[ P(B_j/\gamma)=\int_{b_j} P(b/\gamma)\,db. \tag{5} \]
\[ U_\gamma \begin{cases} =1, & \text{if } M(\Phi)=\min,\ \text{when } R=R_j;\\ =0, & \text{if } M(\Phi)=\min,\ \text{when } R\ne R_j. \end{cases} \]
In principle, distribution (2) makes it possible to determine the regions of sample values of the vector \(\vec m_j\) for all values of \(B_i\).
Taking into account the fact that, for the queueing system under consideration, the regions \(B_i\) do not intersect, the problem of deciding which value \(B_i\) is true can be formulated as follows: determine, with a prescribed confidence probability \(\alpha\), such a minimal value of the sample size \(\kappa\) for which the regions of sample values for different \(B_i\) do not intersect; in this case the true \(B_i\) will be the one into whose region the sample falls.
For the case when \(j=1,2\), the problem under consideration has a relatively simple solution. Expression (2) is rewritten in the form
\[ P(m/B_i)=C_\kappa^m [P(R_1/B_i)]^m [1-P(R_1/B_i)]^{\kappa-m}, \tag{6} \]
\[ j=1,2;\quad i=1,2;\quad m_1=m;\quad m_2=\kappa-m. \]
For a given sample size \(\kappa\) and confidence probability \(\alpha\), a confidence region of sample values can be constructed—this is a region within which the value of the probability \(P=P(R_j/B_i)\) is compatible with the sample value \(P^*=\dfrac{m_i}{\kappa}\) for the corresponding \(B_i\).
The curves bounding the confidence region are determined by the known equations [2]
\[ \sum_{m=\kappa p}^{\kappa} C_\kappa^m p^m(1-p)^{\kappa-m}=\frac{q}{2}, \tag{7} \]
\[ \sum_{m=j}^{np^*} C_k^m p^m (1-p)^{k-m}=\frac{q}{2}, \tag{8} \]
where \(q=1-x\).
For given values of \(\kappa\) and \(P\), these curves determine the smallest and largest values of \(P^*\). Then it is not difficult to find such a minimal \(\kappa=\kappa_{\min}\) for which the intervals of values of \(P^*\) for \(B_1\) and \(B_2\) would not overlap.
On the basis of the foregoing, the decision-making procedure is as follows. A sample of size \(\kappa_{\min}\) is taken. In this case, if the sample value \(\frac{m}{n}\) falls into the interval of sample values \(P^*\) corresponding to \(B_1\), then \(B_1\) is the true one; otherwise \(B_2\) is the true one. Sample values that do not fall into either interval are assigned to the nearest of them.
It should be noted that the problem under study can be solved in the case when, during the observation, the values of \(b\)—the parameter of the demand flow—lie in one of the regions \(B_j\).
In the case when this requirement is not fulfilled, effective control can be achieved only under the condition that the time interval after which the values \(B_i\) change is, on average, much longer than the observation interval.
In this case the mathematical expectation of the service-quality index takes the maximum value \(M(\Phi)_{\max}\) if, throughout the entire operating time of the system, the values \(R_j\) and \(B_j\) are in correspondence, and takes the minimum value \(M(\Phi)_{\min}\) if \(R_j\) and \(B_j\) never correspond. When control is used, a mismatch between \(R_j\) and \(B_j\) may exist for no more than \(\rho=2\) observation intervals. This is, first of all, the interval in which the change of \(B_j\) occurred, and also the one following it, since there is the possibility of an erroneous decision based on the observation results of the preceding interval. However, taking into account that the change in the value of \(B_j\) in the first interval occurs not only at the beginning of the interval and, consequently, during a certain part \(\kappa\) of it there is correspondence with \(B_j\), it is advisable to take \(\rho=1.5\).
Below is an expression that makes it possible to compute the effectiveness of control \(\Pi_j\) for a given value of \(\pi\)—the ratio of the length of the observation interval to the time interval after which \(B_j\) changes:
\[ \Pi_j=\rho\pi\left[M_{jj}(\Phi)\cdot P(B_j)+\sum_{\psi} M_{j\psi}(\Phi)\cdot P(B_\psi)\right]+ \tag{9} \]
\[ +(1-\rho\pi)\sum_j M_{jj}(\Phi)\cdot P(B_j) \]
\[ j=\overline{1,n};\quad \psi=\overline{1,n};\quad \psi\ne j, \]
where \(M_{jj}(\Phi)\) is the mathematical expectation of the service-quality index when the system is in mode \(R_j\) and the value of the parameter \(b\) is in the region \(B_j\); and \(M_{j\psi}(\Phi)\) is when the system is in mode \(R_j\) and \(b\) is in the region \(B_\psi\), \(P(B_j)\) is the probability of the value \(B_j\).
REFERENCES
- L. V. Perfil’ev. Algorithm for modeling one class of mass-service systems. Izvestiya TPI, vol. 211, Tomsk, 1970.
- E. S. Venttsel. Probability Theory. Moscow, “Nauka,” 1964.