Scheduling: Existence of specific total order

Question

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?

Answer 1

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.

Answer 2

It seems you consider intervals totally contained in others or disjoint only. Intervals can overlap partially, e.g. $[1, 3), [2, 4)$.

Scheduling in the general case (any value function for tasks, where you look for the maximum sum of values) is hard (the corresponding decision problem is NP-complete). There is copious literature on algorithms to solve this, typically using dynamic prigramming. The special case where the value is the same for each task can be solved by a greedy algorithm: program the task that ends earliest, eliminate tasks conflicting with it, and repeat.