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

A flexible, fast, and optimal modeling approach applied to crew rostering at London underground

ANNALS OF OPERATIONS RESEARCH 2004年第1-4期127卷 259-281页

作者： Sodhi, MS Norris, S City Univ London Cass Business Sch London England London Underground London England

We present a general modeling approach to crew rostering and its application to computer-assisted generation of rotation-based rosters ( or rotas) at the London Underground. Our goals were flexibility, speed, and optimality, and our approach is unique in that it achieves all three. Flexibility was important because requirements at the Underground are evolving and because specialized approaches in the literature did not meet our flexibility-implied need to use standard solvers. We decompose crew rostering into stages that can each be solved with a standard commercial MILP solver. Using a 167 MHz Sun UltraSparc 1 and CPLEX 4.0 MILP solver, we obtained high-quality rosters in runtimes ranging from a few seconds to a few minutes within 2% of optimality. Input data were takes from different depots with crew sizes ranging from 30 - 150 drivers, i.e., with number of duties ranging from about 200 - 1000. Using an argument based on decomposition and aggregation, we prove the optimality of our approach for the overall crew rostering problem.

关键词： crew rostering rota mixed-integer linear programming cyclic graph decomposition aggregation

来源：评论

学校读者我要写书评

暂无评论

Intraprogram Dynamic Voltage Scaling: Bounding Opportunities with Analytic Modeling

引用

ACM Transactions on Architecture and Code Optimization 2004年第3期1卷 323-367页

作者： Xie, Fen Martonosi, Margaret Malik, Sharad Department of Electrical Engineering Princeton University Equad C305 Princeton NJ 08544 United States

Dynamic voltage scaling (DVS) has become an important dynamic power-management technique to save energy. DVS tunes the power-performance tradeoff to the needs of the application. The goal is to minimize energy consumption while meeting performance needs. Since CPU power consumption is strongly dependent on the supply voltage, DVS exploits the ability to control the power consumption by varying a processor's supply voltage and clock frequency. However, because of the energy and time overhead associated with switching DVS modes, DVS control has been used mainly at the interprogram level. In this paper, we explore the opportunities and limits of intraprogram DVS scheduling. An analytical model is derived to predict the maximum energy savings that can be obtained using intraprogram DVS given a few known program and processor parameters. This model gives insights into scenarios where energy consumption benefits from intraprogram DVS and those where there is no benefit. The model helps us extrapolate the benefits of intraprogram DVS into the future as processor parameters change. We then examine how much of these predicted benefits can actually be achieved through compile-time optimal settings of DVS modes. We extend an existing mixed-integer linear program formulation for this scheduling problem by accurately accounting for DVS energy switching overhead, by providing finer-grained control on settings and by considering multiple data categories in the optimization. Overall, this research provides a comprehensive view of intraprogram compile-time DVS management, providing both practical techniques for its immediate deployment as well theoretical bounds for use into the future. © 2004, ACM. All rights reserved.

关键词： Analytical model Compiler Design Dynamic voltage scaling Experimentation Low power mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Optimal scheduling of casting sequence using genetic algorithms

引用

MATERIALS AND MANUFACTURING PROCESSES 2003年第3期18卷 409-432页

作者： Deb, K Reddy, AR Singh, G Indian Inst Technol Dept Mech Engn Kanpur Genet Algorithms Lab Kanpur 208016 Uttar Pradesh India

Scheduling a casting sequence involving a number of orders with different casting weights and satisfying due dates of is an important optimization problem often encountered in foundries. In this article, we attempt to solve this complex, multi-variable, and multi-constraint optimization problem by using different implementations of genetic algorithms (GAs). In comparison with a mixed-integer linear programming solver, GAs with problem-specific operators are found to provide faster (with a subquadratic computational time complexity) and more reliable solutions to very large (more than 1 million integer variables) casting sequence optimization problems. In addition to solving the particular problem, the study demonstrates how problem-specific information can be introduced in a GA for solving complex real-world problems.

关键词： scheduling genetic algorithms large-scale optimization mixed-integer linear programming knowledge-based GA scalable optimization subquadratic complexity

来源：评论

学校读者我要写书评

暂无评论

Transmission expansion planning: A mixed-integer LP approach

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2003年第3期18卷 1070-1077页

作者： Alguacil, N Motto, AL Conejo, AJ Univ Castilla La Mancha Dept Elect Engn E-13071 Ciudad Real Spain McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 2A7 Canada

This paper presents a mixed-integer LP approach to the solution of the long-term transmission expansion planning problem. In general, this problem is large-scale, mixed-integer, nonlinear, and nonconvex. We derive a mixed-integer linear formulation that considers losses and guarantees convergence to optimality using existing optimization software. The proposed model is applied to Garver's 6-bus system, the IEEE Reliability Test System, and a realistic Brazilian system. Simulation results show the accuracy as well as the efficiency of the proposed solution technique.

关键词： linearized power flow mixed-integer linear programming power loss modeling transmission expansion planning

来源：评论

学校读者我要写书评

暂无评论

Compile-time dynamic voltage scaling settings: Opportunities and limits 03

引用

Conference on programming Language Design and Implementation

作者： Xie, F Martonosi, M Malik, S Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

ISBN: (纸本)9781581136623

With power-related concerns becoming dominant aspects of hardware and software design, significant research effort has been devoted towards system power minimization. Among run-time power-management techniques, dynamic voltage scaling (DVS) has emerged as an important approach, with the ability to provide significant power savings. DVS exploits the ability to control the power consumption by varying a processor's supply voltage (V) and clock frequency (f). DVS controls energy by scheduling different parts of the computation to different (V, f) pairs;the goal is to minimize energy while meeting performance needs. Although processors like the Intel XScale and Transmeta Crusoe allow software DVS control, such control has thus far largely been used at the process/task level under operating system control. This is mainly because the energy and time overhead for switching DVS modes is considered too large and difficult to manage within a single program. In this paper we explore the opportunities and limits of compile-time DVS scheduling. We derive an analytical model for the maximum energy savings that can be obtained using DVS given a few known program and processor parameters. We use this model to determine scenarios where energy consumption benefits from compile-time DVS and those where there is no benefit. The model helps us extrapolate the benefits of compile-time DVS into the future as processor parameters change. We then examine how much of these predicted benefits can actually be achieved through optimal settings of DVS modes. This is done by extending the existing mixed-integer linear Program (MILP) formulation for this problem by accurately accounting for DVS energy switching overhead, by providing finer-grained control on settings and by considering multiple data categories in the optimization. Overall, this research provides a comprehensive view of compile-time DVS management, providing both practical techniques for its immediate deployment as well theoretical

关键词： low power compiler dynamic voltage scaling mixed-integer linear programming analytical model

来源：评论

学校读者我要写书评

暂无评论

System-on-a-chip test scheduling with precedence relationships, preemption, and power constraints

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2002年第9期21卷 1088-1094页

作者： Iyengar, V Chakrabarty, K IBM Microelectron Essex Jct VT 05452 USA Duke Univ Dept Elect & Comp Engn Durham NC 27708 USA

Test scheduling is an important problem in system-on-a-chip (SOC) test automation. Efficient test schedules minimize the overall system test application time, avoid test resource conflicts, and limit power dissipation during test mode. In this paper, we present an integrated approach to several test scheduling problems. We first present a method to determine optimal schedules for reasonably sized SOCs with precedence relationships, i.e., schedules that preserve desirable orderings among tests. We also present an efficient heuristic algorithm to schedule tests for large SOCs with precedence constraints in polynomial time. We describe a novel algorithm that uses preemption of tests to obtain efficient schedules for SOCs. Experimental results for an academic SOC and an industrial SOC show that efficient test schedules can be obtained in reasonable CPU time.

关键词： core-based systems embedded core testing mixed-integer linear programming open shop schedules precedence constraints preemptive test scheduling

来源：评论

学校读者我要写书评

暂无评论

Network-constrained multiperiod auction for a pool-based electricity market

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2002年第3期17卷 646-653页

作者： Motto, AL Galiana, FD Conejo, AJ Arroyo, JM McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 2A7 Canada Univ Castilla La Mancha Dept Elect Engn E-13071 Ciudad Real Spain

This paper presents a multiperiod electricity auction market tool that explicitly takes into account transmission congestion and losses as well as intertemporal operating constraints such as start-up costs, ramp rates, and minimum up and down times that may be included in any generating unit's composite bid. This approach, which requires only existing mixed-integer linear solvers, provides the market operator with a valuable tool for scheduling participants in a competitive market where transparency, fairness, and confidentiality of participants' data are of paramount concern. Indeed, under this framework, only network data are of public domain;producers are not required to reveal corporate data, and they have more flexibility in specifying the structure of their composite bid. This paper demonstrates and illustrates, through numerical studies using test systems, that an efficient and fair competitive electricity market can be implemented, taking into account network constraints and losses.

关键词： congestion management mixed-integer linear programming nodal pricing pool-based electricity market social welfare maximization

来源：评论

学校读者我要写书评

暂无评论

Arterial-based control of traffic flow in urban grid networks

引用

MATHEMATICAL AND COMPUTER MODELLING 2002年第5-6期35卷 657-671页

作者： Gartner, NH Stamatiadis, C Univ Massachusetts Dept Civil & Environm Engn Lowell MA 01854 USA

Urban networks are typically composed of a grid of arterial streets. Optimal control of the traffic signals in the grid system is essential for the effective operation of the network. In this paper, we present mathematical programming models for the development of optimal arterial-based progression schemes. Such schemes are widely used for traffic signal control in arterial streets. Under such a scheme, a continuous green band is provided in each direction along the artery at the desired speed of travel to facilitate the movement of through traffic along the arterial. Traditional schemes consist of uniform-width progressions. New approaches generate variable bandwidth progressions in which each directional road section is allocated an individually weighted band that can be adapted to the prevailing traffic flows on that link. mixed-integer linear programming is used for the optimization. Simulation results indicate that this method can produce considerable gains in performance when compared with traditional progression methods. By introducing efficient computational techniques, this method also lends itself to a natural extension for incorporation in a dynamic traffic management system. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： traffic flow traffic control traffic signals bandwidth progression mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

An effective formulation for short-term scheduling of multipurpose batch plants

An effective formulation for short-term scheduling of multip...

引用

20th Annual American Control Conference (ACC)

作者： Chen, CL Zong, XJ Shao, HH Dai, XM Shanghai Jiao Tong Univ Inst Automat Shanghai 200030 Peoples R China

ISBN: (纸本)0780372980

This paper presents a mixed-integer linear programming (MILP) mathematic model for short-term scheduling of multipurpose batch plants based on the representation of State Task Network (STN) for processes. When the model is built, the assignment of tasks and units is handled through one set of binary variables and the continuous-time representation is used. The model involves less binary variables, continuous variables and constraints than any other existing model. In order to improve the computational efficiency further, some effective techniques are developed to cut down the size of the proposed model based on the characteristics of batch plants and the model. Examples reveal the effectiveness of the model and improvement techniques.

关键词： production control chemical technology multivariable control systems integer programming linear programming optimal control batch processing (industrial) continuous time systems multipurpose batch plants short-term scheduling mixed-integer linear programming state task network representation binary variables continuous-time representation continuous variables computational efficiency production activity scheduling

来源：评论

学校读者我要写书评

暂无评论

Design of survivable networks with a single facility 2

Design of survivable networks with a single facility

引用

2nd European Conference on Universal Multiservice Networks

作者： Kerivin, H Pham, TTL Nace, D Geffard, J France Telecom R&D Optimizat Architectures & Traff R&D Lab F-92794 Issy Les Moulineaux France

ISBN: (纸本)0780374223

In this paper we focus on the single facility capacitated survivable network design problem. We optimize simultaneously the topology, the link dimensioning for the nominal state as well as for the single link failure state when the survivable conditions are expressed by various rerouting strategies. We present an (mixed) integer mathematical approach that consists of several methodologies. To address the high dimensionality we use Benders' decomposition, and in parallel a Branch-and-Bound method and a cutting plane approach. Beyond the interest of the proposed approach itself, we have considered and compared two well,known restoration technics as local rerouting and end-to-end rerouting. Numerous computational results for realistic instance networks are given to compare these rerouting mechanisms in terms of installed capacities as well as overall costs with respect to topology requirements.

关键词： survivable networks dimensioning network topology rerouting strategies mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：