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.

No description available.

Thesis (MBA)--Stellenbosch University, 1999. / ENGLISH ABSTRACT: A mini-study project presented on the use of Microsoft Excel 2000 in the field of simulation. The mini-study project covers the principles of queuing and it’s outputs. The simulation model will test various scenario’s of queuing theory. Inputs can be changed to suit the users requirements. Results may be analysed to determine an optimal queuing environment. / AFRIKAANSE OPSOMMING: Hierdie mini-werkstuk illustreer die gebruik van Excel 2000 in die veld van simulasie. Die beginsels van toustaan modelle word gedek, asook die tipiese resultate. Die simulasiemodel modelleer en toets verskillende toustaan scenarios. Toevoere kan verander word na gelang van die gebruiker se keuse. Die resultate kan ontleed word om die optimale toustaan omgewing te bepaal.

Data fusion in wireless sensor networks can improve the performance of a network by eliminating redundancy and power consumption, ensuring fault-tolerance between sensors, and managing e®ectively the available com- munication bandwidth between network components. This thesis considers a data fusion approach applied to wireless sensor networks based on fuzzy logic theory. In particular, a cluster-based hierarchical design in wire- less sensor networks is explored combined with two data fusion methods based on fuzzy logic theory. A data fusion algorithm is presented and tested using Mamdani and Tsukamoto fuzzy inference methods. In addition, a concept related to the appropriate queuing models is presented based on classical queuing theory. Results show that the Mamdani method gives better results than the Tsukamoto approach for the two implementations considered. We noted that the proposed algorithm requires low processing and computational power. As a result, it can be applied to WSNs to provide optimal data fusion and ensures maximum sensor lifetime and minimum time delay.

L'objectif principal de cette thèse consiste à apporter une contribution méthodologique à la gestion de la sûreté et de coût de la sûreté aéroportuaire. Nous avons proposé un modèle logique du système de contrôle du flux des passagers au départ dans un aéroport. La finalité de ce modèle a permis de tester différents scénarios d'attaque du système, d'analyser le comportement du système dans ces conditions et d'en évaluer la perméabilité. Nous nous sommes ensuite intéressé à l'évaluation du système de contrôle des flux de passagers à l'embarquement au travers d'une approche probabiliste. Ceci conduit à la formulation de problèmes d'optimisation permettant d'améliorer les performances du système de contrôle. Afin d'obtenir la modélisation mathématique des flux de passagers au départ dans une aérogare, nous avons introduit les facteurs temps et espace par rapport au modèle précédent afin de le rendre plus proche de l'opérationnel. Enfin, nous nous sommes intéressés à l'optimisation des affectations des ressources matérielles et humaines destinées au contrôle du trafic de passagers. Le modèle spatio-temporel développé précédemment est mis à profit pour quantifier de façon dynamique, l'attribution des ressources matérielles et humaines au niveau de l'inspection filtrage et surtout d'améliorer la qualité de service. Beaucoup reste à faire dans ce domaine et le développement d'outils de modélisation, d'analyse et d'aide à la décision tels que ceux qui ont été esquissés dans ce mémoire semble s'imposer pour assurer l'optimisation de l'affectation des ressources de la sûreté aéroportuaire et ainsi garantir non seulement la qualité du service de contrôle mais aussi le niveau de coûts en résultant. / Since the tragic events of September 11, aviation security is jeopardized. Many measures were taken both from the standpoint of improved procedures for improving the performance of security officers and equipment safety. Despite the implementation of new procedures and new measures, many events have shaken the airport security system established by ICAO, these include, the latest of which is the attempt acts of unlawful interference in December 2009. The main objective of this thesis is to contribute to methodological constraints security management and cost of airport security. To fight effectively against illegal acts, the standard 4.4.1 of Schedule 17 to the Chicago Convention states: “Each Contracting State shall establish measures to ensure that passengers from flights of commercial air transport and their cabin baggage are subjected to screened before boarding an aircraft departing from an area of security restricted”. The security check is then one of the highlights of airport security. We therefore propose a model system logic to control the flow of departing passengers at an airport. The purpose of this model was used to test different scenarios of attack system, analyze system behavior under these conditions and to assess permeability. We are then interested in evaluating the system of controlling the flow of passengers boarding through a probabilistic approach. This then leads to the formulation of optimization problems to improve the performance of the control system. It is then possible to establish operational procedures leading to improved system performance of passenger screening. To obtain the mathematical modeling of flow of departing passengers in a terminal, we introduced the factors of time and space relative to the previous model to make it closer to the operational. In this model, which adopts a network structure to describe the process and the transfer of passengers between the terminal sites, in particular allows to represent queues and waiting times inflicted on passengers. Finally, we are interested in optimizing the allocation of human and material resources for the control of passenger traffic. The spatio-temporal model developed previously is used to quantify dynamically allocating human and material resources at the security check and especially to improve the quality of service. This optimization allows us to formulate effective policies to manage the short term. Finally, modeling the performance of safety was performed according to a probabilistic point of view and then a dynamic perspective and space. In both cases the optimization problems were formulated based on the determination of operational parameters to improve system performance. Much remains to be done in this area and the development of tools for modeling, analysis and decision support such as those outlined in this paper seems to be necessary to ensure optimal allocation resources for airport security and so ensure not only quality service but also control the level of the resulting costs.

Effective aeromedical evacuation of casualties is one of the most important problems in military medical systems because high-priority casualties will not survive without timely medical care. The decision making process for aeromedical evacuation consists of the following components: (1) identifying which aeromedical evacuation asset (see figure 1) to dispatch to the casualty, (2) locating aeromedical evacuation assets strategically in anticipation of incoming demand, and (3) deciding which medical treatment facility to transport the casualty. These decisions are further complicated because prioritization of casualties is based on severity of injury while aeromedical evacuation assets and medical treatment facilities operate with varying capabilities. In this dissertation, discrete optimization models are developed to examine dispatch, delivery, and location logistics for the effective aeromedical evacuation of casualties in military medical systems.