An algorithm for minimizing setups in precedence constrained scheduling

DOI10.1016/0377-0427(85)90050-0zbMATH Open0584.90041OpenAlexW2050090155MaRDI QIDQ1069848FDOQ1069848

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

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

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

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

Cited In (7)

• Certain exact and approximate algorithms for solving precedence problems with constraints
• A Precedence Graph Algorithm for the Shop Scheduling Problem
• Title not available (Why is that?)
• 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)