Algorithmic Approaches to Setup Minimization

DOI10.1137/0214068MaRDI QIDQ3694689zbMATH OpenOpenAlexFDO

Authors U. Faigle, Gerhard Gierz, Rainer Schrader

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214068

zbMATH Keywords

greedy algorithmN-free ordered setsNP-complete problemspartially ordered setsschedulingseries-parallel connections

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A greedy reduction algorithm for setup optimization
• Constructing greedy linear extensions by interchanging chains
• Setup optimization problems with matroid structure
• A setup heuristic for interval orders
• Minimizing setups in ordered sets of fixed width

Cited in

(12)

• Jump number problem: The role of matroids
• A setup heuristic for interval orders
• An algorithm for minimizing setups in precedence constrained scheduling
• Interval orders without odd crowns are defect optimal
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• A greedy reduction algorithm for setup optimization
• Parallel \(N\)-free order recognition
• scientific article; zbMATH DE number 3860892 (Why is no real title available?)
• NP-completeness properties about linear extensions
• Minimizing completion time for a class of scheduling problems
• The jump number and the lattice of maximal antichains
• A 3/2-approximation algorithm for the jump number of interval orders

This page was built for publication: Algorithmic Approaches to Setup Minimization

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