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)

Full work available at URL https://doi.org/10.1007/BF00337618

zbMATH Keywords

bump numberlinear extensionlinear-time algorithmscheduling unit-time tasks with a precedence partial order on two identical processorstwo-processor scheduling

Mathematics Subject Classification ID

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

Review text

Let (X,\(\prec)\) be a partially ordered set. A linear extension \(x_ 1,x_ 2,..\). has a bump whenever \(x_ i\prec x_{i+1}\), and it has a jump whenever \(x_ i\) and \(x_{i+1}\) are incomparable. The problem of finding a linear extension that minimizes the number of jumps has been studied extensively; \textit{W. R. Pulleyblank} [On minimizing setups in precedence constrained scheduling (to appear)] shows that it is NP- complete in the general case. \textit{P. C. Fishburn} and \textit{W. V. Gehrlein} [Order 3, 3-14 (1986; Zbl 0595.06004)] raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear- time algorithm for the two-processor scheduling problem solves the bump number problem. The authors of the paper reviewed above (see Zbl 0652.06002) have independently discovered a different polynomial-time algorithm to solve the bump number problem.

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

• 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
• scientific article; zbMATH DE number 3963191 (Why is no real title available?)
• Minimizing bumps in linear extensions of ordered sets
• On Some Variants of the Bandwidth Minimization Problem
• Optimal scheduling for two-processor systems
• Optimal Sequencing of Two Equivalent Processors

Cited in

(11)

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

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)