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

DOI10.1016/J.ORL.2010.04.011MaRDI QIDQ613333zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
• Concurrent open shop scheduling to minimize the weighted number of tardy jobs
• Approximation algorithms for shop scheduling problems with minsum objective
• Publication:4952712
• A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective

Cites work

• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• A note on the complexity of the concurrent open shop problem
• Coordinated scheduling of customer orders for quick response
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• On LP-based approximability for strict CSPs
• On the power of unique 2-prover 1-round games
• Open shops with jobs overlap
• Order Scheduling Models: Hardness and Algorithms
• Order scheduling in an environment with dedicated resources in parallel
• Scheduling orders for multiple product types to minimize total weighted completion time
• 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
• Structure of a simple scheduling polyhedron
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(22)

• scientific article; zbMATH DE number 5665941 (Why is no real title available?)
• Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
• Minimizing maximum delivery completion time for order scheduling with rejection
• Integer Programming and Combinatorial Optimization
• Green scheduling, flows and matchings
• Partially concurrent open shop scheduling with integral preemptions
• scientific article; zbMATH DE number 1757967 (Why is no real title available?)
• Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
• The constrained minimum weighted sum of job completion times problem
• On complexity of minimizing weighted number of late jobs in unit time open shops
• A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
• Matroid coflow scheduling
• Iterated greedy algorithms for a complex parallel machine scheduling problem
• Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms
• Minimizing the weighted sum of completion times under processing time uncertainty
• Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
• A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times
• The representation of partially-concurrent open shop problems
• Scheduling fully parallel jobs with integer parallel units
• On scheduling coflows
• Scheduling fully parallel jobs
• Concurrent open shop scheduling to minimize the weighted number of tardy jobs

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)