Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler

DOI10.1137/S0895480197330254MaRDI QIDQ4490785zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, David P. Williamson

Publication date 20 July 2000

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480197330254

zbMATH Keywords

linear programmingschedulingseries-parallel

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Scheduling Graphs on Two Processors
• scientific article; zbMATH DE number 613300
• A Graphical Foundation for Schedules
• Two-phase heuristics for scheduling of multiple projects
• TWO PRECEDENCE-RELATED TASK-SCHEDULING ALGORITHMS
• Two coNP-complete schedule analysis problems
• A two-pass scheduling algorithm for parallel programs
• On Approximation Algorithms for Two-Stage Scheduling Problems
• scientific article; zbMATH DE number 4137518

Cited in

(12)

• Scheduling meets \(n\)-fold integer programming
• On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
• On the approximability of average completion time scheduling under precedence constraints.
• Dual techniques for scheduling on a machine with varying speed
• SPT optimality (mostly) via linear programming
• The constrained minimum weighted sum of job completion times problem
• Total completion time scheduling under scenarios
• Optimal algorithms for scheduling under time-of-use tariffs
• Asymptotically optimal schedules for single-server flow shop problems with setup costs and times
• Partially ordered knapsack and applications to scheduling
• Single machine precedence constrained scheduling is a Vertex cover problem
• Gantt charts: A centenary appreciation.

This page was built for publication: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler

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