A preliminary study of a diagonal channel-routing model

The layout of two-terminal nets in a VLSI channel is realized in a new diagonal channel-routing model (DCRM), where the tracks are segments respectively displayed at +45 ° and ?45 ° on the two layers of the channel. A new definition of channel density is introduced, and a lower bound to the channel width is derived by the application of an algorithm, whose complexity is evaluated as a function of the channel density, and other parameters of the problem. A simple linear-time algorithm is proposed, which produces an optimal layout (i.e., it requires a channel of minimum width) if the length of the longest net equals the lower bound for the channel width. In any case, the number of vias is at most one for each net. Some particular solutions are proposed for problems with long nets. Specific problems are much easier in DCRM than in the classical Manhattan model. For example, any shift-by-i can be realized in DCRM in a channel of widthi.     

Diagonal channel routing with vias at unit distance

We consider the «diagonal» channel routing model (DM), where the connections are laid in two layers, along tracks at +45° and ?45° respectively. A previous result [10] shows that, for a channel routing problem of density d, a DM layout exists with channel width w=2d. However, vias may appear at a distance 1/tr2. We prove here that another DM layout can be constructed with w-kd, k constant, and all vias at a distance ≥1. By a theoretical point of view this layout is superior to the one obtained in the classical Manhattan Model, in the worst case.     

Finding All Minimal Shapes in a Routing Channel

We present an algorithm to find a set of all optimal solutions for a channel placement problem. A channel consists of two rows of horizontal line segments (representing components). Each line segment contains some terminals with fixed positions. Sets of terminals, called nets, are to be connected. The relative ordering of line segments in each row is fixed. The line segments can be shifted left or right, which will affect the width needed for routing and the length of the channel. We want to find the tradeoff between channel length and routing width. Since the channel routing problem is NP-complete, we use a lower bound on routing width, called density. The density of a placement is the maximum number of nets crossing each vertical cut. We can increase the total length to minimize the channel density, or minimize the total length by increasing the channel density. The pair (density, total length) is called the shape of a placement. A shape is minimal if a decrease in density would cause an increase in total length, and vice versa. Our algorithm computes all the minimal shapes in O (N ⁴ ) time, where N is the number of nets. This is the first known algorithm for this problem whose running time is polynomial in the number of nets and independent of the length of the channel. Received January 18, 1996; revised December 2, 1996.     

Channel routing in a Diagonal Overlap model

In this paper we study the channel routing problem (CRP) in a new routing model, called Overlap Diagonal Model (ODM), where the grid consists of right and left tracks displayed at +45° and ?45°. For the unrestrictedoverlap, we present an algorithm which achieves \(w = \left[ {\frac{d}{2}} \right] + 1\) , while for the restricted-overlap, we havew=d+1, whered is the channel density,w is the channel width.     

基于请求应答方式消息传递机制有色Petri网模型

分布式系统的对等模型中,各个节点从功能上看是对等关系,相互之间进行消息的请求和响应。讨论了一种将广播请求和点到点应答两种通信方式相结合的消息传递机制FMPRR(Fast Message Passing based on Request Response mode)的实现,这种机制采用wormhole寻径流控策略。用有色Petri网来形式化描述和分析FMPRR,通过模型状态空间分析结果,对FMPRR消息传递机制进行验证。     

Optimal stationary behavior for a class of timed continuous Petri nets

In this paper, we consider a deterministic timed continuous Petri net model where conflicts at places are solved by using stationary routing parameters. We show how to compute the stationary firing rate for all transitions via linear programming, so as to determine the optimal routing parameters that maximize user-defined linear functions of the firing rates. Finally, we discuss the relations with discrete Petri nets.     

On the area of hypercube layouts

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N² nodes in the plane, in an N×N grid arrangement, uses ⌊2N/3⌋+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).     

A rule-based system for generating a ladder logic control program from a high-level systems model

In this article an interface between a high-level specification of a system and a logic controller of that system is developed. The interface is based on a number of rules to transform an IDEF0 specification into an intermediate-level Petri-net-based controller and to transform the intermediate specification into a ladder logic program which can be run on a PLC. These rules could be used as a basis for developing an expert system to handle the interface. Such an expert system provides an environment for rapid prototyping and analysis of controllers.     

Petri nets‐based model for the analysis of NORIA protocol

Network rOle‐based Routing Intelligent Algorithm is a novel routing algorithm for wireless sensor networks, which combine various effective techniques in order to reduce energy consumption and improve data routes. This algorithm uses role assignment for distributing tasks over the network nodes and fuzzy logic for making decisions. There is a clear need for the use of formal methods to validate the correctness of the protocols as well as performance and functionality prior to the deployment of such algorithms in a real environment. This paper presents a formal and rigorous study of Network rOle‐based Routing Intelligent Algorithm. Prioritised‐timed coloured petri nets (PTCPNs) have been chosen as an appropriate modelling language. In this way, PTCPNs have been used to describe complete and unambiguous specifications of system behaviour, whereas CPNTools is used to evaluate the correctness of the protocol using state space exploration and for performance evaluation using simulation. Copyright © 2015 John Wiley & Sons, Ltd.     

On the closure of the diagonal of a T1-space

Let X be a topological space. The closure of Δ={(x,x):xX} in X×X is a symmetric relation on X. We characterise those equivalence relations on an infinite set that arise as the closure of the diagonal with respect to a T₁-topology.     

Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

A simple Suboptimal siphon‐based control model of a well‐known S3PR

Siphon‐based deadlock control suffers from reaching fewer states than the maximally permissive one. We report an alternative control to reach the same good states as that based on the theory of regions, but with fewer monitors, by refining some monitors into several monitors with smaller controller regions. More states can be reached since the controller region is less disturbed by covering only a place in a subregion where only one place is marked at any reachable marking. Formal proof of the correctness is provided. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

一种新型大容量路由器交换网络中的高效路由策略

路由算法对交换网络性能具有很大的影响。本文针对一种新型的大容量路由器交换网络拓扑-XD（Cross-Direct）网络的特点,提出了一类和应用于传统直连网络中的基于简单维序路由算法具有相同网络性能的路由算法一对角矢量映射法（DVM）。该类算法分为两种,文中对这两种算法进行了详细描述和性能分析,给出了它们各自的应用场合。     

Energy-efficient routing based on vehicular consumption predictions of a mesoscopic learning model

This paper proposes an alternative approach for determining the most energy efficient route towards a destination. An innovative mesoscopic vehicular consumption model that is based on machine learning functionality is introduced and its application in a case study involving Fully Electric Vehicles (FEVs) is examined. The integration of this model in a routing engine especially designed for FEVs is also analyzed and a software architecture for implementing the proposed routing methodology is defined. In order to verify the robustness and the energy efficiency of this methodology, a system prototype has been developed and a series of field tests have been performed. The results of these tests are reported and significant conclusions are derived regarding the generated energy efficient routes.     

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

As a powerful analysis tool of Petri nets, reachability trees are fundamental for systematically investigating many characteristics such as boundedness, liveness and reversibility. This work proposes a method to generate a reachability tree, called ωRT for short, for a class of unbounded generalized nets called ω-independent nets based on new modified reachability trees (NMRTs). ωRT can effectively decrease the number of nodes by removing duplicate and ω-duplicate nodes in the tree, and verify properties such as reachability, liveness and deadlocks. Two examples are provided to show its superiority over NMRTs in terms of tree size.      

Developing a supply chain disruption analysis model: Application of colored Petri-nets

As a result of globalization in the past two decades, supply chains are encountering more unknown conditions and risks. One important category of risks is disruptions that block material flowing through a supply chain and that may even result in end-product manufacturing failure. This paper uses a Petri nets-based model as a tool to understand the dissemination of disruptions and to trace the operational performance of a supply chain. The presented approach models how changes propagate through a supply chain and calculates the impact of disruptions on supply chain attributes by concluding the states that are obtainable from a given initial status in the supply chain.     

Experimental study of diffusion-based extraction from a cell suspension

A recently proposed application of microfluidics is the post-thaw processing of biological cells. Numerical simulations suggest that diffusion-based extraction of the cryoprotective agent dimethyl sulfoxide (DMSO) from blood cells is viable and more efficient than centrifugation, the conventional method of DMSO removal. In order to validate the theoretical model used in these simulations, a prototype was built and the flow of two parallel streams, a suspension of Jurkat cells containing DMSO and a wash stream that contained neither cells nor DMSO, was characterized experimentally. DMSO transport in a rectangular channel (depth 500 μm, width 25 mm and overall length 125 mm) was studied as a function of three dimensionless parameters: depth ratio of the streams, cell volume fraction in the cell solution, and the Peclet number (Pe) based on channel depth, average flow rate and the diffusion coefficient for DMSO in water. In our studies, values of Pe ranged from O(10³) to O(10⁴). Laminar flow was ensured by keeping the Reynolds number between O(1) and O(10). Experimental results based on visual and quantitative data demonstrate conclusively that a microfluidic device can effectively remove DMSO from liquid and cell laden streams without compromising cell recovery. Also, flow conditions in the microfluidic device appear to have no adverse effect on cell viability at the outlet. Further, the results demonstrate that we can predict the amount of DMSO removed from a given device with the theoretical model mentioned previously.     

A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing

This paper presents an extension of a competitive vehicle routing problem with time windows (VRPTW) to find short routes with the minimum travel cost and maximum sale by providing good services to customers before delivering the products by other rival distributors. In distribution of the products with short life time that customers need special device for keeping them, reaching time to customers influences on the sales amount which the classical VRPs are unable to handle these kinds of assumptions. Hence, a new mathematical model is developed for the proposed problem and for solving the problem, a simulated annealing (SA) approach is used. Then some small test problems are solved by the SA and the results are compared with obtained results from Lingo 8.0. For large-scale problems, the, Solomon's benchmark instances with additional assumption are used. The results show that the proposed SA algorithm can find good solutions in reasonable time.     

A neural network model to determine the plate width set-up value in a hot plate mill

Performance of the process reducing the slab width in hot plate mill called edging is critical to produce rolled products with a desired dimension, which otherwise increase the yield loss caused by trimming. This process, therefore, requires a stringent width control performance. In this paper, an edger set-up model generating the desired slab width required for the control is proposed based upon the neural network approach. This neural network model accounts for variation of the dimension of incoming slabs to predict the preset value of the width as accurately as possible. A series of simulations were conducted to evaluate the performance of the neural network estimator for a variety of operating conditions needed for producing rolled products of various dimensions. The results show that the proposed model can estimate the preset value of the slab width with good accuracy, thereby enhancing the dimensional accuracy of rolled products. The estimation performance is discussed in detail for various process operation conditions.