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

DOI10.1016/j.orl.2003.12.003zbMath1054.90038OpenAlexW2037296416MaRDI 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 complexityMakespanPrecedence delaysSequencing

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

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