Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations (Q5117378): Difference between revisions

Revision as of 08:19, 23 July 2024

scientific article; zbMATH DE number 7239250

Language	Label	Description	Also known as
English	Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations	scientific article; zbMATH DE number 7239250

Statements

instance of

scholarly article

0 references

title

Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations (English)

0 references

author

Shi Li

0 references

published in

SIAM Journal on Computing

0 references

publication date

25 August 2020

0 references

full work available at URL

https://arxiv.org/abs/1707.08039

0 references

zbMATH Keywords

scheduling

0 references

weighted completion time

0 references

time indexed

0 references

approximation algorithms

0 references

MaRDI profile type

Publication

0 references

cites work

Optimal Long Code Test with One Free Bit

0 references

Minimizing Flow-Time on Unrelated Machines

0 references

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

0 references

Towards Tight Lower Bounds for Scheduling Problems

0 references

Q4818873

0 references

On (1,<i>∊</i>)-Restricted Assignment Makespan Minimization

0 references

Q4535067

0 references

Approximation schemes for preemptive weighted flow time

0 references

Approximation Techniques for Average Completion Time Scheduling

0 references

Q5501837

0 references

Q3579372

0 references

Q5501838

0 references

Bounds on Multiprocessing Timing Anomalies

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

Efficient scheduling of tasks without full use of processor resources

0 references

On the Configuration-LP of the Restricted Assignment Problem

0 references

Complexity of Scheduling under Precedence Constraints

0 references

Approximation algorithms for scheduling unrelated parallel machines

0 references

Q4526975

0 references

A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

0 references

Q3840372

0 references

Minimizing average completion time in the presence of release dates

0 references

Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems

0 references

Approximation algorithms for shop scheduling problems with minsum objective

0 references

Polynomial time approximation algorithms for machine scheduling: Ten open problems

0 references

Q4252432

0 references

Minimizing Average Flow Time on Unrelated Machines

0 references

Convex quadratic and semidefinite programming relaxations in scheduling

0 references

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

0 references

A PTAS for minimizing the weighted sum of job completion times on parallel machines

0 references

Conditional hardness of precedence constrained scheduling on identical machines

0 references

Santa Claus Schedules Jobs on Unrelated Machines

0 references

Identifiers

zbMATH Open document ID

1452.68277

0 references

DOI

10.1137/17M1156332

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5117378

@@ 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 @@
+Minimizing Flow-Time on Unrelated Machines
@@ Property / cites work: Minimizing Flow-Time on Unrelated Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
+Normal rank
@@ Property / cites work @@
+Towards Tight Lower Bounds for Scheduling Problems
+Normal rank
@@ Property / cites work @@
+Q4818873
@@ Property / cites work: Q4818873 / rank @@
+Normal rank
@@ Property / cites work @@
+On (1,<i>∊</i>)-Restricted Assignment Makespan Minimization
+Normal rank
@@ Property / cites work @@
+Q4535067
@@ Property / cites work: Q4535067 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation schemes for preemptive weighted flow time
+Normal rank
@@ Property / cites work @@
+Approximation Techniques for Average Completion Time Scheduling
+Normal rank
@@ Property / cites work @@
+Q5501837
@@ Property / cites work: Q5501837 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3579372
@@ Property / cites work: Q3579372 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5501838
@@ Property / cites work: Q5501838 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds on Multiprocessing Timing Anomalies
@@ Property / cites work: Bounds on Multiprocessing Timing Anomalies / 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 @@
+Efficient scheduling of tasks without full use of processor resources
+Normal rank
@@ Property / cites work @@
+On the Configuration-LP of the Restricted Assignment Problem
+Normal rank
@@ Property / cites work @@
+Complexity of Scheduling under Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for scheduling unrelated parallel machines
+Normal rank
@@ Property / cites work @@
+Q4526975
@@ Property / cites work: Q4526975 / rank @@
+Normal rank
@@ Property / cites work @@
+A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
+Normal rank
@@ Property / cites work @@
+Q3840372
@@ Property / cites work: Q3840372 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing average completion time in the presence of release dates
+Normal rank
@@ Property / cites work @@
+Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for shop scheduling problems with minsum objective
+Normal rank
@@ Property / cites work @@
+Scheduling Unrelated Machines by Randomized Rounding
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation algorithms for machine scheduling: Ten open problems
+Normal rank
@@ Property / cites work @@
+Q4252432
@@ Property / cites work: Q4252432 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing Average Flow Time on Unrelated Machines
+Normal rank
@@ Property / cites work @@
+Convex quadratic and semidefinite programming relaxations in scheduling
+Normal rank
@@ Property / cites work @@
+A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
+Normal rank
@@ Property / cites work @@
+A PTAS for minimizing the weighted sum of job completion times on parallel machines
+Normal rank
@@ Property / cites work @@
+Conditional hardness of precedence constrained scheduling on identical machines
+Normal rank
@@ Property / cites work @@
+Santa Claus Schedules Jobs on Unrelated Machines
@@ Property / cites work: Santa Claus Schedules Jobs on Unrelated Machines / rank @@
+Normal rank