liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On some Control Problems for Queues
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
1982 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

This thesis consists of three parts. In the first one, optimal policies are constructed for some singe-line queueing situations. The second part deals with finite-state Markovian decision processes, and in the third part the practical modelling of a more complex problem is discussed and exemplified.

The central control object of part I is an M!M/1 queue with fixed arrival rate and controllable service rate. The objective is to minimize the expected long-run average of a cost rate, which isa sum of two functions, associated with the queue length (the holding cost) and the service rate (the service cost), respectively. For the case of a fin ite waiting-room, terminal costs are constructed, such that a solution to the associated dynamic programming (Bellman) equation exists, which is affine in the time parameter. The corresponding optimal control is independent of both time and the length of the control interval. It hasa form which is subsequently used in generali zing into the case of an infinite waiting room. For this case, the analysis res ults in an efficient algorithm, and in several structural results. Assuming essentially only that the holding cost is increasing, it is proved that a monotone optimal policy exists, i.e. that the optimal choice of service rate is an in creasing function of the present queue length. Three variations of the ce ntral problem are also treated in part I. These are the M/M/c problem (for which the above monotonicity result holds only under a stronger condition), the problem of a controllable ar rival rate (with fixed service rate), and the discounted cost problem.

In part II, finite-state Markovian decision processes are discussed. A brief and heuristic introduction is given, regarding continuous-time Markov chains, cost structures on these, and the problem of constructing an optimal poli cy. The purpose is to point out the relations to the queueing control problem with finite waiting-room. Counterexamples demonstrate that the approach of part I is not universally applicable.

In part 111, a simplified mode! is discussed for a situation where th e customers may reenter the queue after a stochastic delay. It is argued that under heavy-traffic conditions, the influx of reentering customers can be approximated with the output of a linear stochastic system with state-dependent Gaussian noise, whose dynamics depend on the delay distribution. This idea is exemplified with the res ults from a simulated experiment on a telephone station.

Place, publisher, year, edition, pages
Linköping: Linköping University , 1982. , 225 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 87
Keyword [en]
Queues, Control problems
National Category
Control Engineering
URN: urn:nbn:se:liu:diva-102244ISBN: 91-7372-593-5OAI: diva2:675601
Public defence
1982-12-16, C3, Hus C, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Available from: 2013-12-05 Created: 2013-12-04 Last updated: 2014-01-08Bibliographically approved

Open Access in DiVA

No full text

By organisation
Automatic ControlThe Institute of Technology
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 90 hits
ReferencesLink to record
Permanent link

Direct link