Computing the bump number with techniques from two-processor scheduling

DOI10.1007/BF00337618zbMath0652.06003MaRDI QIDQ1106865

Barbara B. Simons, Alejandro A. Schäffer

Publication date: 1988

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

linear extensionlinear-time algorithmbump numberscheduling unit-time tasks with a precedence partial order on two identical processorstwo-processor scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Computing the bump number is easy ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ The setup polyhedron of series-parallel posets ⋮ Minimizing the maximum bump cost in linear extensions of a poset ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Hamiltonian cycle is polynomial on cocomparability graphs ⋮ The connection between the bump number problem and flow-shop scheduling with precedence constraints

Cites Work

• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• Optimal scheduling for two-processor systems
• On Some Variants of the Bandwidth Minimization Problem
• Deterministic Scheduling with Pipelined Processors
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Optimal Sequencing of Two Equivalent Processors