检索结果-内蒙古大学图书馆

An exact algorithm for RAP with k-out-of-n subsystems and heterogeneous components under mixed and K-mixed redundancy strategies

引用

ADVANCED ENGINEERING INFORMATICS 2025年 65卷

作者： Li, Jiangang Wang, Dan Yang, Haoxiang Liu, Mingli Si, Shubin Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Peoples R China Northwestern Polytech Univ Key Lab Ind Engn & Intelligent Mfg Minist Ind & Informat Technol Xian 710072 Peoples R China Chinese Univ Hong Kong Sch Data Sci Shenzhen 518172 Peoples R China Anhui Univ Sci & Technol Sch Publ Secur & Emergency Management Hefei 231131 Peoples R China

Redundancy design is a widely used technique for enhancing system reliability across various industries, including aerospace and manufacturing. Consequently, the redundancy allocation problem (RAP) has attracted considerable attention in the field of reliability engineering. The RAP seeks to determine an optimal redundancy scheme for each subsystem under resource constraints to maximize system reliability. However, existing RAP models and exact algorithms are predominantly confined to simple 1-out-of-n subsystems or single optimization strategies, thereby limiting the optimization potential and failing to adequately address the engineering requirements. This paper introduces a model and an exact algorithm for RAP with k-out-of-n subsystems and heterogeneous components under mixed and K-mixed redundancy strategies. The model employs a continuous time Markov chain method to calculate subsystem reliability exactly. A dynamic programming (DP) algorithm based on super component and sparse node strategies is designed to obtain the exact solution for RAP. Numerical experiments confirm that all benchmark test problems reported in the literature are exactly solved by the proposed DP. The experiment results demonstrate that the proposed RAP model offers high flexibility and potential for reliability optimization. Additionally, owing to the generality of the problem considered, the proposed DP also exactly solves other RAP models with 1-out-of-n subsystems and simplified redundancy strategies, which provides a more generalized framework for redundancy optimization. Finally, the research's applicability in reliability engineering is validated through an optimization case study of a natural gas compressor pipeline system.

关键词： Redundancy allocation problem exact algorithm K-out-of-n subsystems Heterogeneous components Redundancy strategy

来源：评论

学校读者我要写书评

暂无评论

exact algorithm and heuristic for the Closest String Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第11期38卷 1513-1520页

作者： Liu, Xiaolan Liu, Shenghan Hao, Zhifeng Mauch, Holger S China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Guangdong Peoples R China S China Univ Technol Dept Math Guangzhou 510640 Guangdong Peoples R China Guangdong Power Grid Corp Informat Ctr Guangzhou 510080 Guangdong Peoples R China Guangdong Univ Technol Fac Comp Guangzhou 510006 Guangdong Peoples R China Eckerd Coll Coll Nat Sci St Petersburg FL USA

The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. journal of Information & Computational Science 2004;1(2): 287-92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Closest String Problem exact algorithm Heuristic Local search strategies

来源：评论

学校读者我要写书评

暂无评论

exact algorithm for graph homomorphism and locally injective graph homomorphism

引用

INFORMATION PROCESSING LETTERS 2014年第7期114卷 387-391页

作者： Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci PL-00662 Warsaw Poland

For graphs G and H, a homomorphism from G to H is a function phi: V(G) -> V(H), which maps vertices adjacent in G to adjacent vertices of H. A homomorphism is locally injective if no two vertices with a common neighbor are mapped to a single vertex in H. Many cases of graph homomorphism and locally injective graph homomorphism are NP-complete, so there is little hope to design polynomial-time algorithms for them. In this paper we present an algorithm for graph homomorphism and locally injective homomorphism working in time O*((b + 2)(vertical bar V(G)vertical bar)), where b is the bandwidth of the complement of H. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Graph homomorphism Locally injective homomorphism H(2,1)-labeling exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence 1

引用

13th International Conference on Learning and Intelligent Optimization (LION)

作者： Kel'manov, Alexander Khamidullin, Sergey Panasenko, Anna Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova St Novosibirsk 630090 Russia

ISBN: (数字)9783030386290

ISBN: (纸本)9783030386290;9783030386283

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.

关键词： Euclidean space Sequence of points Weighted 2-partition Quadratic variation NP-hard problem Integer coordinates exact algorithm Fixed space dimension Pseudopolynomial time

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the single liner service design problem with speed optimisation

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2021年第22期59卷 6809-6832页

作者： Brahimi, Nadjib Cheaitou, Ali Cariou, Pierre Feillet, Dominique Rennes Sch Business Dept Supply Chain Management & IS 2 Rue Robert Arbrissel Rennes France Univ Sharjah Sustainable Engn Asset Management SEAM Res Grp Sharjah U Arab Emirates Univ Sharjah Dept Ind Engn & Engn Management Sharjah U Arab Emirates Ctr Excellence Supply Chain CESIT Kedge Business Sch Talence France Mines St Etienne CMP Georges Charpak Gardanne France LIMOS Gardanne France

This paper models a single liner service design and operations problem. The model selects the ports to be included, their sequence, the sailing speed of vessels, the number of vessels and the amounts of cargo to transport by the service. The objective is to maximise profit. First, a relaxation with a mixed-integer nonlinear programming (MINLP) formulation is proposed. We show how to obtain the optimal speed value. Once this value is obtained, the mathematical programming formulation becomes a mixed-integer linear program (MILP). Then, a two-step exact algorithm is presented to solve the problem. Using real data, the optimal solution was found in less than 1 min for small-size problems and in few hours for relatively large-size problems. More tests were carried out on randomly generated data sets with up to 25 ports. The results of these tests are rather promising, and they enabled us to identify the performance limits of the algorithm.

关键词： Liner shipping vessel routing sailing speed optimisation integer programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the unrestricted block relocation problem

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 95卷 12-31页

作者： Tanaka, Shunji Mizuno, Fumitaka Kyoto Univ Inst Liberal Arts & Sci Nishikyo Ku Kyoto 6158510 Japan Kyoto Univ Dept Elect Engn Nishikyo Ku Kyoto 6158510 Japan

The purpose of this study is to propose an exact algorithm for the unrestricted block relocation problem with distinct priorities. In this problem, a storage area is considered where blocks of the same size are stacked vertically in tiers. Because we can access only topmost blocks, relocations of blocks are required when other blocks are retrieved. The objective is to minimize the total number of such relocations necessary for retrieving all the blocks one by one according to a specified order. In the restricted version of this problem, only the topmost block above the target block is relocatable. On the other hand, no such restriction is imposed on the unrestricted problem, which is considered in this study. We also assume that each block is assigned a distinct retrieval priority and the retrieval order of blocks is unique. To improve the efficiency of a branch-and-bound algorithm for this problem, we propose several dominance properties to eliminate unnecessary nodes in the search tree. Furthermore, we propose a new lower bound of the total number of relocations. The effectiveness of the proposed exact algorithm is verified by numerical experiments for benchmark instances in the literature. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Block relocation problem Container relocation problem exact algorithm Dominance properties Lower bound

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

引用

OPTIMIZATION LETTERS 2011年第2期5卷 297-306页

作者： Ding, Ling Gao, Xiaofeng Wu, Weili Lee, Wonjun Zhu, Xu Du, Ding-Zhu Univ Texas Dallas Dept Comp Sci Dallas TX 75230 USA Korea Univ Dept Comp Sci & Engn Seoul South Korea Xi An Jiao Tong Univ Dept Math Xian Peoples R China

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(delta (2) n), where delta is the maximum node degree in communication graph.

关键词： CDS Shortest path exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for maximum independent set in degree-5 graphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 137-155页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan

The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.1736(n)n(0(1))-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895(n)n(0(1)). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. (C) 2014 Elsevier B.V. All rights reserved.

关键词： exact algorithm Graph algorithm Maximum independent set Measure and Conquer Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer Programs

引用

MANAGEMENT SCIENCE 2010年第12期56卷 2302-2315页

作者： Ozpeynirci, Ozgur Koksalan, Murat Izmir Univ Econ Dept Logist Management TR-35330 Izmir Turkey Middle E Tech Univ Dept Ind Engn TR-06531 Ankara Turkey

In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm's performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives.

关键词： multiobjective optimization nondominated points exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning

引用

PARALLEL COMPUTING 2020年 96卷 102640-102640页

作者： Knigge, Timon E. Bisseling, Rob H. Swiss Fed Inst Technol Zurich Switzerland Univ Utrecht Math Inst Utrecht Netherlands

We investigate sparse matrix bipartitioning - a problem where we minimize the communication volume in parallel sparse matrix-vector multiplication. We prove, by reduction from graph bisection, that this problem is N P-complete in the case where each side of the bipartitioning must contain a linear fraction of the nonzeros. We present an improved exact branch-and-bound algorithm which finds the minimum communication volume for a given matrix and maximum allowed imbalance. The algorithm is based on a maximum-flow bound and a packing bound, which extend previous matching and packing bounds. We implemented the algorithm in a new program called MP (Matrix Partitioner), which solved 839 matrices from the SuiteSparse collection to optimality, each within 24 h of CPU-time. Furthermore, MP solved the difficult problem of the matrix cage6 in about 3 days. The new program is on average more than ten times faster than the previous program MondriaanOpt. Benchmark results using the set of 839 optimally solved matrices show that combining the mediumgrain/iterative refinement methods of the Mondriaan package with the hypergraph bipartitioner of the PaToH package produces sparse matrix bipartitionings on average within 10% of the optimal solution. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Bisection exact algorithm Maximum flow NP Complete Partitioning Sparse matrix

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：