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

Interdicting a Nuclear-Weapons Project

OPERATIONS RESEARCH 2009年第4期57卷 866-877页

作者： Brown, Gerald G. Carlyle, W. Matthew Harney, Robert C. Skroch, Eric M. Wood, R. Kevin USN Postgrad Sch Dept Operat Res Monterey CA 93942 USA USN Postgrad Sch Dept Syst Engn Monterey CA 93942 USA Northrop Grumman Corp Virginia Beach VA 23452 USA

A "proliferator" seeks to complete a first small batch of fission weapons as quickly as possible, whereas an "interdictor" wishes to delay that completion for as long as possible. We develop and solve a max-min model that identifies resource-limited interdiction actions that maximally delay completion time of the proliferator's weapons project, given that the proliferator will observe any such actions and adjust his plans to minimize that time. The model incorporates a detailed project-management ( critical path method) submodel, and standard optimization software solves the model in a few minutes on a personal computer. We exploit off-the-shelf project-management software to manage a database, control the optimization, and display results. Using a range of levels for interdiction effort, we analyze a published case study that models three alternate uranium-enrichment technologies. The task of "cascade loading" appears in all technologies and turns out to be an inherent fragility for the proliferator at all levels of interdiction effort. Such insights enable policy makers to quantify the effects of interdiction options at their disposal, be they diplomatic, economic, or military.

关键词： government: defense foreign policy military: targeting programming: integer linear project management: CPM

来源：评论

学校读者我要写书评

暂无评论

An exact approach to the one-dimensional facility layout problem

引用

OPERATIONS RESEARCH 2008年第4期56卷 1026-1033页

作者： Amaral, Andre R. S. Univ Fed Espirito Santo Dept Informat BR-29060970 Vitoria ES Brazil

The one-dimensional facility layout problem is concerned with arranging n departments of given lengths on a line, while minimizing the weighted sum of the distances between all pairs of departments. The problem is NP-hard because it is a generalization of the minimum linear arrangement problem. In this paper, a 0-1 quadratic programming model consisting of only O(n(2)) 0-1 variables is proposed for the problem. Subsequently, this model is cast as an equivalent mixed-integer program and then reduced by preprocessing. Next, additional redundant constraints are introduced and linearized in a higher space to achieve an equivalent mixed 0-1 linear program, whose continuous relaxation provides an approximation of the convex hull of solutions to the quadratic program. It is shown that the resulting mixed 0-1 linear program is more efficient than previously published mixed-integer formulations. In the computational results, several problem instances taken from the literature were efficiently solved to optimality. Moreover, it is now possible to efficiently solve problems of a larger size.

关键词： facilities/equipment planning: layout programming: integer

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

DNA sequencing by hybridization via genetic search

引用

OPERATIONS RESEARCH 2006年第6期54卷 1185-1192页

作者： Blazewicz, Jacek Oguz, Ceyda Swiercz, Aleksandra Weglarz, Jan Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland Polish Acad Sci Inst Bioorgan Chem PL-61704 Poznan Poland Koc Univ Dept Ind Engn Istanbul Turkey

An innovative approach to DNA sequencing by hybridization utilizes isothermic oligonucleotide libraries. In this paper, we demonstrate the utility of a genetic algorithm for the combinatorial portion of this new approach by incorporating characteristics of DNA sequencing by hybridization in addition to isothermic oligonucleotide libraries. Specialized crossover and mutation operators were developed for this purpose. After initial experiments for parameter adjustment, the performance of the genetic algorithm approach was evaluated with respect to previous methods in the literature. The results indicate that the proposed new approach is superior to previous approaches. The proposed new crossover operator that inherits some features of the structured weighted combinations might also be of value for some other combinatorial problems, including the traveling salesman problem.

关键词： analysis of algorithms: metaheuristics health care: bioinformatics health care: DNA sequencing programming: integer algorithms: heuristic

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the inverse spanning-tree problem

引用

OPERATIONS RESEARCH 2003年第5期51卷 785-797页

作者： Hochbaum, DS Univ Calif Berkeley Dept Ind Engn & Operat Res Walter A Haas Sch Business Berkeley CA 94720 USA

The inverse spanning-tree problem is to modify edge weights in a graph so that a given tree T is a minimum spanning tree. The objective is to minimize the cost of the deviation. The cost of deviation is typically a convex function. We propose algorithms here that are faster than all known algorithms for the problem. Our algorithm's run time for any convex inverse spanning-tree problem is O(nm log(2) n) for a graph on n nodes and m edges plus the time required to find the minima of the n convex deviation functions. This not only improves on the complexity of previously known algorithms for the general problem, but also for algorithms devised for special cases. For the case when the objective is weighted absolute deviation, Sokkalingam et al. (1999) devised an algorithm with run time O(n(2)m log(nC)) for C the maximum edge weight. For the sum of absolute deviations our algorithm runs in time O(n(2) log n), matching the run time of a recent (Ahuja and Orlin 2000) improvement for this case. A new algorithm for bipartite matching in path graphs is reported here with complexity of O(n(1.5) log n). This leads to a second algorithm for the sum of absolute deviations running in O(n(1.5) log n log C) steps.

关键词： programming: integer algorithms optimization in integers Network/graphs: flow algorithms parametric minimum cut Mathematics: convexity convex optimization problem

来源：评论

学校读者我要写书评

暂无评论

A comparison of formulations for the single-airport ground-holding problem with banking constraints

引用

OPERATIONS RESEARCH 2000年第4期48卷 578-590页

作者： Hoffman, R Ball, MO Univ Maryland RH Smith Sch Business College Pk MD 20742 USA Univ Maryland Inst Syst Res College Pk MD 20742 USA Metron Sci Consulting Reston VA 20190 USA

Both the single-airport ground-holding problem (GH) and the multi-airport ground-holding problem can be extended by the addition of banking constraints to accommodate the hubbing operations of major airlines. These constraints enforce the desire of airlines to land certain groups of flights, called banks, within fixed time windows, thus preventing the propagation of delays throughout their entire operation. GH can be formulated as a transportation problem and readily solved. But in the presence of banking constraints, GH becomes a difficult integer programming problem. In this paper, we construct five different models of the single-airport ground-holding problem with banking constraints (GHB). The models are evaluated both computationally and analytically. For two of the models, we show that the banking constraints induce facets of the convex hull of the set of integer solutions. In addition, we explore a linear transformation of variables and a branching technique.

关键词： programming: integer algorithms Transportation: models air traffic management

来源：评论

学校读者我要写书评

暂无评论

STOCHASTIC AND DYNAMIC-MODELS IN TRANSPORTATION - PREFACE

引用

OPERATIONS RESEARCH 1993年第1期41卷 11-14页

作者： DROR, M POWELL, W PRINCETON UNIV PRINCETONNJ 08544

One lives in an environment that is changing more quickly than before, with higher demands on productivity and service, using transportation systems that are larger and more complex. However, the tools to manage these systems are also becoming more sophisticated. Bar coding allows to track shipments and containers as they move through the system, providing minute-by-minute tracking capabilities. Satellites allows to monitor and communicate with long-haul truck drivers, giving truckload carriers the opportunity to genuinely control fleets of thousands of trucks. Mobile communication terminals allow dispatchers to work with local fleets, ranging from pickup and delivery trucks to police and ambulances. information being put in front of us. Real-time operations impose tight constraints on the amount of time that are allowed to make a decision. Manual methods, which are still in use by virtually all modes of transportation, are ill-suited to respond in real time to last minute changes and disruptions.

关键词： inventory/production: multi-echelon lot sizing programming: integer branch and bound relaxation/subgradient

来源：评论

学校读者我要写书评

暂无评论

MODELS ARISING FROM A FLEXIBLE MANUFACTURING MACHINE .2. MINIMIZATION OF THE NUMBER OF SWITCHING INSTANTS

引用

OPERATIONS RESEARCH 1988年第5期36卷 778-784页

作者： TANG, CS DENARDO, EV YALE UNIV SCH ORG & MANAGEMENTNEW HAVENCT 06520

This paper deals with a job scheduling problem for a flexible manufacturing machine. We consider the same manufacturing environment described in a companion study (Part I), but we use a different performance criterion: to minimize the total number of instants at which tools are switched. This performance criterion is appropriate when the switching time is roughly constant and independent of the number of tool switches. We show that this scheduling problem generalizes the classical bin packing problem, and we present a non-LP-based branch-and-bound procedure that terminates with an optimal solution. We extend this procedure to the case of K machines in sequence.

关键词： production/scheduling: material handling programming: integer algorithms branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

DESIGN AND OPERATION OF A MULTICOMMODITY PRODUCTION-DISTRIBUTION SYSTEM USING PRIMAL GOAL DECOMPOSITION

引用

MANAGEMENT SCIENCE 1987年第11期33卷 1469-1480页

作者： BROWN, GG GRAVES, GW HONCZARENKO, MD UNIV CALIF LOS ANGELES GRAD SCH MANAGEMENT LOS ANGELES CA 90024 USA NABISCO BRANDS INC E HANOVER NJ 07936 USA

An optimization-based decision support system has been developed and used by NABISCO to manage complex problems involving facility selection, equipment location and utilization, and manufacture and distribution of products such as the familiar Ritz Crackers, Oreo Cookies, Fig Newtons, etc. (all product names trademarks of NABISCO). A mixed-integer, multi-commodity model is presented for the problems at hand, and a new class of goal decompositions is introduced to yield pure network subproblems for each commodity; the associated master problems have several notable properties which contribute to the effectiveness of the algorithm. Excellent quality solutions for problems with more than 40,000 variables (including several hundred binary variables with fixed charges) and in excess of 20,000 constraints require only 0.6 megabytes region and less than one compute minute on a time-shared IBM 3033 computer; average problems (with fewer binary variables) require only a second or two. The solution method has more to recommend it than sheer efficiency: new insights are given for the fundamental convergence properties of formal decomposition techniques. Several applications of this powerful interactive tool are discussed.

关键词： programming: large-scale systems programming: integer applications facilities/equipment planning

来源：评论

学校读者我要写书评

暂无评论

A BRANCH AND BOUND APPROACH FOR MACHINE LOAD BALANCING IN FLEXIBLE MANUFACTURING SYSTEMS

引用

MANAGEMENT SCIENCE 1986年第10期32卷 1316-1335页

作者： BERRADA, M STECKE, KE UNIV MICHIGAN GRAD SCH BUSINESS ADMANN ARBORMI 48109

A flexible manufacturing system (FMS) is an integrated system of computer numerically controlled machine tools connected with automated material handling. A set of production planning problems for FMSs has been defined (Stecke [Stecke, Kathryn E. 1983. Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Management Sci. 29 (3, March) 273–288.]), and this paper considers one called the loading problem. This problem involves assigning to the machine tools, operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The part types will be machined during the upcoming production period (say, of one to three weeks duration on average) and according to a prespecified part mix. This assignment is constrained by the capacity of each machine's tool magazine as well as by the production capacities of both the system, and each machine type. There are several loading objectives that are applicable in a flexible manufacturing situation. This paper considers the most commonly applied one, that of balancing the workload on all machines.

关键词： production/scheduling: flexible manufacturing production/scheduling: line balancing programming: integer algorithms: branch and bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：