Heavy-tailed workload distributions are commonly experienced in many areas of distributed computing. Such workloads are highly variable, where a small number of very large tasks make up a large proportion of the workload, making the load very hard to distribute effectively. Traditional task assignment policies are ineffective under these conditions as they were formulated based on the assumption of an exponentially distributed workload. Size-based task assignment policies have been proposed to handle heavy-tailed workloads, but their applications are limited by their static nature and assumption of prior knowledge of a task's service requirement. This thesis analyses existing approaches to load distribution under heavy-tailed workloads, and presents a new generalised task assignment policy that significantly improves performance for many distributed applications, by intelligently addressing the negative effects on performance that highly variable workloads cause. Many problems associated with the modelling and optimisations of systems under highly variable workloads were then addressed by a novel technique that approximated these workloads with simpler mathematical representations, without losing any of their pertinent original properties. Finally, we obtain advance queuing metrics (such as the variance of key measurements like waiting time and slowdown that are difficult to obtain analytically) through rigorous simulation.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 409-417).

This thesis proposes a computationally effective analytical approach to automated material handling system (AMHS) performance modeling for a simple closed loop AMHS, such as is typical in supporting a 300mm wafer fab bay. Discrete-event simulation can produce accurate assessments of the production performance, including the contribution by the AMHS. However, the corresponding simulation models are both expensive and time-consuming to construct, and require long execution times to produce statistically valid estimates. These attributes render simulation ineffective as a decision support tool in the early phase of system design, where requirements and configurations are likely to change often. We propose an alternative model that estimates the AMHS performance considering the possibility of vehicle-blocking. A probabilistic model is developed, based on a detailed description of AMHS operations, and the system is analyzed as an extended Markov chain. The model tracks the operations of all the vehicles on the closed-loop considering the possibility of vehicle-blocking. The resulting large-scale model provided reasonably accurate performance estimates; however, it presented some computational challenges. These computational challenges motivated the development of a second model that also analyzes the system as an extended Markov chain but with a much reduced state space because the model tracks the movement of a single vehicle in the system with additional assumptions on vehicle-blocking. Neither model is a conventional Markov Chain because they combine the conventional Markov Chain analysis of the AMHS operations with additional constraints on AMHS stability and vehicle-blocking that are necessary to provide a unique solution to the steady-state behavior of the AMHS. Based on the throughput capacity model, an approach is developed to approximate the expected response time of the AMHS to move requests. The expected response times are important to measure the performance of the AMHS and for estimating the required queue capacity at each pick-up station. The derivation is not straightforward and especially complicated for multi-vehicle systems. The approximation relies on the assumption that the response time is a function of the distribution of the vehicles along the tracks and the expected length of the path from every possible location to the move request location.

In the first half of this thesis, we extend the results of Halfin and Whitt to generally distributed service times. This is accomplished by first writing the system equations for the G/GI/N queue in a manner similar to the system equations for G/GI/Infinity queue. We next identify a key relationship between these two queues. This relationship allows us to leverage several existing results for the G/GI/Infinity queue in order to prove our main result. Our main result in the first part of this thesis is to show that the diffusion scaled queue length process for the G/GI/N queue in the Halfin-Whitt regime converges to a limiting stochastic process which is driven by a Gaussian process and satisfies a stochastic convolution equation. We also show that a similar result holds true for the fluid scaled queue length process under general initial conditions. Customer abandonment is also a common feature of many call centers. Some researchers have even gone so far as to suggest that the level of customer abandonment is the single most important metric with regards to a call center's performance. In the second half of this thesis, we improve upon a result of Ward and Glynn's concerning the GI/GI/1+GI queue in heavy traffic. Whereas Ward and Glynn obtain a diffusion limit result for the GI/GI/1+GI queue in heavy traffic which incorporates only the density the abandonment distribution at the origin, our result incorporate the entire abandonment distribution. This is accomplished by a scaling the hazard rate function of the abandonment distribution as the system moves into heavy traffic. Our main results are to obtain diffusion limits for the properly scaled workload and queue length processes in the GI/GI/1+GI queue. The limiting diffusions we obtain are reflected at the origin with a negative drift which is dependent upon the hazard rate of the abandonment distribution. Because these diffusions have an analytically tractable steady-state distribution, they can be used to provide a closed-form approximation for the steady-state distribution of the queue length and workload processes in a GI/GI/1+GI queue. We demonstrate the accuracy of these approximations through simulation.

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / Mechanical Engineering / Master / Master of Philosophy

No description available.

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 121-128).

Thesis (M.Sc. (Hons.)) -- University of Western Sydney, 2001. / "A thesis presented to the University of Western Sydney in partial fulfilment of the requirements for the degree of Master of Science" Bibliography : leaves 65-69.

Thesis (M.B.A.)--University of Hong Kong, 1996. / Includes bibliographical references (leaf 54-55).