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

TOWARD BREAKING THE CURSE OF DIMENSIONALITY: AN FPTAS FOR STOCHASTIC DYNAMIC PROGRAMS WITH MULTIDIMENSIONAL ACTIONS AND SCALAR STATES

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1131-1163页

作者： Halman, Nir Nannicini, Giacomo Hebrew Univ Jerusalem Jerusalem Sch Business Adm IL-91905 Mt Scopus Israel IBM Corp TJ Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY 10598 USA

We propose a fully polynomial-time approximation scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs, and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single nondiscrete resource over a finite time horizon. We show that under a value oracle model for the cost functions this result for one-dimensional state space is the "best possible," because a similar dynamic programming model with two-dimensional state space does not admit a polynomial-time approximation scheme. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing, under suitable conditions, how to deal with multidimensional action spaces and with vectors of continuous random variables with bounded support. These results bring us one step closer to overcoming the curse of dimensionality of dynamic programming.

关键词： dynamic programming approximation algorithms fully polynomial-time approximation scheme multistage linear programming

来源：评论

学校读者我要写书评

暂无评论

Lot-sizing with non-stationary cumulative capacities

引用

OPERATIONS RESEARCH LETTERS 2007年第4期35卷 549-557页

作者： Sargut, F. Zeynep Romeijn, H. Edwin Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave. (c) 2006 Elsevier B.V All rights reserved.

关键词： capacitated lot-sizing fully polynomial-time approximation scheme Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Parallel-machine scheduling of deteriorating jobs with potential machine disruptions

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2017年 69卷 17-28页

作者： Yin, Yunqiang Wang, Yan Cheng, T. C. E. Liu, Wenqi Li, Jinhai Kunming Univ Sci & Technol Fac Sci Kunming Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machifies will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Deteriorating jobs Disruptive environment 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

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with release dates and rejection

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第3期198卷 975-978页

作者： Zhang, Liqi Lu, Lingfa Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

In this paper, we consider the single machine scheduling problem with release dates and rejection. 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 makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. (C) 2008 Published by Elsevier B.V.

关键词： Scheduling Rejection penalty 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

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling under the job rejection constraint

引用

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1877-1882页

作者： Zhang, Liqi Lu, Lingfa Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion f is minimized, where f is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. (C) 2010 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the two identical parallel machine problem under machine availability constraints

引用

JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING 2023年第1期40卷 54-67页

作者： Nguyen, Anh H. G. Sheen, Gwo-Ji Yeh, Yingchieh Natl Cent Univ Inst Ind Management Taoyuan Taiwan

This study addresses the scheduling problem of two identical parallel machines with the objective of minimizing the total completion time under the machine availability constraints. To the best of our knowledge, this study is the first to develop a fully polynomial-time approximation scheme (FPTAS), a solution method which has been neglected in past studies, to solve the studied problem. The FPTAS, which is based on a dynamic programming algorithm is developed by applying a trimming-the-state-space approach. Theoretical proofs of the error bound and the time complexity for the proposed FPTAS are also provided. The computational results indicate that the proposed FPTAS performs more efficiently than a dynamic programming algorithm in terms of both run time and problem size. The error bound of the FPTAS is demonstrated to be within the pre-specified error bound.

关键词： Parallel machine scheduling machine availability constraints dynamic programming algorithm fully polynomial-time approximation scheme trimming-the-state-space approach

来源：评论

学校读者我要写书评

暂无评论

On the complexity of approximating a KKT point of quadratic programming

引用

MATHEMATICAL PROGRAMMING 1998年第2期80卷 195-211页

作者： Ye, YY Univ Iowa Coll Business Adm Dept Management Sci Iowa City IA 52242 USA

We present a potential reduction algorithm to approximate a Karush-Kuhn-Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy epsilon is an element of (0,1) is O((1/epsilon) log(1/epsilon) log(log(1/epsilon))), compared to the previously best-known result O((1/epsilon)(2)). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. (C) 1998 The Mathematical Programming Society,Inc. Published by Elsevier Science B.V.

关键词： quadratic programming KKT point local minimizer fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation issues of fractional knapsack with penalties: a note

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2022年第2期20卷 209-216页

作者： Kovalev, Sergey INSEEC U Res Ctr INSEEC Sch Business & Econ 25 Rue Univ F-69007 Lyon France

Malaguti et al. introduce (Eur J Oper Res 273:874-888, 2019) the Fractional Knapsack Problem with Penalties, which is similar to the classical 0-1 Knapsack problem, except that each of the n variables associated with one of the n items can take any value from the interval [0, 1], and values other than 0 and 1 are penalized. They state that the problem is NP-hard in the ordinary sense as a generalization of the classical 0-1 knapsack problem and develop a fully polynomial-time approximation scheme for the case of non-negative non-decreasing profit functions. It is demonstrated that, unless P = NP, no polynomial-time approximation algorithm with any approximation ratio exists for the case of polynomially defined, polynomially computable, discontinuous and non-monotone penalty functions even if there is a single item. A fully polynomial-time approximation scheme which is roughly n times faster than the one of Malaguti et al. for the same case is also presented.

关键词： Knapsack problem Computational complexity fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：