Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay.

DOI10.1016/j.orl.2003.12.003zbMath1054.90038MaRDI QIDQ703281

Alix Munier Kordon

Publication date: 11 January 2005

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

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

zbMATH Keywords

Computational complexity; Makespan; Precedence delays; Sequencing

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

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

Related Items

Maximum cost scheduling of jobs with mixed variable processing times and \(k\)-partite precedence constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Black-white pebbles and graph separation
• A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays
• One-machine generalized precedence constrained scheduling problems
• Scheduling chains on a single machine with non-negative time lags
• Optimal scheduling for two-processor systems
• On Some Variants of the Bandwidth Minimization Problem
• Scheduling expressions on a pipelined processor with a maximal delay of one cycle
• Scheduling Interval-Ordered Tasks
• Deterministic Scheduling with Pipelined Processors
• The complexity of short schedules for uet bipartite graphs
• A modified shifting bottleneck procedure for job-shop scheduling
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies