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 mac...
详细信息
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.
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. ...
详细信息
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.
In this paper, we consider the unbounded parallel batch machine scheduling with release dates and rejection. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on t...
详细信息
In this paper, we consider the unbounded parallel batch machine scheduling with release dates and rejection. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on the parallel batch machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. 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 this problem is binary NP-hard and provide a pseudo-polynomial-time algorithm. When the jobs have the same rejection penalty, the problem can be solved in polynomialtime. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. (C) 2008 Published by Elsevier B.V.
We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fullypolynomial-timeapproximation algorithm under mild conditions on the cost functions. ...
详细信息
We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fullypolynomial-timeapproximation 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.
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will u...
详细信息
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP = P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5. (c) 2005 Elsevier B.V. All rights reserved.
作者：
Ye, YYUniv 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 run...
详细信息
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.
Two heuristic procedures for a one-warehouse multi-retailer system are developed. Based on the accuracy desired, the first heuristic evaluates a specified number of points. The relative error is within a bound that ap...
详细信息
Two heuristic procedures for a one-warehouse multi-retailer system are developed. Based on the accuracy desired, the first heuristic evaluates a specified number of points. The relative error is within a bound that approaches 1/(root 2 In 2) - 1 approximate to 2.014%. The complexity of the heuristic is O(n) for a fixed number of evaluations. Although our bound only approaches the one of Roundy (1985), when only a small number of points are evaluated, our method is faster. We show that the bound for our procedure and two bounds proposed by Roundy (1985) are tight. The second heuristic pertains to a class of policies called stationary interval policies. For this class of policies, we develop a fully polynomial-time approximation scheme where the relative error is within epsilon > 0, and the computational effort increases as a linear function of 1/root epsilon. Computational experiments show that these heuristics perform well in practice.
暂无评论