Generalized sorting algorithm on partially ordered set generated by a relation
You can efficiently test whether $\preceq$ extends to a partial order using topological sorting.  Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$.  Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically sorting the graph).

Moreover, we can describe a minimal partial order $\le$ that is consistent with $\preceq$, as follows.  Compute the transitive closure of this graph. Now declare $x \le y$ iff there's an edge $x \to y$ in the transitive closure, or $x=y$.  (Equivalently, declare $x \le y$ iff $y$ is reachable from $x$ in zero or more steps, in the graph derived from $\preceq$.)  By construction, the relation $\le$ defined in this way will automatically be reflexive and transitive; if the original graph has no cycles, then it is easy to prove that the relation $\le$ will be anti-symmetric as well and thus will be a partial order.