Verifying consistency of strict and non-strict partial orders constraints
You may find it helpful to think of your problem in terms of equalities and strict inequalities. 

In the case of the constraints being equalities or disequalities there is a simple saturation procedure based on transitivity of equality.  Strict inequalities can be represented by directed edges in a graph. You can then compute strongly connected components to reason about dependencies between sets of variables. If you have uninterpreted functions, you can use congruence closure.

I would imagine that the first results date to the 50s or at least the 70s, but I do not have a good reference for you. Recent literature in which these ideas occur is the paper below.


  An Interpolating Decision Procedure for Transitive Relations with Uninterpreted Functions, Georg Weissenbacher.