Single Machine Scheduling with Precedence Constraints of Dimension 2

DOI10.1287/MOOR.9.2.248zbMATH Open0541.90054OpenAlexW2083199589MaRDI QIDQ3329201FDOQ3329201

Authors George Steiner 

Publication date 1984

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d9512c3fa3c6abac1da23e73583e85187ccf3619

zbMATH Keywords

acyclic directed graphprecedence constraintsfeasible sequencepartial order dimension

Mathematics Subject Classification ID

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

Recommendations

• Single Machine Scheduling with Series-Parallel Precedence Constraints
• scientific article; zbMATH DE number 5605136
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Scheduling partially ordered jobs faster than \(2^n\)

Cited In (15)

• The use of dynamic programming in genetic algorithms for permutation problems
• On the computational complexity of the order polynomial
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
• An algorithm to generate the ideals of a partial order
• Scheduling partially ordered jobs faster than \(2^{n }\)
• Single Machine Scheduling with Series-Parallel Precedence Constraints
• The minimum dummy task problem
• Understanding the generalized median stable matchings
• Transitive closure for restricted classes of partial orders
• On the complexity of dynamic programming for sequencing problems with precedence constraints
• On estimating the number of order ideals in partial orders, with some applications
• Algorithmic combinatorics based on slicing posets
• Single machine precedence constrained scheduling is a Vertex cover problem
• A compact labelling scheme for series-parallel graphs

This page was built for publication: Single Machine Scheduling with Precedence Constraints of Dimension 2

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