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

A COMPUTATIONALLY EFFICIENT FPTAS FOR CONVEX STOCHASTIC DYNAMIC PROGRAMS

SIAM JOURNAL ON OPTIMIZATION 2015年第1期25卷 317-350页

作者： Halman, Nir Nannicini, Giacomo Orlin, James Hebrew Univ Jerusalem Jerusalem Sch Business Adm Jerusalem Israel MIT Dept Civil & Environm Engn Cambridge MA 02139 USA Singapore Univ Technol & Design Engn Syst & Design Singapore Singapore MIT Sloan Sch Management Cambridge MA 02139 USA

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of K-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674-685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set.

关键词： dynamic programming approximation algorithms inventory control fully polynomial-time approximation scheme discrete convexity

来源：评论

学校读者我要写书评

暂无评论

Static and dynamic source locations in undirected networks

引用

TOP 2015年第3期23卷 619-646页

作者： Turner, Lara Gross, Dwi Poetranto Hamacher, Horst W. Krumke, Sven O. Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany INFORM GmbH D-52076 Aachen Germany

Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented;for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.

关键词： Source location problem Single cover problem Matroid (Dual) greedy algorithm (Minimal) deficient set Plural cover problem Tree network Linear algorithm Pseudo-polynomial algorithm fully polynomial-time approximation scheme Dynamic flow NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of evacuation routes on a three-dimensional geometric network

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2014年 76卷 231-242页

作者： Tang, Huajun Elalouf, Amir Levner, Eugene Cheng, T. C. E. Macau Univ Sci & Technol Sch Business Macau Peoples R China Bar Ilan Univ Dept Management Ramat Gan Israel Ashkelon Acad Coll Sch Econ Ashqelon Israel Hong Kong Polytech Univ Fac Business Hong Kong Hong Kong Peoples R China

We consider a real-time emergency evacuation problem that seeks to compute a set of rapid evacuation routes in a building. Given a three-dimensional geometric structure of the evacuation network, an emergency evacuation route is a sequence of movements of people away from the threat or actual occurrence of a hazard (such as a fire, a hidden bomb) to a safe exit in the network. In such a network each room/crossing/exit in the building is designated as a node and the corridors/staircases/links between the rooms are edges. The evacuation times assigned to the edges are normally distributed random variables. This stochastic routing problem subject to deadline constraints is NP-hard. We provide a new pseudo-polynomial-time dynamic programming algorithm to solve this problem. Based on this algorithm, we construct two types of approximation algorithm, namely a fully polynomial-time approximation scheme providing "almost-optimal" solutions and a fully polynomial-time approximately feasible scheme yielding a best "almost feasible" solution. We present a case study and results of computational experiments to illustrate the working and efficacy of the proposed solution methods, respectively. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Real-time emergency routing No-notice building evacuation Dynamic programming fully polynomial-time approximation scheme fully polynomial-time approximately feasible scheme

来源：评论

学校读者我要写书评

暂无评论

A new graphical approach for solving single-machine scheduling problems approximately

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2014年第13期52卷 3762-3777页

作者： Gafarov, Evgeny R. Dolgui, Alexandre Werner, Frank Ecole Natl Super Mines UMR CNRS 6158 LIMOS F-42023 St Etienne France Russian Acad Sci Inst Control Sci Moscow Russia Univ Magdeburg Fak Math D-39106 Magdeburg Germany

Often the problem of determining an optimal or approximate production schedule in a company can be reduced to the problem of solving a scheduling problem on a bottleneck machine. However, even the majority of the resulting single-machine scheduling problems are NP-hard from a computational point of view and, therefore, it is difficult to solve large instances of such problems exactly. In this paper, we consider five such single-machine problems, where a dynamic programming algorithm of pseudo-polynomial complexity exists. The running time of such an algorithm can often be improved by so-called graphical algorithms which do not need to consider all states in a dynamic programming algorithm separately. Based on such graphical algorithms, we present fully polynomial-time approximation schemes (FPTASes) for five single-machine total tardiness problems. The new FPTASes have the best running time among the known approximation schemes for these problems. The presented approach is rather general and can be applied to many other scheduling and combinatorial optimisation problems as well.

关键词： single-machine scheduling total weighted tardiness graphical algorithm fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Single Machine Scheduling with an Availability Constraint and Rejection

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2014年第5期31卷 1450037-1450037页

作者： Zhao, Chuanli Tang, Hengyong Shenyang Normal Univ Sch Math & Syst Sci Shenyang 110034 Liaoning Peoples R China

This paper considers single machine scheduling with an availability constraint and rejection. It is assumed that the machine is not available for processing during a given time interval. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the weighted total completion time of the accepted jobs and the total rejection penalty of the rejected jobs. For this NP-hard problem, we present a pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS).

关键词： Scheduling machine availability rejection penalty dynamic programming fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Route-Enabling Graph Orientation Problems

引用

ALGORITHMICA 2013年第2期65卷 317-338页

作者： Ito, Takehiro Miyamoto, Yuichiro Ono, Hirotaka Tamaki, Hisao Uehara, Ryuhei Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Sophia Univ Fac Sci & Technol Chiyoda Ku Tokyo 1028554 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan Meiji Univ Sch Sci & Technol Tama Ku Kawasaki Kanagawa 2148571 Japan JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan

Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider two problems of finding an orientation of all edges in G: min-sum orientation is to minimize the sum of the shortest directed distances between all st-pairs;and min-max orientation is to minimize the maximum shortest directed distance among all st-pairs. Note that these shortest directed paths for st-pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomial time, whereas min-max orientation remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st-pairs is a fixed constant.

关键词： approximation algorithm Cactus Dynamic programming fully polynomial-time approximation scheme Graph orientation Planar graph Reachability

来源：评论

学校读者我要写书评

暂无评论

A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2007年第1-2期109卷 180-184页

作者： Kang, Liying Ng, C. T. Shanghai Univ Dept Math Shanghai 200444 Peoples R China Hong Kong Polytech Univ Dept Logist Hong Kong Peoples R China

In this paper we study the NP-hard problem of scheduling n deteriorating jobs on in identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only. (c) 2007 Elsevier B.V. All rights reserved.

关键词： deteriorating jobs fully polynomial-time approximation scheme parallel-machine scheduling

来源：评论

学校读者我要写书评

暂无评论

Scheduling resumable deteriorating jobs on a single machine with non-availability constraints

引用

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 275-280页

作者： Fan, Baoqiang Li, Shisheng Zhou, Li Zhang, Liqi Ludong Univ Dept Math & Informat Yantai 264025 Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Peoples R China

We consider a problem of scheduling resumable deteriorating jobs on a single machine with non-availability constraints. The objective is to minimize the total completion time. We prove that the problem with a single non-availability period is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. In addition, we show that there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio for the problem with two or more non-availability periods, unless P = NP. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling Deteriorating job Non-availability constraint fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Parallel-machine scheduling with deteriorating jobs and rejection

引用

THEORETICAL COMPUTER SCIENCE 2010年第40-42期411卷 3642-3650页

作者： Li, Shisheng Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

We consider several parallel-machine scheduling problems in which the processing time of a job is a (simple) linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. Three variations of the scheduling cost are considered in this paper. The first is the makespan, the second is the total weighted completion time (for simple linear deterioration), and the third is the total completion time. For the former two problems, we propose two fully polynomial-time approximation schemes to solve them when the number of machines is fixed. For the last problem, we present an optimal O(n(2))-time dynamic programming algorithm when the deteriorating rates are equal for all jobs. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling Deteriorating jobs Rejection fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Complexity and approximability of scheduling resumable proportionally deteriorating jobs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第1期200卷 305-308页

作者： Gawiejnowicz, Stanislaw Kononov, Alexander Adam Mickiewicz Univ Fac Math & Comp Sci PL-61614 Poznan Poland Sobolev Inst Math Novosibirsk 630090 Russia

A set of independent, resumable and proportionally deteriorating jobs is to be executed on a single machine. The machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. The criterion of schedule optimality is the maximum completion time. It is proved that the decision version of the problem with a single non-availability period is ordinarily NP-complete. It is also proved that for the problem with a single non-availability period there exists a fully polynomial-time approximation scheme. Finally, it is proved that for the problem with two or more non-availability periods there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio, unless P = NP. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Scheduling Deteriorating jobs Complexity theory fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：