Scheduling: Existence of specific total order A question arising from a scheduling problem:
I have a finite set $X$ with elements $x_i$ and some preorder $\leq$.
I have pairs $p_j$ of $x_i$ (i.e. $p_j$ = $(x_k, x_l)$) with the property that $x_k \leq x_l$.
I say that for two pairs $p, p'$ : $p \leq p'$ when for all $x \in p, x' \in p': x\leq x'$.
I call two pairs $p = (x_1, x_2), p' = (x'_1, x'_2)$ unrelated if for no $x \in p$, $x' \in p'$ holds: $x \leq x'$ or $x' \leq x$.

Question: Does there always exists a total order $\leq'$ of $X$ which is compatible with $\leq$, with the property that $p \leq' p'$ or $p' \leq' p$, for all unrelated pairs $p, p'$?

To give an example:

$X = \{1,2,3,4,5\}$ , $p_1 = (1,2), p_2 = (3,5)$ and a partial order (preorder) $1 \leq 2, 3 \leq 5$. E.g. by topological sorting I can obtain a total order ($ 1 \leq 2 \leq 3 \leq 4 \leq 5$) which satisfies $p_1 \leq p_2$. However, tsort can also give me the total order ($1 \leq 3 \leq 2 \leq 4 \leq 5$), which does not satisfy $p_1 \leq p_2$ or $p2 \leq p1$ (here, $\leq$ refers to the corresponding total orders).

The relation to a specific scheduling problem is that I have undetermined times $x_i$ at which I acquire or release a resource. To avoid deadlocks, the pairs of (acquisition, release) must not overlap.

(In the actual problem, some time $x_i$ can occur in multiple such pairs, but that's another problem not considered here).

UPDATE

I think I found at least some idea, yet not sure if it is correct:
The graph below shows the general structure of such a preorder (which we now treat as a directed acyclic graph): Given two such pairs $(x, x')$ and $(y, y')$, there is a path from $x$ to $x'$ (and from $y$ to $y'$). There may be nodes in-between, and edges connecting to that path. However, by our assumption that the pairs are unrelated, none of the incoming or outgoing edges in the section $x \to x'$ can reach $y$ or $y'$.
We can now start constructing a topological sort. Without loss of generality, we reach $x$ as the first node of all pairs which we consider (which is not necessarily unique, but that does not matter). Because there are no edges between $x$ and $x'$ which connect from/to another point $y$ from another pair, we can continue our topological sort until we reach $x'$. Then, the pair $(x, x')$ is "compact" in our final order, that is, will have a $\leq'$ relation to all other pairs (because no point of any other reservation is between $x$ and $x'$, by construction of the total order $\leq'$). We can repeat this procedure every time we reach the first point of such a pair.

Is there any flaw in this argument?
I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it.



Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological sort.

Here is an other attempt at a proof:



Let $\leq$ denote a partial order on $X$. I claim there exists a total order $\leq'$ compatible with $\leq$ such that the following never occurs:
$a\leq'\alpha\leq'b$
where $a \leq b$, and $\alpha$ is incomparable to both $a$ and $b$. 
(Note that when I say comparable/incomparable I always mean with respect to $\leq$)

To see this choose a compatible total order $\leq'$ with the least amount of such "bad" pairs $(a\leq b)$. Suppose that this amount is non-zero and let $(a\leq b)$ be such a pair with smallest $a$ (with respect to $\leq'$). Let $\alpha_1 \leq' \alpha_2 \leq'\ldots\leq'\alpha_k$ denote all elements between $a$ and $b$ which are incomparable to both $a$ and $b$.

Now create a new total order $\leq^*$ from $\leq'$ by moving all $\alpha_i$'s right in front of $a$ to get $\alpha_1 \leq^* \alpha_2 \leq^*\ldots\leq^*\alpha_k\leq^*a$, the rest remaining unchanged. Notice that this is still compatible with $\leq$, as the only thing that could have gone wrong is that there was some $a\leq c \leq \alpha_i$ but this is impossible as $a$ and $\alpha_i$ are incomparable.

Notice also that, because all elements between $a$ and $b$ (with respect to $\leq^*$) are now comparable to $b$, we have created no "bad" pair $(\alpha_i\leq x)$ with $a\leq^* x \leq^* b$, otherwise we would have $\alpha_i\leq x \leq b$ meaning that $\alpha_i$ and $b$ are comparable. And we have created no "bad" pair $(x\leq a)$, otherwise $(x\leq b)$ would have been a bad pair to start with, contradicting our choice of $a$. Any other type of "bad" pair we created must have already existed previously.

Because $(a,b)$ is no longer a bad pair, $\leq^*$ has strictly less bad pairs than $\leq'$, which is impossible by definition of $\leq'$. Thus, $\leq'$ had no bad pairs to start with. 

It is easy to show from here that $\leq'$ meets your requirements.