Approximation algorithms for shop scheduling problems with minsum objective
From MaRDI portal
Publication:1607979
DOI10.1002/JOS.96zbMATH Open1009.90046OpenAlexW2170050590MaRDI QIDQ1607979FDOQ1607979
Maxim Sviridenko, Maurice Queyranne
Publication date: 8 August 2002
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jos.96
Recommendations
- Publication:4952712
- scientific article; zbMATH DE number 871909
- A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
- scientific article; zbMATH DE number 1757967
- Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)
Cites Work
- A Computational Study of the Job-Shop Scheduling Problem
- Geometric algorithms and combinatorial optimization
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Structure of a simple scheduling polyhedron
- Title not available (Why is that?)
- Scheduling the Open Shop to Minimize Mean Flow Time
- Single machine scheduling with release dates
- Flowshop and Jobshop Schedules: Complexity and Approximation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
- Improved Approximation Algorithms for Shop Scheduling Problems
- Title not available (Why is that?)
- Scheduling open shops with parallel machines
- Approximation schemes for scheduling on parallel machines
- Approximation algorithms for the multiprocessor open shop scheduling problem
- Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
- Title not available (Why is that?)
- The power of \(\alpha\)-points in preemptive single machine scheduling.
- Title not available (Why is that?)
- Makespan minimization in preemptive two machine job shops
- Approximation and randomization in scheduling
- Title not available (Why is that?)
- Tighter bounds on preemptive job shop scheduling with two machines
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (18)
- Approximation Algorithms for Scheduling with Resource and Precedence Constraints
- Scheduling Problems over Network of Machines
- Scheduling on unrelated machines under tree-like precedence constraints
- Title not available (Why is that?)
- The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
- Title not available (Why is that?)
- Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
- Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop
- Approximation algorithms for shop scheduling problems with minsum objective: A correction
- Minimizing L max for large-scale, job-shop scheduling problems
- Improved Approximation Algorithms for Routing Shop Scheduling
- Optimal restricted due date assignment in scheduling
- A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
- A time-indexed LP-based approach for min-sum job-shop problems
- Properties of optimal schedules in preemptive shop scheduling
- Scheduling problems over a network of machines
- On a local protocol for concurrent file transfers
- Combinatorial algorithms for data migration to minimize average completion time
This page was built for publication: Approximation algorithms for shop scheduling problems with minsum objective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1607979)
