An algorithm for minimizing setups in precedence constrained scheduling

DOI10.1016/0377-0427(85)90050-0zbMath0584.90041OpenAlexW2050090155MaRDI QIDQ1069848

George Steiner

Publication date: 1985

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-0427(85)90050-0

zbMATH Keywords

precedence constraintsdecomposition approachsingle processorminimizing setups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling subject to resource constraints: Classification and complexity
• Greedy linear extensions to minimize jumps
• A labeling algorithm to recognize a line digraph and output its root graph
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Optimal Linear Extensions by Interchanging Chains
• On Comparability and Permutation Graphs
• Algorithmic Approaches to Setup Minimization
• The Jump Number of Dags and Posets: An Introduction
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• The Recognition of Series Parallel Digraphs
• Decomposition of Directed Graphs
• Minimizing Setups for Cycle-Free Ordered Sets