No description available.

This thesis considers probabilistic supervisory control of probabilistic discrete event systems (PDES). PDES are modeled as generators of probabilistic languages. The probabilistic supervisors employed are a generalization of the deterministic ones previously employed in the literature. At any state, the supervisor enables/disables events with certain probabilities. The probabilistic supervisory control problem (PSCP) that has previously been considered in the literature is revisited: find, if possible, a supervisor under whose control the behavior of a plant is identical to a given probabilistic specification. The existing results are unified, complemented with a solution of a special case and the computational analysis of synthesis problem and the solution. The central place in the thesis is given to the solution of the optimal probabilistic supervisory control problem (OPSCP) in the framework: if the conditions for the existence of probabilistic supervisor for PSCP problem are not satisfied, find a probabilistic supervisor such that the achievable behaviour is as close as possible to the desired behaviour. The proximity is measured using the concept of pseudometric on states of generators. The distance between two systems is defined as the distance in the pseudometric between the initial states of the corresponding generators. The pseudometric is adopted from the research in formal methods community and is defined as the greatest fixed point of a monotone function. Starting from this definition, we suggest two algorithms for finding the distances in the pseudometric. Further, we give a logical characterization of the same pseudometric such that the distance between two systems is measured by a formula that distinguishes between the systems the most. A trace characterization of the pseudometric is then derived from the logical characterization by which the pseudometric measures the difference of (appropriately discounted) probabilities of traces and sets of traces generated by systems, as well as some more complicated properties of traces. Then, the solution to the optimal probabilistic supervisory control problem is presented. Further, the solution of the problem of approximation of a given probabilistic generator with another generator of a prespecified structure is suggested such that the new model is as close as possible to the original one in the pseudometric (probabilistic model fitting). The significance of the approximation is then discussed. While other applications are briefly discussed, a special attention is given to the use of ideas of probabilistic model fitting in the solution of a modified optimal probabilistic supervisory control problem. / Thesis / Doctor of Philosophy (PhD)

The purpose of this research was to quantify the impact of the log variables: length, grade, and scaling diameter, on the cost of producing hardwood lumber, using the activity-based costing technique. The usual technique of calculating hardwood lumber product costs is based upon traditional cost accounting, where manufacturing costs are allocated to the products based upon the volume of each product that is produced. With the traditional cost accounting procedure, the variation in the resources used to process the logs is not taken into consideration. As a result, when the cost to manufacture the products is subtracted from the market value of the products, the resulting profit levels of the products may not be truly representative of the actual resources consumed in manufacturing the product. Using discrete-event simulation, two hardwood sawmills were modeled and a series of experiments were conducted which would not have been feasible to conduct on the mill floors. Results from the simulation experiments illustrated that the activity-based and traditional cost accounting techniques allocated different amounts of manufacturing costs to the products. The largest difference between the two cost accounting techniques was found to be the amount of raw material costs allocated to the products. For one of the sawmills modeled, log grade was identified as having the greatest influence on determining product costs and total manufacturing costs. Results from the model of the second sawmill however demonstrated that log diameter had a greater impact on determining product costs and total manufacturing costs. The commonality of the results from the two simulation models was that the differences in the volume of lumber produced, between the logs that were studied, was a critical component in determining which log parameter had the most effect on changing the dynamics of the sawmill system. To enable hardwood managers a more precise method of allocating raw material costs to the lumber products, a methodology was developed that uses the principles of activity-based costing to allocate raw material costs. The proposed methodology, termed the lumber yield method, uses lumber yield values from logs with similar characteristics to allocate raw material costs to the lumber products. Analysis of the output from the simulation models illustrated that with the lumber yield method, the amount of raw material costs allocated to the products was not significantly different than the amount allocated by the activity-based costing method. The calculated raw material costs of the products were however, found to be significantly different between the lumber yield method and the traditional volume costing method. / Ph. D.

Advances in computing and communication technologies are blurring the distinction between today's PCs and mobile phones. With expected smart phones sales to skyrocket, lack of awareness regarding securing them, and access to personal and proprietary information, has resulted in the recent surge of mobile malware. In addition to using traditional social-engineering techniques such as email and file-sharing, malware unique to Bluetooth, Short Messaging Service (SMS) and Multimedia Messaging Service (MMS) messages are being used. Large scale simulations of malware on wireless networks have becomes important and studying them under realistic device deployments is important to obtain deep insights into their dynamics and devise ways to control them. In this dissertation, we present EpiNet: an individual-based scalable high-performance oriented modeling environment for simulating the spread of mobile malware over large, dynamic networks. EpiNet can be used to undertake comprehensive studies during both planning and response phase of a malware epidemic in present and future generation wireless networks. Scalability is an important design consideration and the current EpiNet implementation can scale to 3-5 million device networks and case studies show that large factorial designs on million device networks can be executed within a day on 100 node clusters. Beyond compute time, EpiNet has been designed for analysts to easily represent a range of interventions and evaluating their efficacy. The results indicate that Bluetooth malware with very low initial infection size will not result in a major wireless epidemic. The dynamics are dependent on the network structure and, activity-based mobility models or their variations can yield realistic spread dynamics. Early detection of the malware is extremely important in controlling the spread. Non-adaptive response strategies using static graph measures such as degree and betweenness are not effective. Device-based detection mechanisms provide a much better means to control the spread and only effective when detection occurs early on. Automatic signature generation can help in detecting newer strains of the malware and signature distributions through a central server results in better control of the spread. Centralized dissemination of patches are required to reach a large proportion of devices to be effective in slowing the spread. Non-adaptive dynamic graph measures such as vulnerability are found to be more effective. Our studies of SMS and hybrid malware show that SMS-only malware spread slightly faster than Bluetooth-only malware and do not spread to all devices. Hybrid malware spread orders of magnitude faster than either SMS-only or Bluetooth-only malware and can cause significant damage. Bluetooth-only malware spread faster than SMS-only malware in cases where density of devices in the proximity of an infected device is higher. Hybrid malware can be much more damaging than Bluetooth-only or SMS-only malware and we need mechanisms that can prevent such an outbreak. EpiNet provide a means to propose, implement and evaluate the response mechanisms in realistic and safe settings. / Ph. D.

Yes / Competition in the manufacturing industry is growing at an accelerated rate due to globalization trend. This global competition urges manufacturing organizations to review and improve their processes in order to enhance and maintain their competitive advantage. One of those initiatives is the implementation of the Six Sigma methodology to analyze and reduce variation hence improving the processes of manufacturing organizations. This paper presents a Discrete Event Simulation methodology to support a Six Sigma approach for manufacturing organizations. Several approaches to implement Six Sigma focus on improving time management and reducing cycle time. However, these efforts may fail in their effective and practical implementation to achieve the desired results. Following the proposed methodology, a Discrete Event Simulation model was built to assist decision makers in understanding the behavior of the current manufacturing process. This approach helps to systematically define, measure and analyze the current state process to test different scenarios to improve performance. The paper is amongst the first to offer a simulation methodology to support a process improvement approach. It applies an action research strategy to develop and validate the proposed modelling methodology in a British manufacturing organization competing in global markets.

Realistic mobility and cellular traffic modeling is key to various wireless networking applications and have a significant impact on network performance. Planning and design, network resource allocation and performance evaluation in cellular networks require realistic traffic modeling. We propose a Discrete Event Simulation framework, Diamond - (Discrete Event Simulation of Mobility and Spatio-Temporal Spectrum Demand) to model and analyze realistic activity based mobility and spectrum demand patterns. The framework can be used for spatio-temporal estimation of load, in deciding location of a new base station, contingency planning, and estimating the resilience of the existing infrastructure. The novelty of this framework lies in its ability to capture a variety of complex, realistic and dynamically changing events effectively. Our initial results show that the framework can be instrumental in contingency planning and dynamic spectrum allocation. / Master of Science

Discrete event simulation is an important tool for modeling and analysis. Some of the simulation applications such as telecommunication network performance, VLSI logic circuits design, battlefield simulation, require enormous amount of computing resources. One way to satisfy this demand for computing power is to decompose the simulation system into several logical processes (Ip) and run them concurrently. In any parallel discrete event simulation (PDES) system, the events are ordered according to their time of occurrence. In order for the simulation to be correct, this ordering has to be preserved. There are three approaches to maintain this ordering. In a conservative system, no lp executes an event unless it is certain that all events with earlier time-stamps have been executed. Such systems are prone to deadlock. In an optimistic system on the other hand, simulation progresses disregarding this ordering and saves the system states regularly. Whenever a causality violation is detected, the system rolls back to a state saved earlier and restarts processing after correcting the error. There is another approach in which all the lps participate in the computation of a safe time-window and all events with time-stamps within this window are processed concurrently. In optimistic simulation systems, there is a global virtual time (GVT), which is the minimum of the time-stamps of all the events existing in the system. The system can not rollback to a state prior to GVT and hence all such states can be discarded. GVT is used for memory management, load balancing, termination detection and committing of events. However, GVT computation introduces additional overhead. In optimistic systems, large number of rollbacks can degrade the system performance considerably. We have studied the effect of load balancing in reducing the number of rollbacks in such systems. We have designed three load balancing algorithms and implemented two of them on a network of workstations. The other algorithm has been analyzed probabilistically. The reason for choosing network of workstations is their low cost and the availability of efficient message passing softwares like PVM and MPI. All of these load balancing algorithms piggyback on the existing GVT computation algorithms and try to balance the speed of simulation in different lps. We have also designed an optimal GVT computation algorithm for the hypercubes and studied its performance with respect to the other GVT computation algorithms by simulating a hypercube in our network cluster. We use the topological properties of a star network in order to design an algorithm for computing a safe time-window for parallel discrete event simulation. We have analyzed and simulated the behavior of an open queuing network resembling such an architecture. Our algorithm is also extended for hierarchical stars and for recursive window computation.

No description available.

The objective of this dissertation is to introduce a unified framework for modeling and simulating discrete event logistics systems (DELS) by using a formal language, the System Modeling Language (SysML), for conceptual modeling and a corresponding methodology for translating the conceptual model into a simulation model. There are three parts in this research: plant modeling, control modeling, and simulation generation. Part 1:Plant Modeling of Discrete Event Logistics Systems. Contemporary DELS are complex and challenging to design. One challenge is to describe the system in a formal language. We propose a unified framework for modeling DELS using SysML. A SysML subset for plant modeling is identified in this research. We show that any system can be described by using the proposed subset if the system can be modeled using finite state machines or finite state automata. Furthermore, the system modeled by the proposed subset can avoid the state explosion problem, i.e., the number of the system states grows exponentially when the number of the components increases. We also compare this approach to other existing modeling languages. Part 2:Control Modeling of Discrete Event Logistics Systems. The development of contemporary manufacturing control systems is an extremely complex process. One approach for modeling control systems uses activity diagrams from SysML, providing a standard object-oriented graphical notation and enhancing reusability. However, SysML activity diagrams do not directly support the kind of analysis needed to verify the control model, such as might be available with a Petri net (PN) model. We show that a control model represented by UML/SysML activity diagrams can be transformed into an equivalent PN, so the analysis capability of PN can be used and the results applied back in the activity diagram model. We define a formal mathematical notation for activity diagrams, show the mapping rules between PN and activity diagrams, and propose a formal transformation algorithm. Part 3:Discrete Event Simulation Generation. The challenge of cost-effectively creating discrete event simulation models is well-known. One approach to alleviate this issue is to describe a system using a descriptive modeling language and then transform the system model to a simulation model. Some researchers have tried to realize this idea using a transformation script. However, most of the transformation approaches depend on a domain specific language, so extending the domain specific language may require modifying the transformation script. We propose a transformation approach from SysML to a simulation language. We show that a transformation script can be independent of the associated domain specific language if the domain specific language is implemented as domain libraries using a proposed SysML subset. In this case, both the domain library and the system model can be transformed to a target simulation language. We demonstrate a proof-of-concept example using AnyLogic as the target simulation language.

Distributed Discrete Event Simulation (DDES) has received much attention in recent years, owing to the fact that uniprocessor based serial simulations may require excessive amount of simulation time and computational resources. It is therefore natural to attempt to use multiple processors to exploit the inherent parallelism in discrete event simulations in order to speed up the simulation process. In this dissertation we study the performance of distributed simulation of queueing networks, by analysing queueing models of message flows in distributed discrete event simulators. Most of the prior work in distributed discrete event simulation can be catego­rized as either empirical studies or analytic (or formal) models. In the empirical studies, specific experiments are run on both conservative and optimistic simulators to see which strategy results in a faster simulation. There has also been increasing activity in analytic models either to better understand a single strategy or to compare two strategies. Little attention seems to have been paid to the behaviour of the interprocessor message queues in distributed discrete event simulators. To begin with, we study how to model distributed simulators of queueing networks. We view each logical process in a distributed simulation as comprising a message sequencer with associated message queues, followed by an event processor. A major contribution in this dissertation is the introduction of the maximum lookahead sequencing protocol. In maximum lookahead sequencing, the sequencer knows the time-stamp of the next message to arrive in the empty queue. Maximum lookahead is an unachievable algorithm, but is expected to yield the best throughput compared to any realisable sequencing technique. The analysis of maximum lookahead, therefore, should lead to fundamental limits on the performance of any sequencing algorithm We show that, for feed forward type simulators, with standard stochastic assump-tions for message arrival and time-stamp processes, the message queues are unstable for conservative sequencing, and for conservative sequencing with maximum lookahead and hence for optimistic resequencing, and for any resequencing algorithm that does not employ interprocessor "flow control". It follows that the resequencing problem is fundamentally unstable and some form of interprocessor flow control is necessary in order to make the message queues stable (without message loss). We obtain some generalizations of the insta­bility results to time-stamped message arrival processes with certain ergodicity properties. For feedforward type distributed simulators, we study the throughput of the event sequencer without any interprocessor flow control. We then incorporate flow control and study the throughput of the event sequencer. We analyse various flow control mechanisms. For example, we can bound the buffers of the message queues, or various logical processes can be prevented from getting too far apart in virtual time by means of a mechanism like Moving Time Windows or Bounded Lag. While such mechanisms will serve to stabilize buffers, our approach, of modelling and analysing the message flow processes in the simulator, points towards certain fundamental limits of efficiency of distributed simulation, imposed by the synchronization mechanism. Next we turn to the distributed simulation of more general queueing networks. We find an upper bound to the throughput of distributed simulators of open and closed queueing networks. The upper bound is derived by using flow balance relations in the queueing network and in the simulator, processing speed constraints, and synchronization constraints in the simulator. The upper bound is in terms of parameters of the queueing network, the simulator processor speeds, and the way the queueing network is partitioned or mapped over the simulator processors. We consider the problem of choosing a mapping that maximizes the upper bound. We then study good solutions o! this problem as possible heuristics for the problem of partitioning the queueing network over the simulator processors. We also derive a lower bound to the throughput of the distributed simulator for a simple queueing network with feedback. We then study various properties of the maximum lookahead algorithm. We show that the maximum lookahead algorithm does not deadlock. Further, since there are no syn­chronization overheads, maximum lookahead is a simple algorithm to study. We prove that maximum lookahead sequencing (though unrealisable) yields the best throughput compared to any realisable sequencing technique. These properties make maximum lookahead a very useful algorithm in the study of distributed simulators of queueing networks. To investigate the efficacy of the partitioning heuristic, we perform a study of queue­ing network simulators. Since it is important to study the benefits of distributed simula­tion, we characterise the speedup in distributed simulation, and find an upper bound to the speedup for a given mapping of the queues to the simulator processors. We simulate distributed simulation with maximum lookahead sequencing, with various mappings of the queues to the processors. We also present throughput results foT the same mappings but using a distributed simulation with the optimistic sequencing algorithm. We present a num­ber of sufficiently complex examples of queueing networks, and compare the throughputs obtained from simulations with the upper bounds obtained analytically. Finally, we study message flow processes in distributed simulators of open queueing networks with feedback. We develop and study queueing models for distributed simulators with maximum lookahead sequencing. We characterize the "external" arrival process, and the message feedback process in the simulator of a simple queueing network with feedback. We show that a certain "natural" modelling construct for the arrival process is exactly correct, whereas an "obvious" model for the feedback process is wrong; we then show how to develop the correct model. Our analysis throws light on the stability of distributed simulators of queueing networks with feedback. We show how the stability of such simulators depends on the parameters of the queueing network.