Self-optimizing stochastic systems: Applications to stochastic shortest path problem, stochastic traveling salesman problem, and queueing systems.

Persistent Link:
http://hdl.handle.net/10150/185025
Title:
Self-optimizing stochastic systems: Applications to stochastic shortest path problem, stochastic traveling salesman problem, and queueing systems.
Author:
Jayawardena, Thusitha Senadirage.
Issue Date:
1990
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
We investigate stochastic systems which have a set of control parameters and a performance criterion. By operating the system at fixed control parameters, noisy performance values are observed. (The values are noisy due to the inherent stochastic nature of the system.) Certain relevant distributions of the system are assumed unavailable. The task is to develop algorithms that guide the system to optimal parameter settings based on its operating history. Consider the stochastic shortest path problem, where the time to traverse an edge is given by a random variable whose distribution is unavailable explicitly. The optimality criterion (to be maximized) is the probability of going from a given source node to a given terminal node within a specified critical time period. By choosing a particular path and traversing it, realizations of the distributions, i.e. time to go from the source node to the terminal node on that path are observed. Or consider the M/M/1 queue. Here, the control parameter is the average service time. The performance criterion is the sum of cost of the server and cost of system time of a customer in steady-state. By choosing a particular average service time and serving accordingly, a noisy observation of the total cost is obtained. We combine an asymptotically optimal random search method for finding the global optimum of a function with problem-specific local search techniques. Such a combination results in efficient solution procedures for the above problems. This conclusion is reached by applying the procedure to problems for which the optimum solutions are known. The main contribution of the study is in demonstrating that "reasonable" performance can be achieved for the proposed optimization problems in "reasonable" time by exploiting problem-specific structures to advantage. The generality of the method should allow others to use it in different optimization settings than ours. Also, the self-optimizing aspect of these methods and the stochastic versions of the local search techniques are new.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Systems and Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Yakowitz, Sidney

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleSelf-optimizing stochastic systems: Applications to stochastic shortest path problem, stochastic traveling salesman problem, and queueing systems.en_US
dc.creatorJayawardena, Thusitha Senadirage.en_US
dc.contributor.authorJayawardena, Thusitha Senadirage.en_US
dc.date.issued1990en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractWe investigate stochastic systems which have a set of control parameters and a performance criterion. By operating the system at fixed control parameters, noisy performance values are observed. (The values are noisy due to the inherent stochastic nature of the system.) Certain relevant distributions of the system are assumed unavailable. The task is to develop algorithms that guide the system to optimal parameter settings based on its operating history. Consider the stochastic shortest path problem, where the time to traverse an edge is given by a random variable whose distribution is unavailable explicitly. The optimality criterion (to be maximized) is the probability of going from a given source node to a given terminal node within a specified critical time period. By choosing a particular path and traversing it, realizations of the distributions, i.e. time to go from the source node to the terminal node on that path are observed. Or consider the M/M/1 queue. Here, the control parameter is the average service time. The performance criterion is the sum of cost of the server and cost of system time of a customer in steady-state. By choosing a particular average service time and serving accordingly, a noisy observation of the total cost is obtained. We combine an asymptotically optimal random search method for finding the global optimum of a function with problem-specific local search techniques. Such a combination results in efficient solution procedures for the above problems. This conclusion is reached by applying the procedure to problems for which the optimum solutions are known. The main contribution of the study is in demonstrating that "reasonable" performance can be achieved for the proposed optimization problems in "reasonable" time by exploiting problem-specific structures to advantage. The generality of the method should allow others to use it in different optimization settings than ours. Also, the self-optimizing aspect of these methods and the stochastic versions of the local search techniques are new.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineeringen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorYakowitz, Sidneyen_US
dc.contributor.committeememberSen, Suvrajeeten_US
dc.identifier.proquest9024645en_US
dc.identifier.oclc708183944en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.