Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Adaptive control of constrained Markov chains: Criteria and policies (1991)
    Springer
    Annals of operations research 28 (1991), S. 101-134 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We consider the constrained optimization of a finite-state, finite action Markov chain. In the adaptive problem, the transition probabilities are assumed to be unknown, and no prior distribution on their values is given. We consider constrained optimization problems in terms of several cost criteria which are asymptotic in nature. For these criteria we show that it is possible to achieve the same optimal cost as in the non-adaptive case. We first formulate a constrained optimization problem under each of the cost criteria and establish the existence of optimal stationary policies. Since the adaptive problem is inherently non-stationary, we suggest a class ofAsymptotically Stationary (AS) policies, and show that, under each of the cost criteria, the costs of an AS policy depend only on its limiting behavior. This property implies that there exist optimal AS policies. A method for generating adaptive policies is then suggested, which leads to strongly consistent estimators for the unknown transition probabilities. A way to guarantee that these policies are also optimal is to couple them with the adaptive algorithm of [3]. This leads to optimal policies for each of the adaptive constrained optimization problems under discussion.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02055577
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Zero-sum Markov games and worst-case optimal control of queueing systems (1995)
    Springer
    Queueing systems 21 (1995), S. 415-447 
    Details
    ISSN: 1572-9443
    Keywords: Zero-sum stochastic games ; discounted and expected average cost ; worst case control of queueing networks ; value iteration ; structural properties of optimal policies and value function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by “nature” (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control of queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, we extend some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01149169
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Sensitivity of constrained Markov decision processes (1991)
    Springer
    Annals of operations research 32 (1991), S. 1-22 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We consider the optimization of finite-state, finite-action Markov decision processes under constraints. Costs and constraints are of the discounted or average type, and possibly finite-horizon. We investigate the sensitivity of the optimal cost and optimal policy to changes in various parameters. We relate several optimization problems to a generic linear program, through which we investigate sensitivity issues. We establish conditions for the continuity of the optimal value in the discount factor. In particular, the optimal value and optimal policy for the expected average cost are obtained as limits of the dicounted case, as the discount factor goes to one. This generalizes a well-known result for the unconstrained case. We also establish the continuity in the discount factor for certain non-stationary policies. We then discuss the sensitivity of optimal policies and optimal values to small changes in the transition matrix and in the instantaneous cost functions. The importance of the last two results is related to the performance of adaptive policies for constrained MDP under various cost criteria [3,5]. Finally, we establish the convergence of the optimal value for the discounted constrained finite horizon problem to the optimal value of the corresponding infinite horizon problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02204825
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Polling systems with synchronization constraints (1992)
    Springer
    Annals of operations research 35 (1992), S. 231-267 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We introduce a new service discipline, called thesynchronized gated discipline, for polling systems. It arises when there are precedence (or synchronization) constraints between the order that jobs in different qucues should be served. These constraints are described as follows: There areN stations which are “fathers” of (zero or more)synchronized stations (“children”). Jobs that arrive at synchronized stations have to be processed only after jobs that arrived prior to them at their corresponding “father” station have been processed. We analyze the performance of the synchronized gated discipline and obtain expressions for the first two moments and the Laplace-Stieltjes transform (LST) of the waiting times in different stations, and expressions for the moments and LST of other quantities of interest, such as cycle duration and generalized station times. We also obtain a “pscudo” conservation law for the synchronized gated discipline, and determine the optimal network topology that minimizes the weighted sum of the mean waiting times, as defined in the “pseudo” conservation law. Numerical examples are given for illustrating the dependence of the performance of the synchronized gated discipline on different parameters of the network.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02188706
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed information (1995)
    Springer
    Queueing systems 21 (1995), S. 267-291 
    Details
    ISSN: 1572-9443
    Keywords: Markov decision processes ; monotone policies ; delayed information and actions ; submodularity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a discrete-time Markov decision process with a partially ordered state space and two feasible control actions in each state. Our goal is to find general conditions, which are satisfied in a broad class of applications to control of queues, under which an optimal control policy is monotonic. An advantage of our approach is that it easily extends to problems with both information and action delays, which are common in applications to high-speed communication networks, among others. The transition probabilities are stochastically monotone and the one-stage reward submodular. We further assume that transitions from different states are coupled, in the sense that the state after a transition is distributed as a deterministic function of the current state and two random variables, one of which is controllable and the other uncontrollable. Finally, we make a monotonicity assumption about the sample-path effect of a pairwise switch of the actions in consecutive stages. Using induction on the horizon length, we demonstrate that optimal policies for the finite- and infinite-horizon discounted problems are monotonic. We apply these results to a single queueing facility with control of arrivals and/or services, under very general conditions. In this case, our results imply that an optimal control policy has threshold form. Finally, we show how monotonicity of an optimal policy extends in a natural way to problems with information and/or action delay, including delays of more than one time unit. Specifically, we show that, if a problem without delay satisfies our sufficient conditions for monotonicity of an optimal policy, then the same problem with information and/or action delay also has monotonic (e.g., threshold) optimal policies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01149165
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Optimal Open-Loop Control of Vacations, Polling and Service Assignment (2000)
    Springer
    Queueing systems 36 (2000), S. 303-325 
    Details
    ISSN: 1572-9443
    Keywords: multimodular functions ; balanced sequences ; control of vacations ; polling ; service assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider in this paper the optimal open-loop control of vacations in queueing systems. The controller has to take actions without state information. We first consider the case of a single queue, in which the question is when should vacations be taken so as to minimize, in some general sense, workloads and waiting times. We then consider the case of several queues, in which service of one queue constitutes a vacation for others. This is the optimal polling problem. We solve both problems using new techniques from [2,4] based on multimodularity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1011085302786
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    On Elevator polling with globally gated regime (1992)
    Springer
    Queueing systems 11 (1992), S. 85-90 
    Details
    ISSN: 1572-9443
    Keywords: Polling ; globally gating ; Elevator policy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a polling system consisting ofN queues and a single server where polling is performed according to anElevator (scan) scheme. The server first serves queues in the “up” direction, i.e. in the order 1, 2,...,N − 1,N, and then serves these queues in the opposite (“down”) direction, i.e. visiting them in the orderN,N−1,...,2,1. The server then changes direction again, and so on. A globally gating regime is used each time the server changes direction. We show that, for this Elevator scheme,the expected waiting times in all channels are equal. This is the only known non-symmetric polling system that exhibits such afairness phenomenon. We then discuss the problem of optimally ordering the queues so as to minimize some measure of variability of the waiting times.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01159288
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Stability, monotonicity and invariant quantities in general polling systems (1992)
    Springer
    Queueing systems 11 (1992), S. 35-57 
    Details
    ISSN: 1572-9443
    Keywords: Polling system ; stability condition ; monotonicity ; stochastic comparison ; invariant quantities
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Consider a polling system withK≥1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01159286
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On the stability of retrial queues (1997)
    Springer
    Queueing systems 26 (1997), S. 343-363 
    Details
    ISSN: 1572-9443
    Keywords: retrial queues ; stability ; ergodicity ; renovation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ 〉 λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019193527040
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Analysis of TCP Vegas and TCP Reno (2000)
    Springer
    Telecommunication systems 15 (2000), S. 381-404 
    Details
    ISSN: 1572-9451
    Source: Springer Online Journal Archives 1860-2000
    Topics: Electrical Engineering, Measurement and Control Technology
    Notes: Abstract In this paper we use an analytic fluid approach in order to analyze the different features of both Vegas and Reno TCP versions. We then use simulations to confirm our analytic results. When the available bandwidth is high, indeed Vegas can retransmit less than one‐fifth as much data as Reno does, so that the higher the available bandwidth is, the more efficient Vegas is. However, under heavy congestion Vegas behaves like Reno and does not manage to make efficient use of its new mechanism for congestion detection. The analytic results that we obtain are the evolution of the window size, round trip times and their averages, and the average throughput.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019159332202
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...