Approximability of average completion time scheduling on unrelated machines (Q507314): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Normalize DOI.
 
(6 intermediate revisions by 5 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s10107-016-1004-8 / rank
Normal rank
 
Property / author
 
Property / author: R. A. Sitters / rank
Normal rank
 
Property / author
 
Property / author: R. A. Sitters / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s10107-016-1004-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2340234317 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convex quadratic and semidefinite programming relaxations in scheduling / rank
 
Normal rank
Property / cites work
 
Property / cites work: Designing PTASs for MIN-SUM scheduling problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Scheduling independent tasks to reduce mean finishing time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4535067 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5501838 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Single Machine Scheduling with Release Dates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Open Shop Scheduling to Minimize Finish Time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4875178 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Non-Approximability Results for Scheduling Problems with Minsum Criteria / rank
 
Normal rank
Property / cites work
 
Property / cites work: Technical Note—Minimizing Average Flow Time with Parallel Machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum bounded 3-dimensional matching is MAX SNP-complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective / rank
 
Normal rank
Property / cites work
 
Property / cites work: Scheduling Unrelated Machines by Randomized Rounding / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial time approximation algorithms for machine scheduling: Ten open problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximability of Average Completion Time Scheduling on Unrelated Machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of preemptive minsum scheduling on unrelated parallel machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: A PTAS for minimizing the weighted sum of job completion times on parallel machines / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S10107-016-1004-8 / rank
 
Normal rank

Latest revision as of 19:46, 9 December 2024

scientific article
Language Label Description Also known as
English
Approximability of average completion time scheduling on unrelated machines
scientific article

    Statements

    Approximability of average completion time scheduling on unrelated machines (English)
    0 references
    3 February 2017
    0 references
    This paper deals with the unweighted and weighted versions of the problem to minimize total completion time on unrelated parallel machines if preemption of operations is allowed. In Section 2, the author proves that already the unweighted version of this problem is \(\mathcal{APX}\)-hard. The second contribution of this paper are two approximation algorithms for the weighted version of this problem in Section 3. The first approximation algorithm is based on the 2-approximation algorithm given by \textit{M. Skutella} [J. ACM 48, No. 2, 206--242 (2001; Zbl 1323.90024)] and has an approximation ratio less than 1.81. The second algorithm is obtained by applying the first algorithm and another algorithm given by \textit{M. Queyranne} and \textit{M. Sviridenko} [J. Sched. 5, No. 4, 287--305 (2002; Zbl 1009.90046)] and taking then the better of the two solutions determined. This latter algorithm has an approximation ratio less than 1.698. The results of this paper fill a gap in the complexity classification results for this objective function, and it also improves the previously best known approximation ratio for this problem.
    0 references
    0 references
    scheduling
    0 references
    total completion time
    0 references
    preemption
    0 references
    unrelated machines
    0 references
    \(\mathcal{APX}\)-hardness
    0 references
    approximation algorithm
    0 references
    0 references

    Identifiers