No description available.

In this paper we analyze the relationships between the flows of customers in a queueing network whose queue length process is a Markov process. A flow is a stochastic process formed by embedding the queue length process at transitions corresponding to: customers arriving to the network at a node; customers departing the network from a node; customers moving from one node to another node; all customers entering a node; all customers leaving a node; superpositions and decompositions of the flows described above. We show that flow processes in queueing networks are Markov renewal processes. In fact, we construct two Markov renewal processes corresponding to a flow. One Markov renewal process is formed by embedding the queue length process just before transitions of interest. The other Markov renewal process is formed by embedding the queue length process just after the transitions of interest. If a queueing network is a Jackson network and if the queue length process is reversible then the Markov renewal process formed by embedding the queue length process just before inputs to a node is the reverse process of the Markov renewal process formed by embedding the queue length process just after outputs from the node. Similar results hold for other flows in the network. We extend the above results to networks of symmetric queues where the service times are restricted to the Erlang distributed. To do this we need to introduce the concept of the quasi-reversed process of a Markov renewal process. A closed queueing network is constructed where the queue length process is not reversible yet the input process is the reverse process of the output process at each node. Another closed network is constructed where the queue length process is not reversible and the input process is not the reverse process of the output process at a node. From these two examples we conclude that reversibility is not a necessary condition for the input process to be the reverse process of the output process at a node and that the input process is not always the reverse process of the output process. Some implications of these results when applied to the decomposition or recomposition of stochastic processes are discussed. / Ph. D.

This thesis develops a stochastic model for satellite packet switching networks, using results from queueing theory that have been previously explored in modeling communication networks. This thesis also analyzes message queueing delay when users of the network are generating data at moderate to high rates. Average packet delay and average number of packets in the system are formulated. The model developed herein is applied to two cases. In the first case packet transmission and back off times are deterministic. In the second case packet transmission and back off times are exponentially distributed. The input parameters to this model are packet arrival rate, average packet transmission time, average back off time and probability of packet collision. The model yields average packet delay and average number of packets in the system. Methods to compute the probability of collision are presented. / Master of Science

Materials requirements planning (MRP) is a widely used method for production planning and scheduling. Planned lead-time (PLT) and lot size are two of the input parameters for MRP systems, which determine planned order release dates. Presently, planned lead-time and lot size are estimated using independent methodologies. No existing PLT estimation methods consider factors such as machine breakdown, scrap-rate, etc. Moreover, they do not consider the capacity of a shop, which changes dynamically, because the available capacity at any given time is determined by the loading of the shop at that time. The absence of such factors in calculations leads to a huge lead-time difference between the actual lead-time and PLT, i.e., lead-time error. Altering the size of a lot will have an effect not only on the lead-time of that lot but also on that of other lots. The estimation of lot size and lead-time using independent methodologies currently does not completely capture the inter-dependent nature of lead-time and lot size. In this research, a lot-sizing model is modified in such a way that it minimizes the combination of setup cost, holding cost and work-in-process cost. This proposed approach embeds an optimization routine, which is based on dynamic programming on a manufacturing system model, which is based on open queuing network theory. Then, it optimizes lot size by using realistic estimates of WIP and the lead-time of different lots simultaneously for single-product, single-level bills of material. Experiments are conducted to compare the performance of the production plans generated by applying both conventional and the proposed methods. The results show that the proposed method has great potential and it can save up to 38% of total cost and minimize lead-time error up to 72%. / Master of Science

No description available.

In this dissertation we employ stack and queue layouts of graphs to explore the relative power of stacks and queues. Stack layout and queue layouts of graphs can be examined from several points of view. A stack or a queue layout of a graph can be thought of as an embedding of the graph in a plane satisfying certain constraints, or as a graph linearization that optimizes certain cost measures, or as a scheme to process the edges of the graph using the fewest number of stacks or queues. All three points of view permeate this research, though the third point of view dominates. Specific problems in stack and queue layouts of graphs have their origin in the areas of VLSI, fault-tolerant computing, scheduling parallel processes, sorting with a network of stacks and queues, and matrix computations. We first present two tools that are useful in the combinatorial and algorithmic analysis of stack and queue layouts as well as in determining bounds on the stacknumber and the queuenumber for a variety of graphs. The first tool is a formulation of a queue layout of a graph as a covering of its adjacent matrix with staircases. Not only does this formulation serve as a tool for analyzing stack and queue layouts, it also leads to efficient algorithms for several problems related to sequences, graph theory, and computational geometry. The connection between queue layouts and matrix covers also forms the basis of a new scheme for performing matrix computations on a data driven network. Our analysis reveals that this scheme uses less hardware and is faster than existing schemes. The second tool is obtained by considering separated and mingled layouts of graphs. This tool allows us to obtain lower bounds on the stacknumber and the queuenumber of a graph by partitioning the graph into subgraphs and simply concentrating on the interaction of the subgraphs. These tools are used to obtain results in three areas. The first area is stack and queue layouts of directed acyclic graphs (dags). This area is motivated by problems of scheduling parallel processes. We establish the stacknumber and the queuenumber of classes of dags such as trees, unicylic graphs, outerplanar graphs, and planar graphs. We then present linear time algorithms to recognize 1-stack dags and leveled-planar dags. In contrast, we show that the problem of recognizing 9-stack dags and the problem of recognizing 4-queue dags are both NP-complete. The second area is stack and queue layouts of partially ordered sets (posets). We establish upper bounds on the queuenumber of a poset in terms of other measures such as length, width, and jumpnumber. We also present lower bounds on the stacknumber and on the queuenumber of certain classes of posets. We conclude by showing that the problem of recognizing a 4-queue poset is NP-complete. The third area is queue layouts of planar graphs. While it has been shown that the stacknumber of the family of planar graphs is 4, the queuenumber of planar graphs is unknown. We conjecture that a family of planar graphs—the stellated triangles—has unbounded queuenumber; using separated and mingled layouts, we demonstrate significant progress towards that result. / Ph. D.

In this paper we study properties of a queue with instantaneous Bernoulli feedback where the service discipline is one of two symmetric disciplines. For the processor sharing queue with exponentially distributed service requirements we analyze the departure process, imbedded queue lengths, and the input and output processes. We determine the semi-Markov kernel of the internal flow processes and compute their stationary interval distributions and forward recurrence time distributions. For generally distributed service times, we analyze the output process using a continuous state Markov process. We compare the case where service times are exponentially distributed to the case where they are generally distributed. For the infinite server queue with feedback, we show that the output process is never renewal when the feedback probability is non-zero. We compute the time until the next output in three special cases. / Ph. D.

In the present work, we study a queue with a Markov renewal service process. The objective is to model systems where different customers request different services and there is a setup time required to adjust from one type of service to the next. The arrival is a Poisson process independent of the service. After arrival, all the customers will be attended in order of arrival. Immediately before a service starts, the type of next customer is chosen using a finite, irreducible and aperiodic Markov chain P. There is only one server and the service time has a distribution function F_ij, where i and j are the types of the previous and current customer in service, respectively. This model will be called M/MR/l. Embedding at departure epochs, we characterize the queue length and the type of customer as a Markov renewal process. We study a special case where F_ij, is exponential with parameter μ_ij. We prove that the departure is a renewal process if and only if μ_ij = μ , A i j ε E. Furthermore, we show that this renewal is a Poisson process. The type-departure process is extensively studied through the respective counting processes. The crosscovariance and the crosscorrelation are computed and numerical results are shown. Finally, we introduce several expressions to study the interdependence among the type·departure processes in the general case, i.e. the distribution function F_ij, does not have any special form. / Ph. D.

Vacation systems represent an important class of queueing models having application in both computer communication systems and integrated manufacturing systems. By specifying an appropriate server scheduling discipline, vacation systems are easily particularized to model many practical situations where the server's effort is divided between primary and secondary customers. A general stochastic framework that subsumes a wide variety of server scheduling disciplines for the M/GI/1/L vacation system is developed. Here, a class of server scheduling disciplines, called Markov schedules, is introduced. It is shown that the queueing behavior M/GI/1/L vacation systems having Markov schedules is characterized by a queue length/server activity marked point process that is Markov renewal and a joint queue length/server activity process that is semi-regenerative. These processes allow characterization of both the transient and ergodic queueing behavior of vacation systems as seen immediately following customer service completions, immediately following server vacation completions, and at arbitrary times The state space of the joint queue length/server activity process can be systematically particularized so as to model most server scheduling disciplines appearing in the literature and a number of disciplines that do not appear in the literature. The Markov renewal nature of the queue length/server activity marked point process yields important results that offer convenient computational formulae. These computational formulae are employed to investigate the ergodic queue length of several important vacation systems; a number of new results are introduced. In particular, the M/GI/1 vacation with limited batch service is investigated for the first time, and the probability generating functions for queue length as seen immediately following service completions, immediately following vacation completions, and at arbitrary times are developed. / Ph. D.

This paper gives results on various traffic processes and on the sojourn time distribution for a class of models which operate as Markov processes on finite state spaces. The arrival and the service time processes are assumed to be independent renewal processes with interval distributions of phase-type. The queue capacity is finite. A general class of queue disciplines are considered. The primary models studied are from the M/E_k/Φ/L class. The input, output, departure and overflow processes are analyzed. Furthermore, the sojourn time distribution is determined. Markov renewal theory provides the main analytical tools. It is shown that this work unifies many previously known results and offers some new results. Various extensions, including a balking model, are studied. / Ph. D.