Approximability of average completion time scheduling on unrelated machines
type: Item
instance of: scholarly article
title: Approximability of average completion time scheduling on unrelated machines
zbMATH Open document ID: 1357.90059
published in: Mathematical Programming. Series A. Series B
publication date: 2017-02-03T00:00:00Z
review text: 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.
reviewed by: Frank Werner
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6680628
zbMATH Keywords: scheduling
zbMATH Keywords: total completion time
zbMATH Keywords: preemption
zbMATH Keywords: unrelated machines
zbMATH Keywords: \(\mathcal{APX}\)-hardness
zbMATH Keywords: approximation algorithm
author: René A. Sitters
MaRDI profile type: Publication
full work available at URL: s10107-016-1004-8
OpenAlex ID: W2340234317
cites work: Convex quadratic and semidefinite programming relaxations in scheduling
cites work: Designing PTASs for MIN-SUM scheduling problems
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Q4535067
cites work: Q5501838
cites work: Single machine scheduling with release dates
cites work: Open Shop Scheduling to Minimize Finish Time
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Q4875178
cites work: Non-approximability results for scheduling problems with minsum criteria
cites work: Technical Note—Minimizing Average Flow Time with Parallel Machines
cites work: Maximum bounded 3-dimensional matching is MAX SNP-complete
cites work: On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
cites work: Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
cites work: A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
cites work: Scheduling Unrelated Machines by Randomized Rounding
cites work: Polynomial time approximation algorithms for machine scheduling: Ten open problems
cites work: Approximability of Average Completion Time Scheduling on Unrelated Machines
cites work: Complexity of preemptive minsum scheduling on unrelated parallel machines
cites work: A PTAS for minimizing the weighted sum of job completion times on parallel machines
DOI: 10.1007/S10107-016-1004-8
description: scientific article; zbMATH DE number 6680628