We study the scheduling problem on parallel identical machines in order to maximize the total early work, i.e. the parts of non-preemptive jobs executed before a common due date, and investigate mainly the model with ...
详细信息
We study the scheduling problem on parallel identical machines in order to maximize the total early work, i.e. the parts of non-preemptive jobs executed before a common due date, and investigate mainly the model with a fixed number of machines, for which a dynamic programming approach and a fully polynomial time approximation scheme (FPTAS) are proposed. The proposal of these methods allowed us to establish the complexity and approximability status of this problem more exactly. Moreover, since our FPTAS can be also applied for the two-machine case, we improve considerably the result known in the literature for this model, in which a polynomialtimeapproximationscheme (PTAS) was given. The new FPTAS has not only the best computational complexity, but also the much better approximation ratio than the PTAS. Finally, the theoretical studies are completed with computational experiments, performed for dynamic programming, PTAS and FPTAS, showing the high efficiencies of FPTAS both in terms of time consumption and solution quality. (C) 2019 Elsevier B.V. All rights reserved.
The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals {[a(i), 1, a(i,2) ](i=1)(n) and a target integer T, the ISSP is to find a set of integers, at m...
详细信息
The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals {[a(i), 1, a(i,2) ](i=1)(n) and a target integer T, the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target T but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0-1 knapsack problem. We also identify several subclasses of the ISSP which are polynomialtime solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme for solving the general ISSP problem. The time and space complexities of the proposed scheme are O (n max {1/epsilon, log n} and O (n+1/epsilon), respectively, where epsilon is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with n = 100,000 and epsilon = 0.1% within 1 s.
As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensab...
详细信息
ISBN:
(纸本)9781605584973
As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + epsilon running in O(m(2)n(2)b/epsilon(3) + n(3)b(2)/epsilon) time for any 0 < epsilon < 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6x speedup. This clearly demonstrates the practical value of the new algorithm.
The Adaptive Variable Rate (AVR) task model defines a task where job WCET and period are a function of engine speed. Motivated by a lack of tractable AVR task demand methods, this work uses predefined job sequences fo...
详细信息
ISBN:
(纸本)9798400717246
The Adaptive Variable Rate (AVR) task model defines a task where job WCET and period are a function of engine speed. Motivated by a lack of tractable AVR task demand methods, this work uses predefined job sequences for the Bounded Precedence Constraint Knapsack Problem inherent in AVR task demand calculation instead of enumerating all considered speeds as in existing work. A new, exact approach is proposed and approximated, enabling the derivation of a fully polynomial time approximation scheme that outperforms the state-of-the-art in runtime (7,800x improvement) and RAM use (99% reduction) with less than 8% demand overestimate.
This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex s and p destination vertices t(1), t(2),...,t(p)...
详细信息
This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex s and p destination vertices t(1), t(2),...,t(p) 14 together with p corresponding nonnegative delay constraints d(1), d(2),...,d(p), many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique s-t(i) path is no more than d(i) for 1less than or equal toiless than or equal top. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present Computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.
In this paper, we study the K-prize-collecting coverage problem by using aligned disks. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line I., where each user corres...
详细信息
In this paper, we study the K-prize-collecting coverage problem by using aligned disks. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line I., where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set D of disks whose centers are all in S such that the total profit of the users covered by D' is at least K, and the objective value, which consists of the total cost of the disks in D' plus the total penalty of the uncovered users in U\U (D'), is minimized, where the cost of disk D is r(D)(alpha), alpha >= 1 is an attenuation factor, r(D) is the radius of disk D, and K is a given profit bound. We first prove that this problem is NP-hard even when all users are located on line L, alpha=1 and the penalty of each user is 0. We present a pseudo-polynomial-time algorithm. Finally, we present a fully polynomial time approximation scheme for the problem.
In this paper, we study the K $K$ -prize-collecting coverage problem by using aligned disks. Suppose U $U$ is a set of users, L $L$ is a horizontal line on the plane, and S $S$ is a set of points on the line L $L$ , w...
详细信息
In this paper, we study the K $K$ -prize-collecting coverage problem by using aligned disks. Suppose U $U$ is a set of users, L $L$ is a horizontal line on the plane, and S $S$ is a set of points on the line L $L$ , where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set D ′ $\mathcal {D}^{\prime }$ of disks whose centers are all in S $S$ such that the total profit of the users covered by D ′ $\mathcal {D}^{\prime }$ is at least K $K$ , and the objective value, which consists of the total cost of the disks in D ′ $\mathcal {D}^{\prime }$ plus the total penalty of the uncovered users in U ∖ U ( D ′ ) $U\setminus U(\mathcal {D}^{\prime })$ , is minimized, where the cost of disk D $D$ is r ( D ) α $r(D)^{\alpha }$ , α ≥ 1 $\alpha \ge 1$ is an attenuation factor, r ( D ) $r(D)$ is the radius of disk D $D$ , and K $K$ is a given profit bound. We first prove that this problem is N P $NP$ -hard even when all users are located on line L $L$ , α = 1 $\alpha =1$ and the penalty of each user is 0. We present a pseudo-polynomial-time algorithm. Finally, we present a fully polynomial time approximation scheme for the problem.
We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with const...
详细信息
We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with constraints of a general form. This allows us to give different interpretations related to scheduling and input-output analysis. The model may arise either separately or in the structure of more general production models. In both cases it is reasonable to find an optimal or near-optimal distribution of resources between these two facilities. This helps either to develop a new production plan or to improve an existing one. The problem in question is NP-hard. We show that our approach leads to fully polynomial time approximation schemes (FPTASs).
We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be ...
详细信息
We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomialtime. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero. (C) 2007 Elsevier B.V. All rights reserved.
We study a 0-1 knapsack problem, in which the objective value is forbidden to take some values. We call gaps related forbidden intervals. The problem is NP-hard and pseudo-polynomially solvable independently on the me...
详细信息
We study a 0-1 knapsack problem, in which the objective value is forbidden to take some values. We call gaps related forbidden intervals. The problem is NP-hard and pseudo-polynomially solvable independently on the measure of gaps. If the gaps are large, then the problem is polynomially non-approximable. A non-trivial special case with respect to the approximate solution appears when the gaps are small and polynomially close to zero. For this case, two fully polynomial time approximation schemes are proposed. The results can be extended for the constrained longest path problem and other combinatorial problems.
暂无评论