ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    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
    Schlagwort(e): Markov decision processes ; monotone policies ; delayed information and actions ; submodularity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01149165
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Non zero-sum stochastic games in admission, service and routing control in queueing systems (1996)
    Springer
    Queueing systems 23 (1996), S. 259-279 
    Details
    ISSN: 1572-9443
    Schlagwort(e): Non zero-sum stochastic games ; control of queueing networks ; admission control ; service control ; routing control
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: Abstract The purpose of this paper is to investigate situations of non-cooperative dynamic control of queueing systems by two agents, having different objectives. The main part of the paper is devoted to analyzing a problem of an admission and a service (vacation) control. The admission controller has to decide whether to allow arrivals to occur. Once the queue empties, the server goes on vacation, and controls the vacations duration (according to the state and past history of the queue). The immediate costs for each controller are increasing in the number of customers, but no convexity assumptions are made. The controllers are shown to have a stationary equilibrium policy pair, for which each controller uses a stationary threshold type policy with randomization in at most one state. We then investigate a problem of a non-zero sum stochastic game between a router into several queues, and a second controller that allocates some extra service capacity to one of the queues. We establish the equilibrium of a policy pair for which the router uses the intuitive “Join the shortest queue” policy.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01206560
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    On the stability of retrial queues (1997)
    Springer
    Queueing systems 26 (1997), S. 343-363 
    Details
    ISSN: 1572-9443
    Schlagwort(e): retrial queues ; stability ; ergodicity ; renovation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1019193527040
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Adaptive control of constrained Markov chains: Criteria and policies (1991)
    Springer
    Annals of operations research 28 (1991), S. 101-134 
    Details
    ISSN: 1572-9338
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02055577
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    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
    Schlagwort(e): 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
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01149169
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    Sensitivity of constrained Markov decision processes (1991)
    Springer
    Annals of operations research 32 (1991), S. 1-22 
    Details
    ISSN: 1572-9338
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02204825
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Polling systems with synchronization constraints (1992)
    Springer
    Annals of operations research 35 (1992), S. 231-267 
    Details
    ISSN: 1572-9338
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02188706
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Digitale Medien
    Digitale Medien
    Discrete time queues with delayed information (1995)
    Springer
    Queueing systems 19 (1995), S. 361-376 
    Details
    ISSN: 1572-9443
    Schlagwort(e): Discrete time queues ; delayed information
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: Abstract We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thecμ rule remains optimal even in the case of delayed information.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01151929
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 9
    Digitale Medien
    Digitale Medien
    Optimal Open-Loop Control of Vacations, Polling and Service Assignment (2000)
    Springer
    Queueing systems 36 (2000), S. 303-325 
    Details
    ISSN: 1572-9443
    Schlagwort(e): multimodular functions ; balanced sequences ; control of vacations ; polling ; service assignment
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1011085302786
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 10
    Digitale Medien
    Digitale Medien
    Stability, monotonicity and invariant quantities in general polling systems (1992)
    Springer
    Queueing systems 11 (1992), S. 35-57 
    Details
    ISSN: 1572-9443
    Schlagwort(e): Polling system ; stability condition ; monotonicity ; stochastic comparison ; invariant quantities
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01159286
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...