Minimizing the sum of weighted completion times in a concurrent open shop

DOI10.1016/J.ORL.2010.04.011zbMATH Open1202.90139OpenAlexW1982055457MaRDI QIDQ613333FDOQ613333

Andreas S. Schulz, Ola Svensson, Monaldo Mastrolilli, Nelson A. Uhan, Maurice Queyranne

Publication date: 20 December 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.04.011

zbMATH Keywords

approximation algorithmschedulingintegrality gaphardness of approximation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Title not available (Why is that?)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• On the power of unique 2-prover 1-round games
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Structure of a simple scheduling polyhedron
• Coordinated scheduling of customer orders for quick response
• Order scheduling in an environment with dedicated resources in parallel
• Scheduling orders for multiple product types to minimize total weighted completion time
• Order Scheduling Models: Hardness and Algorithms
• A note on the complexity of the concurrent open shop problem
• Open shops with jobs overlap

Cited In (18)

• Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
• Scheduling fully parallel jobs
• Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
• Minimizing maximum delivery completion time for order scheduling with rejection
• Minimizing the weighted sum of completion times under processing time uncertainty
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partially concurrent open shop scheduling with integral preemptions
• Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms
• A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times
• Green scheduling, flows and matchings
• Scheduling Fully Parallel Jobs with Integer Parallel Units
• On complexity of minimizing weighted number of late jobs in unit time open shops
• Iterated greedy algorithms for a complex parallel machine scheduling problem
• Select and permute: an improved online framework for scheduling to minimize weighted completion time
• Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
• The representation of partially-concurrent open shop problems
• On scheduling coflows

This page was built for publication: Minimizing the sum of weighted completion times in a concurrent open shop

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613333)