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

Dynamic Inventory Relocation in Disaster Relief^†

PRODUCTION AND OPERATIONS MANAGEMENT 2022年第3期31卷 1052-1070页

作者： Zhang, Yuli Richter, Amber R. Shanthikumar, Jeyaveerasingam George Shen, Zuo-Jun Max Beijing Inst Technol Sch Management & Econ Beijing 100081 Peoples R China Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA Univ Calif Berkeley Coll Engn Berkeley CA 94720 USA Univ Hong Kong Fac Engn Hong Kong 999077 Peoples R China Univ Hong Kong Fac Business & Econ Hong Kong 999077 Peoples R China

This study investigates dynamic inventory relocation to respond proactively to the changing relief demand forecasts over time. In particular, we examine how to relocate mobile inventory optimally to serve nonstationary stochastic demand at several potential disaster sites. We propose a dynamic relocation model using dynamic programming (DP) and develop both analytical and numerical results regarding optimal relocation policies, the minimum cost-to-go function, and the value of inventory mobility over traditional warehouse pre-positioning. Given the computational complexity of the backwards DP algorithm, we develop a base state heuristic (BSH) for general problems by exploiting the real-world disaster pattern of occurrence. For problems with temporally independent demand, we propose a polynomial time exact algorithm based on a spatial-temporal graph. For problems with spatially independent demand, we design a speedup technique to implement BSH in polynomial time. The proposed model and algorithms are further extended to consider the impact of transportation uncertainties. Numerical experiments show that the proposed algorithms return high-quality decisions only in a small fraction of the time required by an exact algorithm and a myopic algorithm. The proposed model and algorithms are applicable to any type of mobile inventory, facility, or server in similar settings.

关键词： disaster relief mobile inventory dynamic facility location inventory pre-positioning polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Serial batch scheduling on uniform parallel machines to minimize total completion time

引用

INFORMATION PROCESSING LETTERS 2014年第12期114卷 692-695页

作者： Li, Song-Song Zhang, Yu-Zhong Qufu Normal Univ Sch Management Rizhao 276826 Peoples R China

We consider two scheduling problems on in uniform serial batch machines where m is fixed. In the first problem, all jobs have to be scheduled and the objective is to minimize total completion time. In the second problem, each job may be either rejected or accepted to be scheduled and the objective is to minimize the sum of total completion time and total rejection penalty. A polynomial time procedure is presented to solve both problems with the time complexity O (m(2)n(m+2)) and O (m(2)n(m+5)), respectively. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Scheduling Serial batch Parallel machine Total completion time Rejection polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Bandwidth of trees of diameter at most 4

引用

DISCRETE MATHEMATICS 2012年第12-13期312卷 1947-1951页

作者： Bilinski, Mark Choi, Kwang Ju Chun, Deborah Ding, Guoli Dziobiak, Stan Farnham, Rodrigo Iverson, Perry Leu, Shirley Lowrance, Lisa Warshauer Louisiana State Univ Dept Math Baton Rouge LA 70803 USA

For a graph G, let gamma : v(G) -> {1, .... vertical bar V(G)vertical bar} be a one-to-one function. The bandwidth of gamma is the maximum of vertical bar gamma (u) - gamma(v)vertical bar over uv is an element of E(C). The bandwidth of G, denoted b(G), is the minimum bandwidth over all embeddings gamma, b(G) = Min(gamma) {max{vertical bar gamma(u) - gamma(v)vertical bar : uv is an element of E(G)}}. In this paper, we show that the bandwidth computation problem for trees of diameter at most 4 can be solved in polynomial time. This naturally complements the result computing the bandwidth for 2-caterpillars. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Bandwidth Tree polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Routing of uncertain traffic demands

引用

OPTIMIZATION AND ENGINEERING 2005年第3期6卷 283-313页

作者： Ben-Ameur, W Kerivin, H Inst Natl Telecommun GET CNRS Samavor Inst Natl Telecommun F-91011 Evry France Univ Minnesota Inst Math & Applicat Minneapolis MN 55455 USA

Due to the success of the Internet and the diversity of communication applications, it is becoming increasingly difficult to forecast traffic patterns. To capture the traffic variations, we introduce a flexible model where traffic belongs to a polytope. We assume that the traffic demands between nodes can be carried on many paths, with respect to network resources. Moreover, to guarantee the network stability and to make the routing easy to implement, the proportions of traffic flowing through each path have to be independent of the current traffic demands. We show that a minimum-cost routing satisfying the previous properties can be efficiently computed by column and constraint generations. We then present several strategies related to certain algorithmic details. Finally, theoretical and computational studies show that this new flexible model can be much more economical than a classical deterministic model based on a given traffic matrix. This paper can be considered as a mathematical framework for a new flexible virtual private network service offer. It also introduces a new concept: the routing of a polytope.

关键词： network design traffic uncertainty polyhedral model routing polynomial time algorithm virtual private network

来源：评论

学校读者我要写书评

暂无评论

Counting the number of independent sets in chordal graphs

引用

JOURNAL OF DISCRETE algorithmS 2008年第2期6卷 229-242页

作者： Okamoto, Yoshio Uno, Takeaki Uehara, Ryuhei Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets;(2) a linear-time algorithm for counting the number of maximum independent sets;(3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets;(2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate. (C) 2007 Elsevier B.V. All rights reserved.

关键词： Chordal graph Counting Enumeration Independent set NP-completeness #P-completeness polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

The complexity of the equation solvability and equivalence problems over finite groups

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2020年第3期30卷 607-623页

作者： Foldvari, Attila Horvath, Gabor Charles Univ Prague Dept Algebra Sokolovska 83 Prague 18600 8 Czech Republic Univ Debrecen Inst Math Pf 400 H-4002 Debrecen Hungary

We provide a polynomial time algorithm for deciding the equation solvability problem over finite groups that are semidirect products of a p-group and an Abelian group. As a consequence, we obtain a polynomial time algorithm for deciding the equivalence problem over semidirect products of a finite nilpotent group and a finite Abelian group. The key ingredient of the proof is to represent group expressions using a special polycyclic, presentation of these finite solvable groups.

关键词： Semidirect product of groups equation solvability equivalence computational complexity polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On solving a non-convex quadratic programming problem involving resistance distances in graphs

引用

ANNALS OF OPERATIONS RESEARCH 2020年第2期287卷 643-651页

作者： Dubey, Dipti Neogy, S. K. Indian Stat Inst 7 SJS Sansanwal Marg New Delhi 110016 India

Quadratic programming problems involving distance matrix (D) that arises in trees are considered in the literature by Dankelmann (Discrete Math 312:12-20, 2012), Bapat and Neogy (Ann Oper Res 243:365-373, 2016). In this paper, we consider the question of solving the quadratic programming problem of finding maximum of x(T)Rx subject to x being a nonnegative vector with sum 1 and show that for the class of simple graphs with resistance distance matrix (R) which are not necessarily a tree, this problem can be reformulated as a strictly convex quadratic programming problem. An application to symmetric bimatrix game is also presented.

关键词： Resistance distance Laplacian matrix Non-convex quadratic programming polynomial time algorithm Symmetric bimatrix game

来源：评论

学校读者我要写书评

暂无评论

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

引用

MATHEMATICAL PROGRAMMING 2000年第3期87卷 519-542页

作者： Deineko, VG Woeginger, GJ Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England Graz Univ Technol Inst Math A-8010 Graz Austria

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods. First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be declined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. we identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably lends to an NP-complete optimization problem for the QAP.

关键词： neighborhood local search search problem Travelling Salesman Problem Quadratic Assignment Problem polynomial time algorithm NP-completeness combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL COMPLEXITY OF SYSTEM DIAGNOSIS

引用

IEEE TRANSACTIONS ON COMPUTERS 1978年第10期27卷 881-885页

作者： FUJIWARA, H KINOSHITA, K Department of Electronic Engineering Osaka University

In this paper we analyze the computational complexity of system diagnosis. We show that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop s... 详细信息

关键词： Turing Machines Fault Diagnosis polynomial time algorithm polynomially Complete Self Diagnosable Systems

来源：评论

学校读者我要写书评

暂无评论

MINIMIZING SETUPS IN ORDERED SETS OF FIXED WIDTH

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 1985年第3期1卷 225-229页

作者： COLBOURN, CJ PULLEYBLANK, WR UNIV WATERLOO DEPT COMP SCIWATERLOO N2L 3G1ONTARIOCANADA UNIV WATERLOO DEPT COMBINATORIES & OPTIMIZATWATERLOO N2L 3G1ONTARIOCANADA

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a mo... 详细信息

关键词： Primary 06A10 secondary 05C99 68E99 ordered set jump number width setup number polynomial time algorithm dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：