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

Resolution branch and bound and an application: The maximum weighted stable set problem

OPERATIONS RESEARCH 2007年第5期55卷 932-948页

作者： Avenali, Alessandro Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy

We propose a new resolution algorithm, called resolution branch and bound (RBB), where a branch-and-bound scheme is empowered by exploiting the information contained in a family of closed subproblems, collected by a full resolution phase. In particular, we use this information to define a new branching rule that seems able to reduce the risk of incurring inappropriate branchings. We apply RBB and the proposed branching rule to the maximum weighted stable set problem, as its features allow us to speed up a time-consuming step in the full resolution phase. To compute upper bounds, we generalize to the weighted case the polynomial time procedure provided by Mannino and Sassano [Mannino, C., A. Sassano. 1994. An exact algorithm for the maximum stable set problem. Computational Optim. Appl. 3 243-258] for the unweighted case. Computational results validate the effectiveness of the provided branching rule and the good performance of RBB on many DIMACS benchmarks.

关键词： algorithms: branch and bound mathematics: combinatorics networks/graphs programming: integer

来源：评论

学校读者我要写书评

暂无评论

SOLVING A CLASS OF STOCHASTIC MINIMIZATION PROBLEMS

引用

OPERATIONS RESEARCH 1994年第3期42卷 428-438页

作者： BAILEY, MP USN POSTGRAD SCHMONTEREYCA 93940 USA

This work gives a methodology for analyzing a class of discrete minimization problems with random element weights. The minimum weight solution is shown to be an absorbing state in a Markov chain, while the distribution of weight of the minimum weight element is shown to be of phase type. We then present two-sided bounds for matroids with NBUE distributed weights, as well as for weights with bounded positive hazard rates. We illustrate our method using a realistic military communications problem.

关键词： mathematics: combinatorics networks/graphs: stochastic probability: Markov processes

来源：评论

学校读者我要写书评

暂无评论

OPTIMALITY OF MONOTONE ASSEMBLIES FOR COHERENT SYSTEMS COMPOSED OF SERIES MODULES

引用

OPERATIONS RESEARCH 1994年第4期42卷 709-720页

作者： HWANG, FK ROTHBLUM, UG TECHNION ISRAEL INST TECHNOL HAIFAISRAEL RUTGERS STATE UNIV NEW BRUNSWICKNJ 08903

We consider a system with m modules as components. These modules are composed of parts of finitely many types, and the number of parts of each type that is needed in each of the modules is given, e.g., module i requires n(ui) parts of type u. Parts of the same type may have different reliabilities, but they are functionally interchangeable. A module works if and only if all of its parts work, i.e., the internal composition of the modules has series structure. An assembly of the modules consists of an assignment of each of the SIGMA(u)SIGMA(i)n(ui) parts to the modules such that each module meets its specification by getting the required number of parts of each type. Such an assembly is called monotone if the best parts of each type go to one module, the next best parts of each type go to a second module, and so on, until finally the last module gets the worst parts of each type. We prove that for coherent systems, there always exists a monotone assembly which maximizes the reliability of the system. Furthermore, we obtain sufficient conditions under which every optimal assembly is monotone.

关键词： mathematics: combinatorics optimal partitions and convexity reliability: coherent structure optimal assembly and monotone assembly

来源：评论

学校读者我要写书评

暂无评论

DISJOINT PRODUCTS AND EFFICIENT COMPUTATION OF RELIABILITY

引用

OPERATIONS RESEARCH 1988年第5期36卷 703-715页

作者： BALL, MO PROVAN, JS UNIV N CAROLINA DEPT OPERAT RESCHAPEL HILLNC 27514

In this paper, we analyze the problem of computing the probability of the union of a set of events, where each event is given as the product of a set of Boolean variables. Each Boolean variable represents the operation or failure of a particular component. The problem has direct applications to the reliability analysis of complex systems as well as more general applications. After showing that the problem is NP-hard in general, we define simple, computationally efficient procedures for generating upper and lower bounds on the required probability. We show that these procedures produce the exact answer, i.e., the upper bound equals the lower bounds, for two classes of systems, matroids and threshold systems. These results draw on the relationship between this problem and the notion of shellability studied in the context of simplicial polytopes. Shellability is shown to have a very interesting and useful interpretation in this problem setting.

关键词： mathematics: combinatorics networks/graphs stochastic reliability

来源：评论

学校读者我要写书评

暂无评论

LONG-RANGE PROCESS DESIGN AND COMPATIBILITY AMONG OPERATIONS

引用

MANAGEMENT SCIENCE 1988年第5期34卷 619-632页

作者： SINGHAL, J SINGHAL, K WEEKS, JK UNIV BALTIMORE DEPT MANAGEMENTBALTIMOREMD 21201 UNIV N CAROLINA SCH BUSINESS & ECONGREENSBORONC 27412

Most processes consist of several operations. Some or all of these operations may have more than one alternative technological method, resulting in an exponential relationship between the number of possible designs and the number of operation alternatives. However, some of these designs may not be feasible because of incompatibilities among operation alternatives. A feasible process design will include one alternative for each operation in such a way that each operation is compatible with every other operation in the design. For identifying these feasible designs, there are two approaches: traditional and morphological. The former relies on trial-and-error, expert judgment, and creative thinking and the latter considers, explicitly or implicitly, every possible design. This paper presents an efficient algorithm with computational results for identifying all feasible designs based on compatibility considerations. The implementation issues, both computational and organizational, are discussed as integral parts of a framework for process design efforts. This framework combines the advantages of both the traditional and morphological approaches and mitigates their disadvantages. It also facilitates interaction between the expert's judgment and the programmed model.

关键词： production/scheduling: product design research and development mathematics: combinatorics

来源：评论

学校读者我要写书评

暂无评论

FLOWSHOP PROBLEMS WITH TIME LAGS

引用

MANAGEMENT SCIENCE 1983年第4期29卷 477-481页

作者： SZWARC, W University of Wisconsin Milwaukee

This paper defines a model that covers the multimachine extensions of all existing flow-shop problems with time lags as well as flow-shop problems where setup, processing and release times are separated. Approximate s... 详细信息

关键词： production/scheduling: flow shop queues: deterministic mathematics: combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：