Computing the bump number with techniques from two-processor scheduling

DOI10.1007/BF00337618MaRDI QIDQ1106865zbMATH OpenFDO

Authors Alejandro A. Schäffer, Barbara B. Simons

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

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

Recommendations

• Computing the bump number is easy
• Minimizing bumps in linear extensions of ordered sets
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• scientific article; zbMATH DE number 221764
• Minimizing bumps for posets of width two

Cites work

• scientific article; zbMATH DE number 3963191 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Computing the bump number is easy
• Deterministic Scheduling with Pipelined Processors
• Minimizing bumps in linear extensions of ordered sets
• On Some Variants of the Bandwidth Minimization Problem
• Optimal Sequencing of Two Equivalent Processors
• Optimal scheduling for two-processor systems

Cited in

(11)

• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• The setup polyhedron of series-parallel posets
• scientific article; zbMATH DE number 221764 (Why is no real title available?)
• 1-tough cocomparability graphs are hamiltonian
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• Hamiltonian cycle is polynomial on cocomparability graphs
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Minimizing the maximum bump cost in linear extensions of a poset

This page was built for publication: Computing the bump number with techniques from two-processor scheduling

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