1-14hit |
Kazuhiko IWASAKI Hiroyuki GOTO
The exact expected test lengths of pseudo-random patterns that are generated by LFSRs are theoretically analyzed for a CUT containing hard random-pattern-resistant faults. The exact expected test lengths are also analyzed when more than one primitive polynomials are selected.
This paper examines the properties of the greatest subsolution for linear equations in the max-plus algebra. The greatest subsolution is a relaxed solution of the linear equations, and gives a unified and reasonable solution whether there exists a strict solution or not. Accordingly, it forms part of a key algorithm for deriving a control law in the field of controller design, and some effective controllers based on the greatest subsolution have been proposed. However, there remain several issues to be discussed regarding the properties of the greatest subsolution. Hence, the main focus of this paper is on the following fundamental properties: 1) Formulation as an optimization problem, 2) Uniqueness of the greatest subsolution, 3) Necessary and sufficient condition for the correspondence of the greatest subsolution with the strict solution. These results could provide flexibility of the controller design based on the greatest subsolution, and facilitate the performance evaluation of the controller. Finally, the uniqueness of the strict solution of the linear equations is examined, and it is confirmed through illustrative examples.
This letter presents a method for solving several linear equations in max-plus algebra. The essential part of these equations is reduced to constraint satisfaction problems compatible with mixed integer programming. This method is flexible, compared with optimization methods, and suitable for scheduling of certain discrete event systems.
We propose Max-Plus Linear (MPL) systems with selective parameters that can describe a certain class of Timed Petri nets (TPN). In this class, selector and joint places are incorporated with Single-Input and Single-Output Timed Event Graph (SISO TEG) subnets. We confirm that the proposed controller effectively works taking into account practical constraints through a numerical example.
This research considers an efficient method for calculating the transition matrix in an MPL (Max-Plus Linear) state-space representation. This matrix can be generated by applying the Kleene star operator to an adjacency matrix. The proposed method, based on the idea of a topological sort in graph theory and block splitting, is able to calculate the transition matrix efficiently.
Hiroyuki GOTO Yasuhide TSUJI Takashi YASUI Koichi HIRAYAMA
In this paper, the function expansion based topology optimization is employed to the automatic optimization of the waveguide dispersion property, and the optimum design of low-dispersion slow-light photonic crystal waveguides is demonstrated. In order to realize low-dispersion and large group index, an objective function to be optimized is expressed by the weighted sum of the objective functions for the desired group index and the low-dispersion property, and weighting coefficients are updated through the optimization process.
Shinsuke ODAGIRI Hiroyuki GOTO
For a fixed number of nodes, we focus on directed acyclic graphs in which there is not a shortcut. We find the case where the number of paths is maximized and its corresponding count of maximal paths. Considering this case is essential in solving large-scale scheduling problems using a PERT chart.
Hiroyuki GOTO Yohei KAKIMOTO Yoichi SHIMAKAWA
Given a network G(V,E), a lightweight method to calculate overlaid origin-destination (O-D) traffic flows on all edges is developed. Each O-D trip shall select the shortest path. While simple implementations for single-source/all-destination and all-pair trips need O(L·n) and O(L·n2) in worst-case time complexity, respectively, our technique is executed with O(m+n) and O(m+n2), where n=|V|, m=|E|, and L represents the maximum arc length. This improvement is achieved by reusing outcomes of priority queue-based algorithms. Using a GIS dataset of a road network in Tokyo, Japan, the effectiveness of our technique is confirmed.
This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGs). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.
Hiroyuki GOTO Hirotaka TAKAHASHI
A method for efficiently representing the state equation in a class of max-plus linear systems is proposed. We introduce a construct referred to as 'cell' in which the list of possible longest paths is stored. By imposing interval constraints on the system parameters, we can reduce the complexity of the state equation. The proposed method would be useful in scheduling applications for systems with adjustable system parameters.
This letter extends the existent MPL (Max-Plus Linear) state-space representation and proposes a new form that can account for both capacity and order constraints. It is often essential to consider these factors when applying the MPL approach to scheduling problems for production or transportation systems. The derived form is a type of augmented state-representation and can contribute to obtaining the earliest start and completion times for processes in installed facilities.
Hiroyuki GOTO Hirotaka TAKAHASHI
This research proposes efficient calculation methods for the transition matrices in discrete event systems, where the adjacency matrices are represented by directed acyclic graphs. The essence of the research focuses on obtaining the Kleene Star of an adjacency matrix. Previous studies have proposed methods for calculating the longest paths focusing on destination nodes. However, in these methods the chosen algorithm depends on whether the adjacency matrix is sparse or dense. In contrast, this research calculates the longest paths focusing on source nodes. The proposed methods are more efficient than the previous ones, and are attractive in that the efficiency is not affected by the density of the adjacency matrix.
We develop an algorithm for a controller design method for Max-Plus Linear (MPL) systems with selective parameters. Since the conventional algorithm we proposed requires high computational load when the prediction horizon is large, two methods for reducing the calculation time are proposed. One is based upon the branch-and-bound method, and the other is to reuse the optimal solution. The effectiveness of these two methods is confirmed through numerical simulation.
This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband EngineTM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.