Name
Abstract | ||
|---|---|---|
The problem under consideration is to schedule jobs on a machine in order to minimize the sum of the penalties of delayed jobs. A “range-and-bound” method is proposed for finding a tight bound P̃ such that P̃ ≤ P ∗≤2 P̃ , P ∗ being the minimal sum desired. The considered scheduling problem, for n jobs and accuracy ε > 0, is solved by a fully polynomial ε-approximation algorithm in O(n 2 log n + n 2 ε ) time and O( n 2 ε ) space. |
Year | DOI | Venue |
|---|---|---|
1981 | 10.1016/0166-218X(81)90008-1 | DISCRETE APPLIED MATHEMATICS |
Field | DocType | Volume |
Approximation algorithm,Binary logarithm,Discrete mathematics,Combinatorics,Job shop scheduling,Polynomial,Mathematics | Journal | 3 |
Issue | ISSN | Citations |
4 | 0166-218X | 41 |
PageRank | References | Authors |
4.48 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| G.V. Gens | 1 | 41 | 4.48 |
| E.V. Levner | 2 | 41 | 4.48 |