A supermodular relaxation for scheduling with release dates

DOI10.1007/3-540-61310-2_22MaRDI QIDQ4645930zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans

Publication date 11 January 2019

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61310-2_22

zbMATH Keywords

completion timegreedy algorithmrelease datescheduling problemtransportation problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds
• Convex quadratic and semidefinite programming relaxations in scheduling
• Single machine scheduling with release dates
• A polyhedral approach to single-machine scheduling problems.
• Scheduling with rejection

Cites work

• A Sequencing Problem with Release Dates and Clustered Jobs
• An analysis of approximations for maximizing submodular set functions—I
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds
• Structure of a simple scheduling polyhedron
• Submodular functions and optimization

Cited in

(14)

• A 1. 47-approximation for a preemptive single-machine scheduling problem
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
• An improved greedy algorithm for stochastic online scheduling on unrelated machines
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Approximately Supermodular Scheduling Subject to Matroid Constraints
• Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds
• Randomized mechanism design for decentralized network scheduling
• Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• The power of proportional fairness for nonclairvoyant polytope scheduling
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms

This page was built for publication: A supermodular relaxation for scheduling with release dates

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