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

Batch scheduling and common due-date assignment on a single machine

DISCRETE APPLIED MATHEMATICS 1996年第3期70卷 231-245页

作者： Cheng, TCE Kovalyov, MY BYELARUSSIAN ACAD SCI INST ENGN CYBERNET MINSK 220012 BELARUS

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches;jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.

关键词： scheduling batching due-date assignment dynamic programming fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A Dynamic Programming Approach for the Decentralized Control of Energy Retrofit in Large-Scale Street Lighting Systems

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2020年第3期17卷 1140-1157页

作者： Carli, Raffaele Dotoli, Mariagrazia Politecn Bari Dept Elect & Informat Engn I-70125 Bari Italy

This article proposes a decision-making procedure that supports the city energy manager in determining the optimal energy retrofit plan of an existing public street lighting system throughout a wide urban area. The proposed decision model aims at simultaneously maximizing the energy consumption reduction and achieving an optimal allocation of the retrofit actions among the street lighting subsystems, while efficiently using the available budget. The resulting optimization problem is formulated as a quadratic knapsack problem. The proposed solution relies on a decentralized control algorithm that combines discrete dynamic programming with additive decomposition and value functions approximation. The optimality and complexity of the presented strategy are investigated, demonstrating that the proposed algorithm constitutes a fully polynomial approximation scheme. Simulation results related to a real street lighting system in the city of Bari (Italy) are presented to show the effectiveness of the approach in the optimal energy management of large-scale street lighting systems. Note to Practitioners-This article addresses the emerging need for decision support tools for the energy management of urban street lighting systems. The proposed decision-making strategy allows city energy managers and local policy makers taking retrofit decisions on an existing public street lighting system throughout a wide urban area. The presented strategy can be implemented in any engineering software, providing decision makers with a low-complexity and scalable Information and Communication Technology (ICT) tool for the optimization of the energy efficiency and environmental sustainability of street lighting systems.

关键词： Lighting Urban areas Optimization Tools Dynamic programming Decision making Decentralized control Decision-making dynamic programming energy management fully polynomial approximation scheme optimization urban street lighting

来源：评论

学校读者我要写书评

暂无评论

Improved approximation schemes for scheduling unrelated parallel machines

引用

MATHEMATICS OF OPERATIONS RESEARCH 2001年第2期26卷 324-338页

作者： Jansen, K Porkolab, L Univ Kiel Inst Informat & Prakt Math D-2300 Kiel Germany Univ London Imperial Coll Sci Technol & Med Dept Comp London England

We consider the problem of scheduling n independent jobs on m unrelated parallel machines where each job has to be processed by exactly one machine, processing job j on machine i requires p(ij) time units, and the objective is to minimize the makespan, i.e., the maximum job completion time. Focusing on the case when m is fixed, we present for both preemptive and nonpreemptive variants of the problem fully polynomial approximation schemes whose running times depend only linearly on n. We also study an extension of the problem where processing job j on machine i incurs a cost of c(ij), and thus there are two optimization criteria: makespan and cost. We show that, for any tired m. there is a fully polynomial approximation scheme that, given values T and C, computes for any tired epsilon > 0 a schedule in O(n) time with makespan at most (1 + epsilon )T and cost at most (1 + epsilon )C, if there exists a schedule of makespan T and cost C.

关键词： scheduling parallel machines makespan fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Minimization of half-products

引用

MATHEMATICS OF OPERATIONS RESEARCH 1998年第3期23卷 649-660页

作者： Badics, T Boros, E Parametr Technol Corp Waltham MA 02154 USA Rutgers State Univ RUTCOR New Brunswick NJ 08904 USA

In this paper a special class of quadratic functions, the so called half-products are considered. It is shown that while the minimization over the set of binary n-vectors for half-products is NP-complete, an epsilon-a... 详细信息

关键词： completion time variance minimization quadratic binary minimization fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic programming in connection with an FPTAS for the knapsack problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2004年第1期8卷 5-11页

作者： Kellerer, H Pferschy, U Graz Univ Dept Stat & Operat Res A-8010 Graz Austria

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over l of the l-th entry of the first vector plus the sum of the first k-l+1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n(2)) time bound. The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0-1 knapsack problem by the same authors.

关键词： dynamic programming knapsack problem fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A NONLINEAR KNAPSACK-PROBLEM

引用

OPERATIONS RESEARCH LETTERS 1995年第3期17卷 103-110页

作者： HOCHBAUM, DS UNIV CALIF BERKELEY DEPT IEORBERKELEYCA 94720

The nonlinear Knapsack problem is to maximize a separable concave objective function, subject to a single ''packing'' constraint, in nonnegative variables. We consider this problem in integer and continuous variables, and also when the packing constraint is convex. Although the nonlinear Knapsack problem appears difficult in comparison with the linear Knapsack problem, we prove that its complexity is similar. We demonstrate for the nonlinear Knapsack problem in n integer variables and knapsack volume limit B, a fully polynomial approximation scheme with running time (O) over tilde((1/epsilon(2)) (n + 1/epsilon(2))) (omitting polylog terms);and for the continuous case an algorithm delivering an epsilon-accurate solution in O(n log(B/epsilon)) operations.

关键词： CONVEX OPTIMIZATION fully polynomial approximation scheme KNAPSACK PROBLEM QUADRATIC KNAPSACK PROBLEM ALLOCATION PROBLEM

来源：评论

学校读者我要写书评

暂无评论

A near-optimal solution to a two-dimensional cutting stock problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2000年第4期25卷 645-656页

作者： Kenyon, C Rémila, E Univ Paris Sud LRI F-91405 Orsay France Univ St Etienne IUT Roanne Grima F-42334 Roanne France Ecole Normale Super Lyon CNRS Umr 5668 F-69364 Lyon France

We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. The algorithm, based on a new linear-programming relaxation, finds a packing of n rectangles whose total height is within a factor of(1 + epsilon) of optimal (up to an additive term), and has running time polynomial both in n and in 1/epsilon.

关键词： cutting-stock strip-packing fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

SINGLE-MACHINE BATCH SCHEDULING WITH DEADLINES AND RESOURCE DEPENDENT PROCESSING TIMES

引用

OPERATIONS RESEARCH LETTERS 1995年第5期17卷 243-249页

作者： CHENG, TCE KOVALYOV, MY BELARUS ACAD SCI INST ENGN CYBERNET MINSK 220012 BELARUS

We consider the problem of scheduling n jobs on a single machine where each job has a deadline and a processing time that is a linear decreasing function of the amount of a common discrete resource allocated to the job. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of the batch is processed. The completion time of each job in a batch coincides with the completion time of the last job in the batch. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find simultaneously a resource allocation and a schedule which is feasible with respect to the deadlines so as to minimize the total weighted resource consumption. The problem is shown to be NP-hard even for the special case of common parameters. Two dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.

关键词： SINGLE MACHINE SCHEDULING BATCHING RESOURCE ALLOCATION DYNAMIC PROGRAMMING fully polynomial approximation scheme

来源：评论

学校读者我要写书评

暂无评论

WORST-CASE ANALYSIS OF GREEDY ALGORITHMS FOR THE SUBSET-SUM PROBLEM

引用

MATHEMATICAL PROGRAMMING 1984年第2期28卷 198-205页

作者： MARTELLO, S TOTH, P UNIV FLORENCE IST INFORMAT & SISTEMISTI-50121 FLORENCEITALY

Given a set ofn positive integers and another positive integerW, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding,W. We present a polynomial approximation scheme for this proble... 详细信息

关键词： fully polynomial approximation scheme Greedy Algorithms polynomial approximation scheme Subset Sum Worst-Case Performance Ratio

来源：评论

学校读者我要写书评

暂无评论

Faster min-max resource sharing in theory and practice

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2011年第1期3卷 1-35页

作者： Mueller, Dirk Radke, Klaus Vygen, Jens Univ Bonn Res Inst Discrete Math Lennestr 2 D-53113 Bonn Germany Rhein Westfal TH Aachen Dept Comp Sci D-52074 Aachen Germany

We consider the (block-angular) min-max resource sharing problem, which is defined as follows. Given finite sets R of resources and C of customers, a convex set B-c, called block, and a convex function g(c) : B-c -> R-+(R) for every c is an element of C, the task is to find b(c) is an element of B-c (c is an element of C) approximately attaining lambda* := inf{max(r is an element of R) Sigma(c is an element of C) (g(c)(b(c)))r | b(c) is an element of B-c (c is an element of C)}. As usual we assume that g(c) can be computed efficiently and we have a constant sigma >= 1 and oracle functions f(c) : R-+(R). B-c, called block solvers, which for c is an element of C and y is an element of R-+(R) return an element b(c) is an element of B-c with y(inverted perpendicular) g(c)(b(c)) <= sigma inf(b is an element of Bc) y(inverted perpendicular) g(c)(b). We describe a simple algorithm which solves this problem with an approximation guarantee sigma(1 + omega) for any omega > 0, and whose running time is O(theta (| C|+| R|) log | R|(log log | R|+omega(-2))) for any fixed sigma >= 1, where theta is the time for an oracle call. This generalizes and improves various previous results. We also prove other bounds and describe several speed-up techniques. In particular, we show how to parallelize the algorithm efficiently. In addition we review another algorithm, variants of which were studied before. We show that this algorithm is almost as fast in theory, but it was not competitive in our experiments. Our work was motivated mainly by global routing in chip design. Here the blocks are mixedinteger sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We present experimental results on instances

关键词： Min-max resource sharing Fractional packing fully polynomial approximation scheme Parallelization Global routing Chip design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：