A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective (Q1755846): Difference between revisions

Latest revision as of 19:49, 17 July 2024

scientific article

Language	Label	Description	Also known as
English	A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective	scientific article

Statements

instance of

scholarly article

0 references

title

A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective (English)

0 references

author

Martin Skutella

0 references

published in

Operations Research Letters

0 references

publication date

11 January 2019

0 references

full work available at URL

https://arxiv.org/abs/1603.04690

0 references

zbMATH Keywords

approximation algorithm

0 references

machine scheduling

0 references

precedence constraints

0 references

total weighted completion time

0 references

LP relaxation

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Single machine precedence constrained scheduling is a Vertex cover problem

0 references

On the Approximability of Single-Machine Scheduling with Precedence Constraints

0 references

Optimal Long Code Test with One Free Bit

0 references

Approximation Techniques for Average Completion Time Scheduling

0 references

Single-Machine Scheduling with Precedence Constraints

0 references

Q4198056

0 references

A supermodular relaxation for scheduling with release dates

0 references

Q5501838

0 references

Single Machine Scheduling with Release Dates

0 references

Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

0 references

Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

0 references

Q4875178

0 references

Minimizing average completion time in the presence of release dates

0 references

Structure of a simple scheduling polyhedron

0 references

Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds

0 references

Q2723565

0 references

List Scheduling in Order of α-Points on a Single Machine

0 references

Identifiers

zbMATH Open document ID

1408.90140

0 references

DOI

10.1016/j.orl.2016.07.016

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1755846

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2963832601
@@ Property / OpenAlex ID: W2963832601 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04690
@@ Property / arXiv ID: 1603.04690 / rank @@
+Normal rank
@@ Property / cites work @@
+Single machine precedence constrained scheduling is a Vertex cover problem
+Normal rank
@@ Property / cites work @@
+On the Approximability of Single-Machine Scheduling with Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Optimal Long Code Test with One Free Bit
@@ Property / cites work: Optimal Long Code Test with One Free Bit / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Techniques for Average Completion Time Scheduling
+Normal rank
@@ Property / cites work @@
+Single-Machine Scheduling with Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+A supermodular relaxation for scheduling with release dates
+Normal rank
@@ Property / cites work @@
+Q5501838
@@ Property / cites work: Q5501838 / rank @@
+Normal rank
@@ Property / cites work @@
+Single Machine Scheduling with Release Dates
@@ Property / cites work: Single Machine Scheduling with Release Dates / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
+Normal rank
@@ Property / cites work @@
+Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
+Normal rank
@@ Property / cites work @@
+Q4875178
@@ Property / cites work: Q4875178 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing average completion time in the presence of release dates
+Normal rank
@@ Property / cites work @@
+Structure of a simple scheduling polyhedron
@@ Property / cites work: Structure of a simple scheduling polyhedron / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
+Normal rank
@@ Property / cites work @@
+Q2723565
@@ Property / cites work: Q2723565 / rank @@
+Normal rank
@@ Property / cites work @@
+List Scheduling in Order of α-Points on a Single Machine
+Normal rank