The poset scheduling problem

Let P and Q be two finite posets and for each pP and qQ let c(p, q) be a specified (real-valued) cost. The poset scheduling problem is to find a function s: PQ such that _pP c(p,s(p)) is minimized, subject to the constraints that p in P implies 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.This work was done in the fall semester of 1982 when the second author was visiting Cornell University. The first author was his research associate during that period.The first author was supported by National Science Council of Republic of China under Grant NSC73-0208-M008-08 when he wrote the final version of this paper.