A topological sorting algorithm for three‐layer channel routing

Abstract

Three‐layer channel routing is an important problem in VLSI layout. In this paper, we present a topological sorting algorithm to determine the topological order on nets depending on the operations of the vertical constraint graph (VCG) and the horizontal constraint graph (HCG). According to the order, the base router can finish the connections of all nets. In the algorithm, the HVH mode is assumed, and some examples including Deutsch's difficult example are used as test problems.     

Task assignment in loosely‐coupled multiprocessor systems

Abstract

In loosely‐coupled multiprocessor systems, a parallel program has its modules distributedly assigned among the processors. The assignment policy is to minimize interprocessor communication cost and to balance the workload of processors. However, there exists conflict between these two criteria and a compromise must be made to obtain an optimal solution. In this paper, we propose a new task assignment model for distributed computing systems, and for solving the assignment problem based on partitioning graphs. The problem of finding an optimal solution had been shown to be in the class of NP‐complete. For the sake of computation efficiency, we propose some heuristics for obtaining suboptimal solutions.     

多波长光网络的动态路由等效算法

针对多波长光网络的特点，提出了一种动态路由和波长分配的等效算法。采用波长图、增加虚拟源节点和目的节点等技术，把多波长网络转化为等效的单波长网络，避免了求解路由和波长分配两个复杂子问题，简化了算法的程序设计。利用最短径算法进行路由和波长分配可以求得问题的最优解，从而有效地降低了网络阻塞率。仿真结果表明：与FAR-2D算法相比，在4和8波长的全波长转换网络中，采用等效算法阻塞率最大降幅分别达到0．02、0．025。     

A fast IP lookup scheme for high speed routers

Abstract

One of the key design issues for the next generation of IP routers is the IP lookup mechanism. IP lookup is an important action in a router, that is, to find the next hop for each incoming packet with a longest‐prefix‐match address in the routing table. In this paper, we propose an IP lookup mechanism with the number of memory accesses for an IP lookup being one in the best case and being four in the worst case. The forwarding table needed by our mechanism is small enough to fit in the SRAM. For example, a large routing table with 40000 routing entries can be compacted to a forwarding table of 260KBytes in our scheme.     

Task assignment problems in distributed computing systems by simulated annealing

Abstract

The stochastic, heuristic search algorithm called simulated annealing is considered for the problems of static task assignment in distributed computing systems. The purposes of task assignment problems are to assign modules of programs over a set of interconnected processors in order to both maximize the utilization of processors and minimize interprocessor communication costs. This problem has been proven to be NP‐hard. Although simulated annealing has been applied to a broad class of combinatorial optimization problems, but it requires a long computation time in order to converge to the globally optimal solution. In this paper, we design a very efficient annealing schedule with good move generation strategies and use the concept of specific heat and the frozen condition to obtain near‐optimal solutions for task assignment problems with a significantly large reduction in the number of iterations.     

Dynamic multicast routing and wavelength assignment using generic graph model for wavelength-division-multiplexing networks

The problem of dynamic multicast routing and wavelength assignment (MC-RWA) in the wavelength-routed wavelength-division-multiplexing networks is addressed. Current solutions to this problem always rely on homogeneous network constructions. However, future backbone networks tend to be heterogeneous in nature. Thus, the dynamic MC-RWA problem should be studied in a more realistic situation by considering the heterogeneity of network structures. A new graph model is proposed for the MC-RWA problem. This model is based on layered auxiliary graph which is generic and able to support various node architectures and heterogeneous network structures. Based on this graph model, the dynamic MC-RWA problem can be simply solved by an efficient multicast tree algorithm on various light-splitting and wavelength-conversion scenarios. In general, this graph model provides a universal platform to study different aspects of the dynamic MC-RWA as well as related problems.     

A genetic algorithm with domain knowledge for weapon‐target assignment problems

Abstract

In this paper, a novel genetic algorithm, including domain specific knowledge into the crossover operator and the local search mechanism for solving weapon‐target assignment (WTA) problems is proposed. The WTA problem is a full assignment of weapons to hostile targets with the objective of minimizing the expected damage value to own‐force assets. It is an NP‐complete problem. In our study, a greedy reformation and a new crossover operator are proposed to improve the search efficiency. The proposed algorithm outperforms its competitors on all test problems.     

Scheduling of a job-shop problem with limited output buffers

ABSTRACT

This article addresses a job-shop problem with limited output buffers (JS-LOB) with the objective of minimizing the process makespan. An integer nonlinear mathematical programming model is proposed to describe this problem. Based on the model, a two-stage algorithm consisting of obtaining feasible solutions and a local search is proposed to solve the JS-LOB problem. The local search has two operators: the first is a neighbourhood structure based on a disjunctive graph model, and the second is similar to crossover in the genetic algorithm to avoid falling into local optima. Computational results are presented for a set of benchmark tests. The results show the effectiveness of the proposed algorithm and indicate whether the processing time of the job conforms to a uniform distribution. When the proportion between the capacity of the buffer and the number of jobs is larger than 20%, the influence of the buffer becomes very small.     

Channel routing using neural networking

Abstract

The channel routing problem in an integrated circuit layout design involves making interconnections among terminals located on opposite sides of a rectangular channel. This problem has been proven to be NP‐complete and most currently available algorithms are heuristic. This paper proposes a neural network to handle the channel routing problem. Neural networking has been successfully applied to many combinatorial optimization problems. However, applying this technique to the channel routing problem has not ever been reported. This network allows users to preroute any critical nets and then invoke the network to complete the rest. User intervention also can speedup the operation of the router significantly. Typical examples from published literature are taken for experiments. The theoretic lower bounds are achieved in all examples.     

Design of “silent” circular saws

Abstract

This paper addresses a new problem of aligning two rows of movable terminals in order to minimize the channel width and via usage in the channel. The alignment problem of movable terminals is subject to the constraint that the number of vertical tracks used is not increased in the process. This constraint is not considerated in the paper referred to [6] which first considered the alignment problem of movable terminals. This problem is first shown to be NP‐complete, therefore, we present a heuristic algorithm. All examples presented in [2] including Deutsch's difficult example are used as the test routing problems. The programs were coded in C and implemented on SUN 3/110 workstation.     

A vehicle routing problem with time windows and stochastic demands

Abstract

This study presents an approach for considering a vehicle routing problem where customers’ pickup demands are uncertain and require serving within some settled time windows. Customers’ demands are assumed to follow given discrete probability distributions. This study proposes a nonlinear stochastic integer program with recourse to formulate the vehicle routing problem with stochastic demands and time windows (VRPTW‐SD, for short). The objective of the VRPTW‐SD is to minimize the total cost of the first‐stage solution and expected recourse cost of the second‐stage solution. The total cost of the first‐stage problem includes the total travel cost for all links and the total waiting cost at all nodes. When a vehicle capacity is attained or exceeded, recourse actions are needed and recourse costs incurred in order to finish the planned route schedules. Two categories of schedule failure are introduced in this work; the recourse costs derive from the variations in travel time travel time, waiting time, and penalties of late arrival for time windows. In addition, an optimization algorithm is developed for solving the VRPTW‐SD, according to the framework of the L‐shaped method. Numerical results are given to demonstrate its validity.     

基于遗传算法的图关联着色算法

图的着色算法是一种典型的NP-完全问题。给出了一种用于图的关联着色的遗传算法。遗传算法用于进行全局搜索,从而有效的查找解空间。文中对关联色数为6的一个图进行了仿真实验,给出了该图的关联色数以及4种6-关联着色。用本文提出的算法,得到了完全图、完全多部图的关联色数。实验结果表明,本文设计的遗传算法可以很好的对关联着色猜想进行求解,获得问题的高质量的解。     

Location and layout planning

This paper gives a review on quantitative methods for microeconomic location planning which can be subdivided into facility location and layout planning. Depending on different objectives and restrictions, there is a large variety of problems, especially in the field of facility location planning. Basic models arising in discrete and continuous facility location planning (e.g., warehouse location, center, location routing, competitive location problems), as well as corresponding solution methods, are presented. Generalized models and recent developments in these fields are outlined. Within layout planning, the quadratic assignment problem and graph-theoretic concepts are considered.     

Load-balanced wavelength assignment strategies for optical burst/packet switching networks

Loss-free schemes are defined to ensure successful packet/burst transmissions in optical packet/burst switching networks. To this end, they rely on a collision-free routing and wavelength assignment (CF-RWA) scheme combined with simple contention resolution mechanisms that guarantee the absence of losses in intermediate links. Here, the CF-RWA problem is studied. In particular, by using graph theory, the problem of finding CF-RWA schemes that minimise the number of wavelengths to serve a given traffic matrix is set. The problem is simplified when it is formulated by using pre-defined sets of non-colliding paths. Within this framework, the problem is shown to be equivalent to finding a given vertex-set colouring of the so-called restriction digraph. Here, two heuristic algorithms are proposed to obtain such vertex-set colourings. One of them provides a suitable CF-RWA without having to solve the minimisation problem. By way of example, the proposed method is applied to the NSFNet and the EON network providing quasi-optimal results.     

Transfer coefficients on the shell progressive poisoning model

Abstract

The idle server first (ISF) routing strategy in a finite queueing system with multiple unequal‐rate synchronous servers is studied. This paper extends the work of [4] by considering unequal‐rate servers. The input is assumed to be a batch Poisson distribution. The state transition equations used to describe the queueing behavior of the system are successfully solved. The performance measures, including average message blocking probability, average packet delay, average message delay, and system throughput, are obtained. The results show that ISF routing can have pretty good performance, and its effective measures are almost independent of routing probabilities. Validity of the analysis has also been verified by computer simulations.     

A computational algorithm for catalysts experiencing concentration‐dependent deactivation

Abstract

A computational algorithm is proposed for catalyst pellets or reactors experiencing concentration‐dependent deactivation. In the integration of the deactivation equation in each time interval, the concentration of poison, reactant or/and product is considered to be a constant. The value of concentration is recalculated from the mass balance equation before integrating the deactivation equation. By such an approach, the number of equations is reduced; thus a two‐dimensional problem can be converted to a single‐dimensional one.     

An expert system for network management control

Abstract

Due to the varying time and the complexity of the commercial telecommunication network configuration, routing of the communication traffic becomes very important for telecommunication systems. No one can keep in mind all the complex routing plans used in networks, so it is hard to quickly take proper actions while the switching node is being blocked.

In this paper, we propose an expert system which can collect traffic data, monitor network status, reason and take appropriate actions for extreme traffic congestion on a network just as a network management expert can do. It would certainly streamline the whole network control procedure, and. provide dynamic routing functions based on the original static routing method adopted in Taiwan. It does improve both network efficiency and network reliability.     

An application of an expert system in layout compaction of VLSI design

Abstract

Recent research in knowledge‐based expert systems of VLSI design tools has concentrated on placement, routing, and cell generation. This paper presents an alternative application for artificial intelligence (AI) techniques on compaction design for a VLSI mask layout‐expert compactor. In order to overcome the shortcomings of iterative search through a large problem space within a working memory, and therefore, to speed‐up the runtime of compaction, a set of rule‐based region query operations and knowledge‐based techniques for the plane sweep method are proposed in this system. Experimental results have explored the possibility of using expert system technology (EST) to automate the compaction process by “reasoning” out the layout design and applying sophisticated expert rules to its knowledge base.     

Robust pole‐assignment for dynamic systems with uncertain parameters

Abstract

In this paper, by using discrete‐type Lyapunov stability criterion, new sufficient conditions for robust pole‐assignment of uncertain systems in a specified disk are presented. The norm bound on linear time‐invariant perturbations is obtained. The relationship between the allowable bound and the eigenvalues of the nominal system matrix is discussed. A design method for robust pole‐assignment is proposed. Examples are given to demonstrate the use of the proposed techniques.     

GaAs metal‐semiconductor‐metal photodetectors (MSM‐PD'S) with AlGaAs cap and buffer layers

Abstract

GaAs metal‐semiconductor‐metal photodetectors with AlGaAs cap and buffer layers have been fabricated and studied. It is shown that the trap‐induced effects which result from the GaAs surface trap states can be avoided by adding an AlGaAs cap layer. In addition, we used an AlGaAs buffer layer to reduce the interfacial charge effects between the GaAs substrate and the GaAs absorption layer. The dark currents were less than 1 nA and the low frequency internal gain was dramatically improved. The results also show that a complete depletion can occur even at biases below 0.5 V.