The poset scheduling problem (Q1062616): Difference between revisions

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.