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

Optimal Solutions for Fault-Tolerant Topology Control in Wireless Ad Hoc Networks

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2009年第12期8卷 5970-5981页

作者： Moraes, Renato E. N. Ribeiro, Celso C. Duhamel, Christophe Univ Fed Fluminense Dept Comp Sci BR-24210240 Niteroi RJ Brazil Univ Clermont Ferrand 2 F-63173 Aubiere France

Topology control is one of the most important techniques used in wireless ad hoc and sensor networks to reduce energy consumption. Algorithms for topology control attempt to reduce the number of links and the power consumption in a network subject to connectivity constraints. We show that the related optimization problems may be classified into four main variants, regarding the topology of the input graph (symmetric or asymmetric) and of the solution (unidirectional or bidirectional). We present three mixed integer programming formulations for the k-connected minimum power consumption problem, which consists in finding a power assignment to the nodes of a wireless network so as that the resulting network topology be. k-vertex connected (i.e., k-fault tolerant) and the total power consumption be minimum. These formulations are sufficiently general to encompass all four problem variants. We report computational experiments comparing the formulations. Optimal solutions for moderately sized networks are obtained using a commercial solver.

关键词： Wireless networks ad hoc networks topology control k-connectivity fault tolerance energy consumption optimization mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

Simulation of Optimal Medium-Term Hydro-Thermal System Operation by Grid Computing

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2009年第3期24卷 1208-1217页

作者： Baslis, Costas G. Papadakis, Stylianos E. Bakirtzis, Anastasios G. Aristotle Univ Thessaloniki Dept Elect & Comp Engn GR-54124 Thessaloniki Greece Technol Inst Kavala Dept Ind Informat Div Comp Syst GR-65404 Kavala Greece

This paper presents a model for the simulation of the optimal medium-term operation of a hydrothermal system. System stochastic parameters are modeled by Monte Carlo scenarios, which are solved on distributed processors. For each scenario a yearly hydro-thermal scheduling (HTS) problem with hourly time resolution is formulated and solved as a large mixed integer linear program (MILP). HTS modeling includes unit commitment, start-up costs and minimum up/down time constraints. The model is applied to the Greek Power System, comprising 29 thermal units and 13 hydroplants;100 simulation scenarios are generated and solved on 18 distributed processors. Test results include both medium-term objectives, such as reservoir water management, and short-term decisions such thermal unit start-up decisions.

关键词： Grid computing mixed integer programming Monte Carlo simulation power system simulation

来源：评论

学校读者我要写书评

暂无评论

Algorithmic challenges and current problems in market coupling regimes

引用

EUROPEAN TRANSACTIONS ON ELECTRICAL POWER 2009年第4期19卷 532-543页

作者： Tersteegen, Bernd Schroeders, Christian Stein, Sebastian Haubrich, Hans-Juergen Rhein Westfal TH Aachen Inst Power Syst & Power Econ D-52056 Aachen Germany

Increasing cross-border trade at European borders has lead to the necessity of an efficient allocation of scarce cross-border capacities. Explicit auctions used to be the commonly applied auction method in the past at most borders, but clue to the separation of the trade of electrical energy and the allocation of cross-border capacity, market inefficiencies arise. As a consequence, a trend toward a market coupling, which combines the trade of electrical energy with the allocation of cross-border capacity, can be observed across Europe. The most convincing approach to solve the complex optimization task associated with market couplings solves the problem by a maximization of the system-wide welfare based on a closed form optimization. Practical experience show, that problems remain with such an approach. This paper thoroughly analyzes problems that may Occur in market coupling regimes with a closed-form optimization. In this paper an extension of formerly presented formulations of the optimization problem is presented, which avoids the described problems. The extended formulation still assures practically feasible calculation times of far less than 10 minutes even for systems with up to 12 market areas. Further, a fair and transparent approach to determine feasible market clearing prices not neglecting the time and market coupling relationship between prices is shown in this paper and it is demonstrated that this approach does not lead to practically infeasible calculation times. Copyright (C) 2009 John Wiley & Sons, Ltd.

关键词： Market coupling implicit auction congestion management price coupling volume couplings mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

On the existence of duality gaps for mixed integer programming

引用

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE 2005年第6期36卷 375-379页

作者： Tanaka, Y Hokkaido Univ Grad Sch Econ & Business Adv Sapporo Hokkaido 0600809 Japan

Only a few theoretical studies of surrogate duality have been carried out since Greenberg and Pierskalla's comprehensive work. Recently, Ram and Karwan examined surrogate duality, and exemplified the existence of surrogate duality gaps for a class of mixed integer programming problems. In this paper, we show that the surrogate duality gaps may exist even for integer programming problems and present necessary sufficient conditions for surrogate ( or Langrangion) duality gaps to occur. Then, we extend the results for a class of mixed integer programming problems.

关键词： surrogate duality duality gap mixed integer programming complexity

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Target-Oriented Scheduling in Directional Sensor Networks

引用

IEEE TRANSACTIONS ON COMPUTERS 2009年第9期58卷 1259-1274页

作者： Cai, Yanli Lou, Wei Li, Minglu Li, Xiang-Yang Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200030 Peoples R China Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA

Unlike convectional omnidirectional sensors that always have an omniangle of sensing range, directional sensors may have a limited angle of sensing range due to the technical constraints or cost considerations. A directional sensor network consists of a number of directional sensors, which can switch to several directions to extend their sensing ability to cover all the targets in a given area. Power conservation is still an important issue in such directional sensor networks. In this paper, we address the multiple directional cover sets (MDCS) problem of organizing the directions of sensors into a group of nondisjoint cover sets to extend the network lifetime. One cover set in which the directions cover all the targets is activated at one time. We prove the MDCS to be NP-complete and propose several algorithms for the MDCS. Simulation results are presented to demonstrate the performance of these algorithms.

关键词： Coverage energy conservation mixed integer programming scheduling sensor networks

来源：评论

学校读者我要写书评

暂无评论

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第2期196卷 697-706页

作者： Ferreira, Deisemara Morabito, Reinaldo Rangel, Socorro Univ Fed Sao Carlos Dept Prod Engn BR-13565905 Sao Carlos SP Brazil Sao Paulo State Univ UNESP BR-15054000 Sao Jose Do Rio Preto SP Brazil

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Lot sizing Scheduling Soft drink industry mixed integer programming Relax-and-fix heuristic

来源：评论

学校读者我要写书评

暂无评论

Local and global deadlock prevention policies for resource allocation systems using partially generated reachability graphs

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2009年第4期57卷 1168-1181页

作者： Hu, Hesuan Li, Zhiwu Xidian Univ Sch Electromech Engn Xian 710071 Shaanxi Peoples R China

This paper considers the deadlock prevention problem for a class of conjunctive/disjunctive resource allocation systems (C/D-RAS) which cover relatively general cases in which the multiple resource acquisitions and flexible routings are allowed. First, an improved siphon-based liveness characterization for the Petri nets modeling C/D-RAS is proposed. Subsequently, this characterization facilitates the utilization of a mixed integer programming (MIP) based deadlock prevention policy that can well avoid the explicit enumeration of both siphons and the reachable states. The resulting policy is implemented by an iterative algorithm each step of which is characterized as an MIP formulation in conjunction with both a bad marking detection and a feedback control operation. Finally, the deadlock prevention policy developed in this paper is, respectively, characterized by the local and global ones so as to realize a trade-off between the behavior permissiveness and the structural simplicity of the supervisor. Both the theoretical and experimental results validate the effectiveness and efficiency of such an approach. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Deadlock prevention Resource allocation systems Petri nets mixed integer programming Reachability graph

来源：评论

学校读者我要写书评

暂无评论

Cutting circles and polygons from area-minimizing rectangles

引用

JOURNAL OF GLOBAL OPTIMIZATION 2009年第2-3期43卷 299-328页

作者： Kallrath, Josef BASF AG Sci Comp D-67056 Ludwigshafen Germany Univ Florida Dept Astron Gainesville FL 32611 USA

A set of circles, rectangles, and convex polygons are to be cut from rectangular design plates to be produced, or from a set of stocked rectangles of known geometric dimensions. The objective is to minimize the area of the design rectangles. The design plates are subject to lower and upper bounds of their widths and lengths. The objects are free of any orientation restrictions. If all nested objects fit into one design or stocked plate the problem is formulated and solved as a nonconvex nonlinear programming problem. If the number of objects cannot be cut from a single plate, additional integer variables are needed to represent the allocation problem leading to a nonconvex mixed integer nonlinear optimization problem. This is the first time that circles and arbitrary convex polygons are treated simultaneously in this context. We present exact mathematical programming solutions to both the design and allocation problem. For small number of objects to be cut we compute globally optimal solutions. One key idea in the developed NLP and MINLP models is to use separating hyperplanes to ensure that rectangles and polygons do not overlap with each other or with the circles. Another important idea used when dealing with several resource rectangles is to develop a model formulation which connects the binary variables only to the variables representing the center of the circles or the vertices of the polytopes but not to the non-overlap or shape constraints. We support the solution process by symmetry breaking constraints. In addition we compute lower bounds, which are constructed by a relaxed model in which each polygon is replaced by the largest circle fitting into that polygon. We have successfully applied several solution techniques to solve this problem among them the Branch&Reduce Optimization Navigator (BARON) and the LindoGlobal solver called from GAMS, and, as described in Rebennack et al. [21], a column enumeration approach in which the columns represent the assignme

关键词： Global Optimization mixed integer programming Cutting stock problem Packing problem Shape constraints Non-overlap constraints Design problem Assignment

来源：评论

学校读者我要写书评

暂无评论

A decision support system for cyclic master surgery scheduling with multiple objectives

引用

JOURNAL OF SCHEDULING 2009年第2期12卷 147-161页

作者： Belien, Jeroen Demeulemeester, Erik Cardoen, Brecht Hogesch Univ Brussel Res Ctr Modelling & Simulat B-1000 Brussels Belgium Katholieke Univ Leuven Dept Decis Sci & Informat Management Fac Business & Econ B-3000 Louvain Belgium

This paper presents a decision support system for cyclic master surgery scheduling and describes the results of an extensive case study applied in a medium-sized Belgian hospital. Three objectives are taken into account when building the master surgery schedule. First of all, the resulting bed occupancy at the hospitalization units should be leveled as much as possible. Second, a particular operating room is best allocated exclusively to one group of surgeons having the same speciality;i.e., operating rooms should be shared as little as possible between different surgeon groups. Third, the master surgery schedule is preferred to be as simple and repetitive as possible, with few changes from week to week. The system relies on mixed integer programming techniques involving the solution of multi-objective linear and quadratic optimization problems, and on a simulated annealing metaheuristic.

关键词： Master surgery scheduling Decision support system mixed integer programming Simulated annealing Case study

来源：评论

学校读者我要写书评

暂无评论

LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第4期36卷 1064-1089页

作者： Boland, Natashia Dumitrescu, Irina Froyland, Gary Gleixner, Ambros M. Univ New S Wales Sch Math & Stat Sydney NSW 2052 Australia Univ Melbourne Dept Math & Stat Parkville Vic 3010 Australia Tech Univ Berlin Inst Math D-10623 Berlin Germany

Given a discretisation of an orebody as a block model. the open pit mining production scheduling problem (OPMPSP) consists of finding the sequence in which the blocks should be removed from the pit., over the lifetime of the mine, such that the net present value (NPV) of the operation is maximised. In practice. due to the large number of blocks and precedence constraints linking them, blocks are typically aggregated to form larger scheduling units. We aim to solve the OPMPSP, formulated as a mixed integer programme (MIP), so that aggregates are used to schedule the mining process, while individual blocks are used for processing decisions. We propose an iterative disaggregation method that refines the aggregates (with respect to processing) up to the point where the refined aggregates defined for processing produce the same optima I solution for the linear programming (LP) relaxation of the MIP as the optimal solution of the LP relaxation with individual block processing. We propose several strategies of creating refined aggregates for the MIP processing, using duality results and exploiting the problem structure. These refined aggregates allow the solution of very large problems in reasonable time with very high solution quality in terms of NPV. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： Open pit mining Constrained scheduling problems Net present value Aggregation Iterative disaggregation mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：