An algorithm for minimizing setups in precedence constrained scheduling

DOI10.1016/0377-0427(85)90050-0MaRDI QIDQ1069848zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Minimizing completion time for a class of scheduling problems
• Non-approximability of precedence-constrained sequencing to minimize setups.
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• scientific article; zbMATH DE number 4085404
• Task scheduling with precedence constraints to minimize the total completion time

Cites work

• scientific article; zbMATH DE number 3757695 (Why is no real title available?)
• scientific article; zbMATH DE number 3499169 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A labeling algorithm to recognize a line digraph and output its root graph
• Algorithmic Approaches to Setup Minimization
• Decomposition of Directed Graphs
• Greedy linear extensions to minimize jumps
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• On Comparability and Permutation Graphs
• Optimal Linear Extensions by Interchanging Chains
• Scheduling subject to resource constraints: Classification and complexity
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• The Jump Number of Dags and Posets: An Introduction
• The Recognition of Series Parallel Digraphs

Cited in

(7)

• Certain exact and approximate algorithms for solving precedence problems with constraints
• A Precedence Graph Algorithm for the Shop Scheduling Problem
• scientific article; zbMATH DE number 5260973 (Why is no real title available?)
• Non-approximability of precedence-constrained sequencing to minimize setups.
• Minimizing completion time for a class of scheduling problems
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• An iterative algorithm for scheduling unit-times tasks with precedence constraints to minimise the maximum lateness

This page was built for publication: An algorithm for minimizing setups in precedence constrained scheduling

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