A note on the precedence-constrained class sequencing problem

DOI10.1016/J.DAM.2006.03.038MaRDI QIDQ868379zbMATH OpenOpenAlexWikidataFDO

Authors José R. Correa, Samuel Fiorini, N. E. Stier-Moses

Publication date 2 March 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.03.038

zbMATH Keywords

approximation algorithmshardness of approximationprecedence-constrained scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Non-approximability of precedence-constrained sequencing to minimize setups.
• Hardness of precedence constrained scheduling on identical machines
• Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
• Conditional hardness of precedence constrained scheduling on identical machines
• scientific article; zbMATH DE number 1187165

Cites work

• Non-approximability of precedence-constrained sequencing to minimize setups.
• On approximation properties of the Independent set problem for degree 3 graphs
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the complexity of loop fusion
• Routing Printed Circuit Cards Through an Assembly Cell

Cited in

(2)

• Non-approximability of precedence-constrained sequencing to minimize setups.
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem

This page was built for publication: A note on the precedence-constrained class sequencing problem

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