Thesis--Auburn University, 2008. / Abstract. Vita. Includes bibliographic references (p.35).

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Multiclass queueing networks are widely used to model complex manufacturing systems and communications networks. In this dissertation we describe and analyze a multiclass queueing network model known as the Cambridge Ring. As the name suggest this network has a circular topology with unidirectional routing. In many cases the analysis of a stochastic model is a difficult task. For a few special cases of this network we show that all non-idling policies are throughput optimal for this system. One of the major differences between this work and precious literature is that we prove throughput optimality of all non-idling policies, whereas most of the previous work has been on establishing throughput optimality for a specific policy (usually First-In-First-Out). We use a macroscopic technique known as fluid model to identify optimal policies with respect to work in process. In one case we consider, the discrete scheduling policy motivated by the optimal fluid policy is indeed optimal in the discrete network. For the other special case we show by means of a deterministic counterexample that the discrete policy most naturally suggested by the fluid optimal policy may not be optimal for the queueing network. We also formulate the fluid holding cost optimization problem and present its solution for a simple version of the Cambridge Ring. Further we establish that the optimal policy under a class of policies known as "non-ejective" policies may be an idling policy. We use an example of the Cambridge Ring with a single vehicle to show that the optimal policy for this example has to be an idling policy. / text

Thesis (M.Sc.). / Written for the School of Computer Science. Title from title page of PDF (viewed 2008/07/29). Includes bibliographical references.

In post-industrial economies, modern service systems are dramatically changing the daily lives of many people. Such systems are often complicated by uncertainty: service providers usually cannot predict when a customer will arrive and how long the service will be. Fortunately, useful guidance can often be provided by exploiting stochastic models such as queueing networks. In iterating the design of service systems, decision makers usually favor analytical analysis of the models over simulation methods, due to the prohibitive computation time required to obtain optimal solutions for service operation problems involving multidimensional stochastic networks. However, queueing networks that can be solved analytically require strong assumptions that are rarely satisfied, whereas realistic models that exhibit complicated dependence structure are prohibitively hard to analyze exactly. In this thesis, we continue the effort to develop useful analytical performance approximations for the single-class open queueing network with Markovian routing, unlimited waiting space and the first-come first-served service discipline. We focus on open queueing networks where the external arrival processes are not Poisson and the service times are not exponential. We develop a new non-parametric robust queueing algorithm for the performance approximation in single-server queues. With robust optimization techniques, the underlying stochastic processes are replaced by samples from suitably defined uncertainty sets and the worst-case scenario is analyzed. We show that this worst-case characterization of the performance measure is asymptotically exact for approximating the mean steady-state workload in G/G/1 models in both the light-traffic and heavy-traffic limits, under mild regularity conditions. In our non-parametric Robust Queueing formulation, we focus on the customer flows, defined as the continuous-time processes counting customers in or out of the network, or flowing from one queue to another. Each flow is partially characterized by a continuous function that measures the change of stochastic variability over time. This function is called the index of dispersion for counts. The Robust Queueing algorithm converts the index of dispersion for counts into approximations of the performance measures. We show the advantage of using index of dispersion for counts in queueing approximation by a renewal process characterization theorem and the ordering of the mean steady-state workload in GI/M/1 models. To develop generalized algorithm for open queueing networks, we first establish the heavy-traffic limit theorem for the stationary departure flows from a GI/GI/1 model. We show that the index of dispersion for counts function of the stationary departure flow can be approximately characterized as the convex combination of the arrival index of dispersion for counts and service index of dispersion for counts with a time-dependent weight function, revealing the non-trivial impact of the traffic intensity on the departure processes. This heavy-traffic limit theorem is further generalized into a joint heavy-traffic limit for the stationary customer flows in generalized Jackson networks, where the external arrival are characterized by independent renewal processes and the service times are independent and identically distributed random variables, independent of the external arrival processes. We show how these limiting theorems can be exploited to establish a set of linear equations, whose solution serves as approximations of the index of dispersion for counts of the flows in an open queueing network. We prove that this set of equations is asymptotically exact in approximating the index of dispersion for counts of the stationary flows. With the index of dispersion for counts available, the network is decomposed into single-server queues and the Robust Queueing algorithm can be applied to obtain performance approximation. This algorithm is referred to as the Robust Queueing Network Analyzer. We perform extensive simulation study to validate the effectiveness of our algorithm. We show that our algorithm can be applied not only to models with non-exponential distirbutions but also to models with more complex arrival processes than renewal processes, including those with Markovian arrival processes.

We examine the problem of staffing refreshment stations at a long distance road race. A race is modeled as a mixed queueing network in which the required number of servers at each service station has to be estimated. Two models to represent the progress of runners along a long distance road race course are developed. One model is a single-class model that allows a road race manager to staff service stations assuming the runners are identical to those in some historical dataset. Another model is a multi-class simulation model that allows a road race manager to simulate a race of any number of runners, classified based on their running pace into different runner classes. Both the single-class model and the multi-class model include estimates for the rates at which the runners arrive at specified locations along the course. The arrival rates, combined with assumed service rates, allow us to base staffing decisions on the Erlang loss formula or a lesser known staffing rule that gives a lower bound for the required number of servers. We develop a staffing strategy that we call the Peak Arrival Staffing Bound (PASB), which is based on this staffing bound. The PASB and the Erlang loss formula are implemented in the single-class model and the multi-class simulation model. By way of numerical experiments, we find that the PASB is numerically stable and can be used to get staffing results regardless of the traffic intensity. This finding is in contrast to the Erlang loss formula, which is known to become numerically unstable and overflows when the traffic intensity exceeds 171. We compare numerical results of the PASB and the Erlang loss formula with a blocking probability level of 5% and find that when iii the traffic intensity is high, staffing results based on the PASB are more conservative than staffing results based on the Erlang loss formula. As the traffic intensity gets lower, we find that staffing results based on the PASB are similar to staffing results based on the Erlang loss formula. These findings suggest that the PASB can be a valuable tool to aid race directors in making staffing decisions for races of all traffic intensities

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Ayhan, Hayriye; Committee Member: Foley, Robert D.; Committee Member: Goldsman, David M.; Committee Member: Reed, Joshua; Committee Member: Zwart, Bert. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Fluid networks are useful tools for analyzing complex manufacturing environments especially in semiconductor wafer fabrication. The makespan of a fluid network is defined as the time to drain the system, when there is fluid present in the buffers initially. Based on this definition, the question of determining the allocation of resources so as to minimize the makespan of a fluid network is known as the makespan problem. In the deterministic version of the makespan problem, it is assumed that the parameters of the system, such as incoming rates, service rates and initial inventory, are known deterministically. The deterministic version of the makespan problem for reentrant lines and multiclass fluid networks has been investigated in the literature and an analytical solution for the problem is well-known. In this work, we provide another formulation for the deterministic makespan problem and prove that the problem can be solved for each station separately. Optimal solutions for the deterministic makespan problem have been used as a guide to develop heuristics methods to solve makespan scheduling problem in the job-shop context in the literature. This provides one motivation for further investigation of the fluid makespan problem. In this work our main focus is solving the makespan problem when the problem parameters are uncertain. This uncertainty may be caused by various factors such as the unpredictability of the arrival process or randomness in machine availability due to failures. In the presence of parameter uncertainty, the decision maker's goal is to optimally allocate the capacity in order to minimize the expected value of the makespan. We assume that the decision maker has distributional information about the parameters at the time of decision making. We consider two decision making schemes. In the first scheme, the controller sets the allocations before observing the parameters. After the initial allocations are set, they cannot be changed. In the second scheme, the controller is allowed a recourse action after a data collection process. It is shown that in terms of obtaining the optimal control, both schemes differ considerably from the deterministic version of the problem. We formulate both schemes using stochastic programming techniques. The first scheme is easier to analyze since the resulting model is convex. Unfortunately, under the second decision scheme, the objective function is non-convex. We develop a branch-and-bound methodology to solve the resulting stochastic non-convex program. Finally, we identify some special cases where the stochastic problem is analytically solvable. This work uses stochastic programming techniques to formulate and solve a problem arising in queueing networks. Stochastic programming and queueing systems are two major areas of Operations Research that deal with decision making under uncertainty. To the best of our knowledge, this dissertation is one of the first works that brings these two major areas together.

Concurrent systems, including asynchronous circuits, computer networks, and multi-threaded programs, have important applications, but they are also very complex and expensive to test. This thesis studies how to test concurrent systems through contexts consisting of queues. Queues, modeling buffers and communication delays, are an integral part of the test settings for concurrent systems. However, queues can also distort the behavior of the concurrent system as observed by the tester, so one should take into account the queues when defining conformance relations or deriving tests. On the other hand, queues can cause state explosion, so one should avoid testing them if they are reliable or have already been tested. To solve these problems, we propose two different solutions. The first solution is to derive tests using some test selection criteria such as test purposes, fault coverage, and transition coverage. The second solution is to compensate for the problems caused by the queues so that testers do not discern the presence of the queues in the first place. Unifying the presentation of the two solutions, we consider in a general testing framework partial specifications, various contexts, and a hierarchy of conformance relations. Case studies on test derivation for asynchronous circuits, communication protocols, and multi-threaded programs are presented to demonstrate the applications of the results.

The Internet has experienced a tremendous growth over the past two decades and with that growth have come severe congestion problems. Research efforts to alleviate the congestion problem can broadly be classified into three groups: Cl) Router based congestion detection; (2) Generation and transmission of congestion notification signal to the traffic sources; (3) End-to-end algorithms which control the flow of traffic between the end hosts. This dissertation has largely addressed the first two groups which are basically router initiated. Router based congestion detection mechanisms, commonly known as Active Queue Management (AQM), can be classified into two groups: conventional mathematical analytical techniques and fuzzy logic based techniques. Research has shown that fuzzy logic techniques are more effective and robust compared to the conventional techniques because they do not rely on the availability of a precise mathematical model of Internet. They use linguistic knowledge and are, therefore, better placed to handle the complexities associated with the non-linearity and dynamics of the Internet. In spite of all these developments, there still exists ample room for improvement because, practically, there has been a slow deployment of AQM mechanisms. In the first part of this dissertation, we study the major AQM schemes in both the conventional and the fuzzy logic domain in order to uncover the problems that have hampered their deployment in practical implementations. Based on the findings from this study, we model the Internet congestion problem as a multi-objective problem. We propose a Fuzzy Logic Congestion Detection (FLCD) which synergistically combines the good characteristics of the fuzzy approaches with those of the conventional approaches. We design the membership functions (MFs) of the FLCD algorithm automatically by using Multi-objective Particle Swarm Optimization (MOPSO), a population based stochastic optimization algorithm. This enables the FLCD algorithm to achieve optimal performance on all the major objectives of Internet congestion control. The FLCD algorithm is compared with the basic Fuzzy Logic AQM and the Random Explicit Marking (REM) algorithms on a best effort network. Simulation results show that the FLCD algorithm provides high link utilization whilst maintaining lower jitter and packet loss. It also exhibits higher fairness and stability compared to its basic variant and REM. We extend this concept to Proportional Differentiated Services network environment where the FLCD algorithm outperforms the traditional Weighted RED algorithm. We also propose self learning and organization structures which enable the FLCD algorithm to achieve a more stable queue, lower packet losses and UDP traffic delay in dynamic traffic environments on both wired and wireless networks. In the second part of this dissertation, we present the congestion notification mechanisms which have been proposed for wired and satellite networks. We propose an FLCD based dual explicit congestion notification algorithm which combines the merits of the Explicit Congestion Notification (ECN) and the Backward Explicit Congestion Notification (BECN) mechanisms. In this proposal, the ECN mechanism is invoked based on the packet marking probability while the BECN mechanism is invoked based on the BECN parameter which helps to ensure that BECN is invoked only when congestion is severe. Motivated by the fact that TCP reacts to tbe congestion notification signal only once during a round trip time (RTT), we propose an RTT based BECN decay function. This reduces the invocation of the BECN mechanism and resultantly the generation of reverse traffic during an RTT. Compared to the traditional explicit notification mechanisms, simulation results show that the new approach exhibits lower packet loss rates and higher queue stability on wired networks. It also exhibits lower packet loss rates, higher good-put and link utilization on satellite networks. We also observe that the BECN decay function reduces reverse traffic significantly on both wired and satellite networks while ensuring that performance remains virtually the same as in the algorithm without BECN traffic reduction. / Thesis (M.Sc.Eng.)-University of KwaZulu-Natal, 2006.