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

decomposition approachminimizing setupsprecedence constraintssingle processor

Mathematics Subject Classification ID

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

Review text

Consider a set of tasks to be scheduled on a single processor subject to precedence constraints. A setup occurs when a task is performed immediately after another task which is not its predecessor. The general problem is to find a schedule minimizing the number of setups. We present a decomposition approach for this problem. This leads to new complexity results and the identification of new classes of precedence constraints for which the problem is efficiently solvable.

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

• 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
• 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?)
• 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)

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

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)