On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems

DOI10.1016/j.tcs.2006.05.013zbMath1146.90032MaRDI QIDQ2503352

David P. Williamson, Joel M. Wein, R. N. Uma

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.013

zbMATH Keywords

scheduling; combinatorial lower bounds; LP-based lower bounds

Mathematics Subject Classification ID

90C05: Linear programming

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling-LPs bear probabilities. Randomized approximations for min-sum criteria
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• Scheduling with release dates on a single machine to minimize total weighted completion time
• A time indexed formulation of non-preemptive single machine scheduling problems
• Minimizing average completion time in the presence of release dates
• Improved bounds on relaxations of a parallel machine scheduling problem
• A polyhedral approach to single-machine scheduling problems.
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• Structure of a simple scheduling polyhedron
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• Scheduling of a single machine to minimize total weighted completion time subject to release dates
• Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time
• On n/1/?? dynamic deterministic problems
• New Bounds for the Identical Parallel Processor Weighted Flow Time Problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• A supermodular relaxation for scheduling with release dates