Acknowledgements

I joined Computer Science Department at Carnegie Mellon University as a graduate student in the fall of 2001. Mor Harchol-Balter has been my adviser since then. First of all, I would like to thank Mor for her advice on all aspects of my graduate study.

One of my first accomplishments as a graduate student was an analysis of the size-based task assignment with cycle stealing under immediate dispatching, SBCS-ID (Chapter 5). In the summer of 2002, I derived a closed form solution for the mean response time of the long jobs via a virtual waiting time analysis (Theorem 9). This small step turned out to be a ``big'' step in my graduate research. Mor Harchol-Balter, Alan Scheller-Wolf, and Mark S. Squillante had been taking a different approach in the analysis of SBCS-ID, which was later developed into dimensionality reduction (DR) as in this thesis. With the virtual waiting time analysis, I joined the project of SBCS-ID analysis. It was very fortunate that I could join the project of developing DR in its early stage.

In parallel to SBCS-ID, we analyzed the size-based task assignment with cycle stealing under central queue, SBCS-CQ (Chapter 5). The analysis of SBCS-CQ was more difficult, and we needed to introduce an additional approximation together with the renaming scheme. Ironically, it turns out that SBCS-CQ can be analyzed without the additional approximation by DR (when it is extended as in this thesis) if the renaming scheme is not used; however, DR does not apply without an additional approximation if the renaming scheme is used.

In the fall of 2002, we summarized SBCS-ID in [68] and SBCS-CQ in [67], and Mor, Alan, and I moved on to the analysis of a threshold-based policy for reducing switching costs in cycle stealing (Chapter 6). Retrospectively, it is quite surprising that we were able to analyze this system at that time, when the DR was not fully generalized as in this thesis. This system can be modeled as a GFB process where the background process is a QBD process. At that time, we did not know how to analyze the inter-level passage time in a QBD process (Section 3.7). Nevertheless, we were able to combine various busy periods in M/G/1 queues with setup times to represent the inter-level passage time in a QBD process in this special case. We summarized the analysis for the case without the donor size threshold in [151], and the full analysis in [152]. The use of generalized vacation as in Theorem 11 was suggested by an anonymous reviewer of Performance Evaluation, and this simplified the analysis of the mean response time of donor jobs.

In the analysis of SBCS-ID, SBCS-CQ, and the threshold-based policy for reducing switching costs in cycle stealing, I had occasionally encountered a problem in approximating a busy period duration by a two-phase phase type (PH) distribution. The parameters of the two-phase PH distributions sometimes became complex numbers! This motivated me to investigate which distributions can be well-represented (Definition 1) by an $n$-phase PH distribution for $n=2,3,4,...$ (Chapter 2). This characterization was summarized in [147] with Mor Harchol-Balter.

This characterization gave me a great insight into how a general distribution can be well-represented by a PH distribution with nearly minimal number of phases (Chapter 2). Discovery of the properties of function $\phi$ (Theorem 3) was the key in the development of our moment matching algorithms. The moment matching algorithms were summarized in [145] with Mor Harchol-Balter. The two papers [145,147] were selected among the best papers in TOOLS 2003, and combined into [148] for a special edition in Performance Evaluation. Miklos Telek and anonymous reviewers of TOOLS 2003 and Performance Evaluation gave us very detailed and relevant comments and suggestions for [147,145,148], and the quality of these papers and Chapter 2 of this thesis was greatly improved by these comments and suggestion. Also, the Positive solution (Section 2.8) was motivated by a discussion with Miklos Telek and Armin Heindl at TOOLS 2003. Applications of moment matching algorithms in inventory system analysis were suggested by Geert-Jan van Houtum (Section 2.1), and the benefit of acyclic PH distribution over cyclic one was suggested by Sindo Nunez Queija (Section 2.9) during my visit at Eindhoven University of Technology in July 2004.

DR was extended quite a bit in the summer of 2003, utilizing Neuts' algorithm for computing the inter-level passage time in a QBD process [134,137]. The extended DR was then applied to an analysis of multiserver systems with multiple priority classes (Chapter 4), which was summarized in [156,155,70] with Adam Wierman, Mor Harchol-Balter, and Alan Scheller-Wolf.

DR was also applied to an analysis of threshold-based policies for the Beneficiary-Donor model (Chapter 7) in the spring of 2004. This interesting problem was inspired by a talk by Li Zhang at our weekly seminar, SQUALL, and Li Zhang, Mor Harchol-Balter, Alan Scheller-Wolf, and I started to analyzed the performance of various threshold-based policies. The analysis was summarized in an invited paper at Allerton Conference [153]. The extensive analysis of the threshold-based policies revealed robustness of these threshold-based policies. Mor Harchol-Balter, Alan Scheller-Wolf, and I continued to investigate the robustness of threshold-based policies for the Beneficiary-Donor model, and the results were summarized in [149]. some of the results in [149] were also presented at the MAMA workshop [69].

DR was further extended and formalized in the summer and fall of 2004. I defined a class of Markov chains called RFB/GFB processes, and the RFB/GFB process was analyzed via DR (Chapter 3). The RFB/GFB process can model all the multiserver systems that we had analyzed by then [67,68,69,70,149,151,153,155,156] as well as more multiserver systems such as multiserver systems with nonpreemptive priority classes. Also, in [67,68,69,70,149,151,153,155,156], only the performance of ``beneficiary jobs'' or ``low priority jobs'' was analyzed via DR, and the performance of ``donor jobs'' or ``high priority jobs'' needed to be analyzed independently with different techniques for different multiserver systems. By contrast, in the analysis of RFG/GFB process, the performance of ``donor jobs'' or ``high priority jobs'' is also analyzed with a unified framework of DR. This extension and formalization were inspired by a discussion with Ivo Adan, Andrei Sleptchenko, and Onno Boxma during my visit at Eindhoven University of Technology in July 2004. A part of the results in Chapter 3 was summarized in a technical report [143].

I would like to thank Mor Harchol-Balter, Mark S. Squillante, Varun Gupta, Alan Scheller-Wolf, and Adam Wierman for reading an earlier version of this thesis. Their comments and suggestions significantly helped improving the quality of the thesis. Also, the thesis would not be completed if it was not for their encouragement. Further, I would like to thank IBM Japan and IBM Tokyo Research Laboratory for their full support during the four years of my graduate study. Finally, I would like to thank Adam Wierman for making my graduate life productive and fun.