Effective scheduling algorithms for service and computing systems
Abstract/Contents
- Abstract
- A number of dynamic stochastic optimization problems of current interest are difficult to solve from both a practical as well as theoretical perspective. These problems are often said to suffer from the 'curse of dimensionality'. Unfortunately, there are few, if any, general methodologies to address these high dimensional optimization problems; such problems tend to be considered on a case-by-case basis. This is in stark contrast to deterministic optimization, wherein there exists techniques for large well-studied families of tractable problems such as convex optimization for continuous problems and submodular optimization over matroids for combinatorial problems. This thesis takes a first step towards constructing such a framework for high dimensional stochastic optimization problems. The main approaches focus on reducing the time horizon over which to optimize and/or making systematic modeling reductions. The scheduling problems presented in this thesis fall under a broad, general class of dynamic stochastic optimization problems whose objectives can be classified as either profit maximization, cost minimization, or a tradeoff between cost and delay minimization. This thesis presents effective, near optimal solutions to a number of hard scheduling problems which have received considerable attention in their own right including, but not limited to, parallel server queues, multimedia broadcast scheduling, product line design, the Adwords assignment problem, and hospital Intensive Care Unit Scheduling. The focus of this thesis is on evaluating the performance of myopic and myopic-like heuristics. This thesis presents a general framework in which to consider a number of dynamic optimization problems. Problems which can be cast in this framework will inherit the performance guarantees of the presented simple, yet effective, heuristic policies.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2010 |
| Publication date | 2009, c2010; 2009 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Chan, Carri W |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Bambos, Nicholas |
| Thesis advisor | Bambos, Nicholas |
| Thesis advisor | Apostolopoulos, John G |
| Thesis advisor | Glynn, Peter W |
| Advisor | Apostolopoulos, John G |
| Advisor | Glynn, Peter W |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Carri Wing Sie Chan. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2010. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2010 by Carri Wing Sie Chan
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...