The poset scheduling problem

DOI10.1007/BF00334849MaRDI QIDQ1062616zbMATH OpenFDO

Authors Jack Edmonds, Gerard Jennhwa Chang

Publication date 1985

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00334849

zbMATH Keywords

closed set problemminimum cut problemNP-completeNP-hardposet scheduling

Mathematics Subject Classification ID

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

Review text

Let P and Q be two finite posets and for each \(p\in P\) and \(q\in Q\) let c(p,q) be a specified (real-valued) cost. The poset scheduling problem is to find a function s:P\(\to Q\) such that \(\sum_{p\in P}c(p,s(p))\) is minimized, subject to the constraints that \(p<p'\) in P implies \(s(p)<s(p')\) in Q. We prove that the poset scheduling problem is NP-hard. This problem with a totally ordered poset Q is proved to be transformable to the closed set problem or the minimum cut problem in a network.

Recommendations

• scientific article; zbMATH DE number 4189460
• Schedule-induced posets
• Scheduling of project networks
• Scheduling partially ordered jobs faster than \(2^{n }\)
• scientific article; zbMATH DE number 512916

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• Resource constrained scheduling as generalized bin packing
• Selected Applications of Minimum Cuts in Networks
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

Cited in

(9)

• Schedule-induced posets
• A note on order preserving matchings
• The setup polytope of \(N\)-sparse posets
• Maximizing the expected net present value in a project with uncertain cash flows
• scientific article; zbMATH DE number 4033467 (Why is no real title available?)
• scientific article; zbMATH DE number 4189460 (Why is no real title available?)
• On project scheduling with irregular starting time costs
• Minimizing the sum cost in linear extensions of a poset
• Project scheduling with irregular costs: complexity, approximability, and algorithms

This page was built for publication: The poset scheduling problem

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