Performance Evaluation of Flexible Manufacturing Systems with Finite Local Buffers: Fixed and Dynamic Routings

This article evaluates the performance of flexible manufacturing systems with finite local buffers and fixed or dynamic routing rules, and addresses the optimal design or system configuration problem of maximizing the system throughput. The costs include machine cost, part (or pallet) cost, and local buffers cost. First, the system throughputs and their behaviors are considered with both queueing network analysis and simulation, and it is shown for a fixed routing model that the system throughput in the case of finite local buffers is greater than in the case of infinite local buffers. For a fixed versus dynamic routing rule, it is also found that the throughput in the former case can be close to the one in the latter case by changing the setting parameters. Next, the design problems of maximizing the system throughput are considered numerically for fixed and dynamic routing cases. Then, it is seen that better combination of design variables is a class of the monotonicity in local buffers, service rates, and routing probabilities.     

Performance Analysis of Flexible Manufacturing Systems with a Single Discrete Material-Handling Device

We present an analytical model for performance prediction of flexible manufacturing systems (FMSs) with a single discrete material-handling device (MHD). This configuration of FMS is significant for many reasons: it is commonly found in industry, it simplifies material-handling control, it is amenable to analytical modeling, and it forms a building block for more complex systems. Standard queueing models are inadequate to analyze this configuration because of the need to take into consideration many nontrivial issues such as state-dependent routing, interference from the MHD, and the analysis of the MHD. To account for state-dependent routing, we develop an iterative method that is built around mean value analysis. To analyze the MHD interference, we use two queueing network models. In the first, we ignore queueing at the MHD but model the interference from the MHD by inflating the station service times. The second network models the queueing for the MHD and estimates the blocking (inflation) times needed for the first model. By iterating between the two networks, we are able to predict the performance of this configuration of FMS. Our analytical estimates are validated against discrete event simulation and shown to be quite accurate for initial system design.     

Modeling,analysis and simulation of ant-based network routing protocols

Using the metaphor of swarm intelligence, ant-based routing protocols deploy control packets that behave like ants to discover and optimize routes between pairs of nodes. These ant-based routing protocols provide an elegant, scalable solution to the routing problem for both wired and mobile ad hoc networks. The routing problem is highly nonlinear because the control packets alter the local routing tables as they are routed through the network. We mathematically map the local rules by which the routing tables are altered to the dynamics of the entire networks. Using dynamical systems theory, we map local protocol rules to full network performance, which helps us understand the impact of protocol parameters on network performance. In this paper, we systematically derive and analyze global models for simple ant-based routing protocols using both pheromone deposition and evaporation. In particular, we develop a stochastic model by modeling the probability density of ants over the network. The model is validated by comparing equilibrium pheromone levels produced by the global analysis to results obtained from simulation studies. We use both a Matlab simulation with ideal communications and a QualNet simulation with realistic communication models. Using these analytic and computational methods, we map out a complete phase diagram of network behavior over a small multipath network. We show the existence of both stable and unstable (inaccessible) routing solutions having varying properties of efficiency and redundancy depending upon the routing parameters. Finally, we apply these techniques to a larger 50-node network and show that the design principles acquired from studying the small model network extend to larger networks.     

Comparison of three flow line layouts with unreliable machines and profit maximization

Manufacturing system design is a complex challenge when a new factory is being built. Although some factories produce the same product, the layouts of the factories may be different. Manufacturing systems for automotive engines can be modelled with several types of queueing networks with finite buffers and unreliable machines. In this paper, three types of layout structures which are commonly used in automotive engine shops are compared with respect to maximizing profit that is determined by throughput and the investment cost of buffers. We assume that the service times are constant but inhomogeneous, and the time to failure and the time to repair are exponentially distributed. To solve this problem we used approximation methods which are based on aggregation and overlapping decomposition for computing performance measures, and a gradient search method for finding an optimal buffer allocation.     

Intervention in a family of Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is a collection of Boolean networks in which the gene state vector transitions according to the rules of one of the constituent networks and where network choice is governed by a selection distribution. The theory of automatic control has been applied to find optimal strategies for manipulating external control variables that affect the transition probabilities to desirably affect dynamic evolution over a finite time horizon. In this paper we treat a case in which we lack the governing probability structure for Boolean network selection, so we simply have a family of Boolean networks, but where these networks possess a common attractor structure. This corresponds to the situation in which network construction is treated as an ill-posed inverse problem in which there are many Boolean networks created from the data under the constraint that they all possess attractor structures matching the data states, which are assumed to arise from sampling the steady state of the real biological network. RESULTS: Given a family of Boolean networks possessing a common attractor structure composed of singleton attractors, a control algorithm is derived by minimizing a composite finite-horizon cost function that is a weighted average over all the individual networks, the idea being that we desire a control policy that on average suits the networks because these are viewed as equivalent relative to the data. The weighting for each network at any time point is taken to be proportional to the instantaneous estimated probability of that network being the underlying network governing the state transition. The results are applied to a family of Boolean networks derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation. AVAILABILITY: The software is available on request. SUPPLEMENTARY INFORMATION: The supplementary Information is available at http://ee.tamu.edu/~edward/tree     

TripNet: A Method for Constructing Rooted Phylogenetic Networks from Rooted Triplets

The problem of constructing an optimal rooted phylogenetic network from an arbitrary set of rooted triplets is an NP-hard problem. In this paper, we present a heuristic algorithm called TripNet, which tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes from an arbitrary set of rooted triplets. Despite of current methods that work for dense set of rooted triplets, a key innovation is the applicability of TripNet to non-dense set of rooted triplets. We prove some theorems to clarify the performance of the algorithm. To demonstrate the efficiency of TripNet, we compared TripNet with SIMPLISTIC. It is the only available software which has the ability to return some rooted phylogenetic network consistent with a given dense set of rooted triplets. But the results show that for complex networks with high levels, the SIMPLISTIC running time increased abruptly. However in all cases TripNet outputs an appropriate rooted phylogenetic network in an acceptable time. Also we tetsed TripNet on the Yeast data. The results show that Both TripNet and optimal networks have the same clustering and TripNet produced a level-3 network which contains only one more reticulation node than the optimal network.     

Batch sizes and lead-time performance in flexible manufacturing systems

Production lead-time performance in flexible manufacturing systems is influenced by several factors which include: machine groupings, demand rates, machine processing rates, product batching, material handling system capacity, and so on. Hence, control of lead-time performance can be affected through the manipulation of one or more of these variables. In this article, we investigate the potential of batch sizing as a control variable for lead-time performance through the use of a queueing network model. We establish a functional relationship between the two variables, and incorporate the relationship in an optimization model to determine the optimal batch size(s) which minimizes the sum of annual work-in-process inventory and final inventory costs. The nonlinear batch sizing problem which results is solved by discrete optimization via marginal analysis. Results show that batch sizing can be a cheap and effective variable for controlling flexible manufacturing system throughput.     

Ongoing Processes in a Fitness Network Model under Restricted Resources

In real networks, the resources that make up the nodes and edges are finite. This constraint poses a serious problem for network modeling, namely, the compatibility between robustness and efficiency. However, these concepts are generally in conflict with each other. In this study, we propose a new fitness-driven network model for finite resources. In our model, each individual has its own fitness, which it tries to increase. The main assumption in fitness-driven networks is that incomplete estimation of fitness results in a dynamical growing network. By taking into account these internal dynamics, nodes and edges emerge as a result of exchanges between finite resources. We show that our network model exhibits exponential distributions in the in- and out-degree distributions and a power law distribution of edge weights. Furthermore, our network model resolves the trade-off relationship between robustness and efficiency. Our result suggests that growing and anti-growing networks are the result of resolving the trade-off problem itself.     

Algorithms for energy efficient mobile object tracking in wireless sensor networks

Wireless sensor networks have found more and more applications in a variety of pervasive computing environments, in their functions as data acquisition in pervasive applications. However, how to get better performance to support data acquisition of pervasive applications over WSNs remains to be a nontrivial and challenging task. The network lifetime and application requirement are two fundamental, yet conflicting, design objectives in wireless sensor networks for tracking mobile objects. The application requirement is often correlated to the delay time within which the application can send its sensing data back to the users in tracking networks. In this paper we study the network lifetime maximization problem and the delay time minimization problem together. To make both problems tractable, we have the assumption that each sensor node keeps working since it turns on. And we formulate the network lifetime maximization problem as maximizing the number of sensor nodes who don’t turn on, and the delay time minimization problem as minimizing the routing path length, after achieving the required tracking tasks. Since we prove the problems are NP-complete and APX-complete, we propose three heuristic algorithms to solve them. And we present several experiments to show the advantages and disadvantages referring to the network lifetime and the delay time among these three algorithms on three models, random graphs, grids and hypercubes. Furthermore, we implement the distributed version of these algorithms.     

A general mathematical performance model for wormhole-switched irregular networks

Irregular topologies are desirable network structures for building scalable cluster systems and very recently they have also been employed in SoC (system-on-chip) design. Many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube, torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the aforementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.     

Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs

In this paper, we consider the problem of scheduling divisible loads on arbitrary graphs with the objective to minimize the total processing time of the entire load submitted for processing. We consider an arbitrary graph network comprising heterogeneous processors interconnected via heterogeneous links in an arbitrary fashion. The divisible load is assumed to originate at any processor in the network. We transform the problem into a multi-level unbalanced tree network and schedule the divisible load. We design systematic procedures to identify and eliminate any redundant processor–link pairs (those pairs whose consideration in scheduling will penalize the performance) and derive an optimal tree structure to obtain an optimal processing time, for a fixed sequence of load distribution. Since the algorithm thrives to determine an equivalent number of processors (resources) that can be used for processing the entire load, we refer to this approach as resource-aware optimal load distribution (RAOLD) algorithm. We extend our study by applying the optimal sequencing theorem proposed for single-level tree networks in the literature for multi-level tree for obtaining an optimal solution. We evaluate the performance for a wide range of arbitrary graphs with varying connectivity probabilities and processor densities. We also study the effect of network scalability and connectivity. We demonstrate the time performance when the point of load origination differs in the network and highlight certain key features that may be useful for algorithm and/or network system designers. We evaluate the time performance with rigorous simulation experiments under different system parameters for the ease of a complete understanding.     

Learning Bayesian network classifiers using ant colony optimization

Bayesian networks are knowledge representation tools that model the (in)dependency relationships among variables for probabilistic reasoning. Classification with Bayesian networks aims to compute the class with the highest probability given a case. This special kind is referred to as Bayesian network classifiers. Since learning the Bayesian network structure from a dataset can be viewed as an optimization problem, heuristic search algorithms may be applied to build high-quality networks in medium- or large-scale problems, as exhaustive search is often feasible only for small problems. In this paper, we present our new algorithm, ABC-Miner, and propose several extensions to it. ABC-Miner uses ant colony optimization for learning the structure of Bayesian network classifiers. We report extended computational results comparing the performance of our algorithm with eight other classification algorithms, namely six variations of well-known Bayesian network classifiers, cAnt-Miner for discovering classification rules and a support vector machine algorithm.     

Intervention in context-sensitive probabilistic Boolean networks

MOTIVATION: Intervention in a gene regulatory network is used to help it avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is essentially a finite collection of Boolean networks in which at any discrete time point the gene state vector transitions according to the rules of one of the constituent networks. For an instantaneously random PBN, the governing Boolean network is randomly chosen at each time point. For a context-sensitive PBN, the governing Boolean network remains fixed for an interval of time until a binary random variable determines a switch. The theory of automatic control has been previously applied to find optimal strategies for manipulating external (control) variables that affect the transition probabilities of an instantaneously random PBN to desirably affect its dynamic evolution over a finite time horizon. This paper extends the methods of external control to context-sensitive PBNs. RESULTS: This paper treats intervention via external control variables in context-sensitive PBNs by extending the results for instantaneously random PBNs in several directions. First, and most importantly, whereas an instantaneously random PBN yields a Markov chain whose state space is composed of gene vectors, each state of the Markov chain corresponding to a context-sensitive PBN is composed of a pair, the current gene vector occupied by the network and the current constituent Boolean network. Second, the analysis is applied to PBNs with perturbation, meaning that random gene perturbation is permitted at each instant with some probability. Third, the (mathematical) influence of genes within the network is used to choose the particular gene with which to intervene. Lastly, PBNs are designed from data using a recently proposed inference procedure that takes steady-state considerations into account. The results are applied to a context-sensitive PBN derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation, since the available data suggest that disruption of this influence could reduce the chance of a melanoma metastasizing.     

An autonomic routing framework for sensor networks

Current routing services for sensor networks are often designed for specific applications and network conditions, thus have difficulty in adapting to application and network dynamics. This paper proposes an autonomic framework to promote the adaptivity of routing services in sensor networks. The key idea of this framework is to maintain some feature functions that are decoupled from originally-integrated routing services. This separation enables significant service changes to be done by only tuning these functions. Measures including parameterization are taken to save the energy for changing these functions. Further, this framework includes a monitoring module to support a policy-based collaborative adaptation. This paper shows an example autonomic routing service conforming to this framework. Some of this work was done while the author was at ISI     

Capacity optimization of flexible manufacturing systems under budget constraints

The capacity of a flexible manufacturing system (FMS) is optimized with the objective to maximize the system's throughput, while a budget constraint is considered. Decisions are performed on the capacity of machine groups (sets of identical machines), the transportation system and, in case of a significant cost impact, the number of pallets in the system. Throughput evaluation is achieved either by an open finite queueing network or by a closed queueing network if the number of pallets is included in the decision process. For both cases the solution procedure is based on the marginal allocation scheme.     

Decreasing-Rate Pruning Optimizes the Construction of Efficient and Robust Distributed Networks

Robust, efficient, and low-cost networks are advantageous in both biological and engineered systems. During neural network development in the brain, synapses are massively over-produced and then pruned-back over time. This strategy is not commonly used when designing engineered networks, since adding connections that will soon be removed is considered wasteful. Here, we show that for large distributed routing networks, network function is markedly enhanced by hyper-connectivity followed by aggressive pruning and that the global rate of pruning, a developmental parameter not previously studied by experimentalists, plays a critical role in optimizing network structure. We first used high-throughput image analysis techniques to quantify the rate of pruning in the mammalian neocortex across a broad developmental time window and found that the rate is decreasing over time. Based on these results, we analyzed a model of computational routing networks and show using both theoretical analysis and simulations that decreasing rates lead to more robust and efficient networks compared to other rates. We also present an application of this strategy to improve the distributed design of airline networks. Thus, inspiration from neural network formation suggests effective ways to design distributed networks across several domains.     

Optimal link removal for epidemic mitigation: a two-way partitioning approach

The structure of the contact network through which a disease spreads may influence the optimal use of resources for epidemic control. In this work, we explore how to minimize the spread of infection via quarantining with limited resources. In particular, we examine which links should be removed from the contact network, given a constraint on the number of removable links, such that the number of nodes which are no longer at risk for infection is maximized. We show how this problem can be posed as a non-convex quadratically constrained quadratic program (QCQP), and we use this formulation to derive a link removal algorithm. The performance of our QCQP-based algorithm is validated on small Erd?s–Renyi and small-world random graphs, and then tested on larger, more realistic networks, including a real-world network of injection drug use. We show that our approach achieves near optimal performance and out-performs other intuitive link removal algorithms, such as removing links in order of edge centrality.     

On the performance of single-layered neural networks

This paper studies the performance of single-layered neural networks. This study begins with the performance of single-layered neural networks trained using the outer-product rule. The outer-product rule is a suboptimal learning scheme, resulting under certain assumptions from optimal least-squares training of single-layered neural networks with respect to their analog output. Extensive analysis reveals the improvement on the network performance caused by its optimal least-squares training. The effect of the training scheme on the performance of single-layered neural networks with binary output is exhibited by experimentally comparing the performance of single-layered neural networks trained with respect to their analog and binary output.     

Resource Management for Ad-Hoc Wireless Networks with Cluster Organization

Boosted by technology advancements, government and commercial interest, ad-hoc wireless networks are emerging as a serious platform for distributed mission-critical applications. Guaranteeing QoS in this environment is a hard problem because several applications may share the same resources in the network, and mobile ad-hoc wireless networks (MANETs) typically exhibit high variability in network topology and communication quality. In this paper we introduce DYNAMIQUE, a resource management infrastructure for MANETs. We present a resource model for multi-application admission control that optimizes the application admission utility, defined as a combination of the QoS satisfaction ratio. A method based on external adaptation (shrinking QoS for existing applications and later QoS expansion) is introduced as a way to reduce computation complexity by reducing the search space. We designed an application admission protocol that uses a greedy heuristic to improve application utility. For this, the admission control considers network topology information from the routing layer. Specifically, the admission protocol takes benefit from a cluster network organization, as defined by ad-hoc routing protocols such as CBRP and LANMAR. Information on cluster membership and cluster head elections allows the admission protocol to minimize control signaling and to improve application quality by localizing task mapping.