Scan shift power can be reduced by activating only a subset of scan cells in each shift cycle. In contrast to shift power reduction, the use of only a subset of scan cells to capture responses in a cycle may cause cap...
详细信息
ISBN:
(纸本)9781424481927
Scan shift power can be reduced by activating only a subset of scan cells in each shift cycle. In contrast to shift power reduction, the use of only a subset of scan cells to capture responses in a cycle may cause capture violations, thereby leading to fault coverage loss. In order to restore the original fault coverage, new test patterns must be generated, leading to higher test-data volume. In this paper, we propose minimum-violations partitioning (MVP), a scan-cell clustering method that can support multiple capture cycles in delay testing without increasing test-data volume. This method is based on an integer linear programming model and it can cluster the scan flip-flops into balanced parts with minimum capture violations. Based on this approach, hierarchical partitioning is proposed to make the partitioning method routing-aware. Experimental results on ISCAS'89 and IWLS'05 benchmark circuits demonstrate the effectiveness of our method.
Hardware fault-insertion test is a promising method to diagnose functional failures and target "no trouble found (NTF)" problems in electronic systems. However, it is costly and impractical to equip all the ...
详细信息
ISBN:
(纸本)9780769542485
Hardware fault-insertion test is a promising method to diagnose functional failures and target "no trouble found (NTF)" problems in electronic systems. However, it is costly and impractical to equip all the potential fault sites with fault-insertion hardware. We present an optimization method to select the most effective outputs of a module where fault insertion logic must be placed to facilitate diagnosis. Faults inserted at the selected outputs are able to generate fault syndromes that are most similar to the errors produced by defects inside the module. This approach also ensures that the ambiguous fault candidates from other modules are maximally removed from the set of suspects. A fault syndrome is defined by the order of error occurrence at the observation points, and it is referred as an error flow. The similarity between two error flows is measured by the metric of edit distance. An integer linear programming model is used to maximize diagnostic effectiveness with a small number of fault-insertion points. Results on diagnostic accuracy for an open-source RISC highlight the effectiveness of the proposed method compared to a baseline random fault-insertion scheme.
In this paper, we present three new integrative approaches for solving the classical car-sequencing problem. These hybrid approaches are essentially based on a genetic algorithm which incorporates crossover operators ...
详细信息
In this paper, we present three new integrative approaches for solving the classical car-sequencing problem. These hybrid approaches are essentially based on a genetic algorithm which incorporates crossover operators using an integer linear programming model during the crossover process for the construction of a solution. This form of integrative hybridization has been proposed by Cotta and Troya in a framework for hybridizing evolutionary algorithms with a branch-and-bound algorithm in order to explore the dynastic potential of the two parents' solutions and thus obtain the best offspring. However, while our crossovers also use problem-knowledge in the recombination process, they are not strictly transmitting operators and do not limit the exploration to the dynastic potential of the parents' solutions. We show that the hybrid approach outperforms a genetic algorithm with local search and other algorithms found in the literature on the CSPLib benchmarks. Although the computation times are long when integrative hybridization is used, this study well illustrates the interest of designing hybrid approaches exploiting the strengths of different methods.
Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximu...
详细信息
Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.
High-throughput techniques produce massive data on a genome-wide scale which facilitate pharmaceutical research. Drug target discovery is a crucial step in the drug discovery process and also plays a vital role in the...
详细信息
High-throughput techniques produce massive data on a genome-wide scale which facilitate pharmaceutical research. Drug target discovery is a crucial step in the drug discovery process and also plays a vital role in therapeutics. In this study, the problem of detecting drug targets was addressed, which finds a set of enzymes whose inhibition stops the production of a given set of target compounds and meanwhile minimally eliminates non-target compounds in the context of metabolic networks. The model aims to make the side effects of drugs as small as possible and thus has practical significance of potential pharmaceutical applications. Specifically, by exploiting special features of metabolic systems, a novel approach was proposed to exactly formulate this drug target detection problem as an integer linear programming model, which ensures that optimal solutions can be found efficiently without any heuristic manipulations. To verify the effectiveness of our approach, computational experiments on both Escherichia coli and Homo sapiens metabolic pathways were conducted. The results show that our approach can identify the optimal drug targets in an exact and efficient manner. In particular, it can be applied to large-scale networks including the whole metabolic networks from most organisms.
This paper presents a new integerlinearprogramming (ILP) model to schedule flexible job shop, discrete parts manufacturing industries that operate on a make-to-order basis. The model considers groups of parallel hom...
详细信息
This paper presents a new integerlinearprogramming (ILP) model to schedule flexible job shop, discrete parts manufacturing industries that operate on a make-to-order basis. The model considers groups of parallel homogeneous machines, limited intermediate buffers and negligible set-up effects. Orders consist of a number of discrete units to be produced and follow one of a given number of processing routes. The model allows re-circulation to take place, an important issue in practice that has received scant treatment in the scheduling literature. Good solution times were obtained using commercial mixed-integerlinearprogramming (MILP) software to solve realistic examples of flexible job shops to optimality. This supports the claim that recent advances in computational power and MILP solution algorithms are making this approach competitive with others traditionally applied in job shop scheduling.
EUGENE is a sophisticated mixed integer linear programming model developed to help regional decision makers on long-term planning for solid waste management activities. The model removes almost every limitations encou...
详细信息
EUGENE is a sophisticated mixed integer linear programming model developed to help regional decision makers on long-term planning for solid waste management activities. The model removes almost every limitations encountered in other waste management models and contains a large quantity of variables and constraints. The method used to embed waste management environmental parameters in the EUGENE model consists in building global impact index (GII) for all site/facility combinations. First, an environmental and spatial evaluation of waste management facilities over sites is based on qualitative and quantitative criteria measuring biophysical and social impacts. Spatial analysis is carried out by geographical information system routines. Then, a multicriteria analysis ranks all site/facility combinations, according to their global performance based on all criteria. The net flow, computed by the PROMETHEE multicriteria outranking method, is considered as a GII to be embedded into EUGENE. The model objective function is thus modified to minimize total system cost and GII Some practical results obtained for the City of Montreal are discussed. Crown Copyright (C) 2002 Published by Elsevier Science B.V. All rights reserved.
暂无评论