Evaluation of basis functions for generating approximate linear programming (ALP) average cost solutions and policies for multiclass queueing networks

Repository

Evaluation of basis functions for generating approximate linear programming (ALP) average cost solutions and policies for multiclass queueing networks

Show simple record

dc.contributor.advisor Hasenbein, John J.
dc.creator Gurfein, Kate Elizabeth
dc.date.accessioned 2012-08-16T18:18:01Z
dc.date.available 2012-08-16T18:18:01Z
dc.date.created 2012-05
dc.date.issued 2012-08-16
dc.date.submitted May 2012
dc.identifier.uri http://hdl.handle.net/2152/ETD-UT-2012-05-5441
dc.description.abstract The average cost of operating a queueing network depends on several factors such as the complexity of the network and the service policy used. Approximate linear programming (ALP) is a method that can be used to compute an accurate lower bound on the optimal average cost as well as generate policies to be used in operating the network. These average cost solutions and policies are dependent on the type of basis function used in the ALP. In this paper, the ALP average cost solutions and policies are analyzed for twelve networks with four different types of basis functions (quadratic, linear, pure exponential, and mixed exponential). An approximate bound on the optimality gap between the ALP average cost solution and the optimal average cost solution is computed for each system, and the size of this bound is determined relative to the ALP average cost solution. Using the same set of networks, the performance of ALP generated policies are compared to the performance of the heuristic policies first-buffer-first-served (FBFS), last-buffer-first-served (LBFS), highest-queue-first-served (HQFS), and random-queue-first-served (RQFS). In general, ALP generated average cost solutions are considerably smaller than the simulated average cost under the corresponding policy, and therefore the approximate bounds on the optimality gaps are quite large. This bound increases with the complexity of the queueing network. Some ALP generated policies are not stabilizing policies for their corresponding networks, especially those produced using pure exponential and mixed exponential basis functions. For almost all systems, at least one of the heuristic policies results in mean average cost less than or nearly equal to the smallest mean average cost of all ALP generated policies in simulation runs. This means that generally there exists a heuristic policy which can perform as well as or better than any ALP generated policy. In conclusion, a useful bound on the optimality gap between the ALP average cost solution and the optimal average cost solution cannot be computed with this method. Further, heuristic policies, which are more computationally tractable than ALP generated policies, can generally match or exceed the performance of ALP generated policies, and thus computing such policies is often unnecessary for realizing cost benefits in queueing networks.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subject Approximate linear programming
dc.subject ALP
dc.subject Multiclass queueing networks
dc.subject Dynamic programming
dc.subject Optimal policy
dc.subject Optimality gap
dc.title Evaluation of basis functions for generating approximate linear programming (ALP) average cost solutions and policies for multiclass queueing networks
dc.date.updated 2012-08-16T18:18:08Z
dc.identifier.slug 2152/ETD-UT-2012-05-5441
dc.contributor.committeeMember Morton, David P.
dc.description.department Operations Research and Industrial Engineering
dc.type.genre thesis
dc.type.material text
thesis.degree.department Operations Research and Industrial Engineering
thesis.degree.discipline Operations Research & Industrial Engineering
thesis.degree.grantor University of Texas at Austin
thesis.degree.level Masters
thesis.degree.name Master of Science in Engineering

Files in this work

Size: 1.096Mb
Format: application/pdf

This work appears in the following Collection(s)

Show simple record


Advanced Search

Browse

My Account

Statistics

Information