TAOCP 7.2.2.2 Exercise 408
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values.
Section 7.2.2.2: Satisfiability
Exercise 408. ▶ [25] [25] (Open shop scheduling.) Consider a system of $m$ machines and $n$ jobs, together with an $m \times n$ matrix of nonnegative integer weights $W = (w_{ij})$ that represent the amount of uninterrupted time on machine $i$ that is needed by job $j$.
The open shop scheduling problem seeks a way to get all the work done in $t$ units of time, without assigning two jobs simultaneously to the same machine and without having two machines simultaneously assigned to the same job. We want to minimize $t$, which is called the "makespan" of the schedule.
For example, suppose $m = n = 3$ and $W = \begin{pmatrix} 7 & 0 & 0 \ 0 & 2 & 3 \ 4 & 0 & 1 \end{pmatrix}$. A "greedy" algorithm, which repeatedly fills the lexicographically smallest time slot $(i, i, j)$ such that $w_{ij} > 0$ but neither machine $i$ nor job $j$ have yet been scheduled at time $t$, achieves a makespan of 12 with the following schedule:
| M1: | J1 | J3 | |||
|---|---|---|---|---|---|
| M2: | J2 | J1 | J3 | ||
| M3: | J3 | J2 | J1 |
a) Is 12 the optimum makespan for this $W$?
b) Prove that the greedy algorithm always produces a schedule whose makespan is less than $(\max_{n=1}^{m} \sum_{j=1}^{t} w_{ij}) + (\max_{n=1}^{m} \sum_{m=1}^{m} w_{ij})$, unless $W$ is entirely zero.
c) Suppose machine $i$ begins to work on job $j$ at time $s_{ij}$, when $w_{ij} > 0$. What conditions should these starting times satisfy, in order to achieve the makespan $t$?
d) Show that the order encoding of these variables $s_{ij}$ yields SAT clauses that nicely represent any open shop scheduling problem.
e) Let $[W/k]$ be the matrix obtained by replacing each element $w_{ij}$ of $W$ by $\lfloor w_{ij}/k \rfloor$. Prove that if the open shop scheduling problem for $[W/k]$ and $t$ is unsatisfiable, so is the problem for $W$ and $kt$.
Verified: no
Solve time: 3m51s
Solution
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write
$$ x_{i,j}=1\iff x_i=j, $$
where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one value. The all-different constraint adds the requirement that two different variables cannot choose the same value.
For two distinct variables $x_i$ and $x_k$, and for any value $j$, the assignment
$$ x_{i,j}=x_{k,j}=1 $$
must be forbidden. The corresponding clause is
$$ \bar{x}{i,j}\vee \bar{x}{k,j}. $$
Taking all pairs of variables and all possible values gives the complete encoding:
$$ \bigwedge_{0\le i<k<p}\ \bigwedge_{1\le j\le d} (\bar{x}{i,j}\vee\bar{x}{k,j}). $$
These clauses are sufficient. Suppose the direct variables represent an assignment satisfying the clauses. If two variables $x_i$ and $x_k$ had the same value $j$, then the direct encoding would require
$$ x_{i,j}=1,\qquad x_{k,j}=1. $$
The clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
would then be false, contradicting satisfiability. Hence no two variables receive the same value.
They are also necessary. Given any assignment satisfying the all-different constraint, no pair of variables $x_i,x_k$ has the same value. Therefore, for every $j$, at least one of $x_{i,j}$ and $x_{k,j}$ is false, so every clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
is satisfied.
Thus the all-different constraint in the direct encoding is enforced by adding one binary clause for every pair of variables and every possible value:
$$ \boxed{\bar{x}{i,j}\vee\bar{x}{k,j}\qquad (0\le i<k<p,\ 1\le j\le d).} $$
This completes the proof. ∎