TAOCP 7.2.2.2 Exercise 408
Number the rows and columns of the diagram from $0$ to $3$.
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: 3m47s
Solution
Number the rows and columns of the diagram from $0$ to $3$. A rearrangement that works is
$$ \begin{array}{|c|c|c|c|} \hline T&H&E&A\ \hline T&R&O&F\ \hline U&C&M&G\ \hline P&M&I&N\ \hline \end{array} $$
The phrase to be traced, ignoring the separators, is
$$ \text{THEARTOFCOMPUTERPROGRAMMING}. $$
A sequence of positions that traces this phrase is
$$ \begin{aligned} &(0,0),(0,1),(0,2),(0,3),(1,1),(0,0),(1,2),(1,3),(2,1),\ &(1,2),(2,2),(3,0),(2,0),(1,0),(0,2),(1,1),(3,0),\ &(1,1),(1,2),(2,3),(1,1),(0,3),(2,2),(3,1),(3,2),\ &(3,3),(2,3). \end{aligned} $$
Reading the letters in these positions gives
$$ \begin{aligned} &T,H,E,A,R,T,O,F,C,O,M,P,U,T,E,R\ &\qquad P,R,O,G,R,A,M,M,I,N,G, \end{aligned} $$
which is exactly
$$ \text{THE_ART_OF_COMPUTER_PROGRAMMING}. $$
For consecutive positions in the displayed path, the displacement is always either a king move, meaning that the row and column changes are each at most $1$, or a knight move, meaning that the absolute changes are $1$ and $2$ in some order. The only repeated type of move that needs checking is the transition between the final occurrences of letters, and the last transition is
$$ (3,3)\rightarrow(2,3), $$
which is a king move. Thus the former exceptional step from $R$ to $G$ has also been replaced by a legal move.
Therefore the rearranged diagram above permits the complete phrase to be traced using only king moves and knight moves.
$$ \boxed{ \begin{array}{|c|c|c|c|} \hline T&H&E&A\ \hline T&R&O&F\ \hline U&C&M&G\ \hline P&M&I&N\ \hline \end{array} } $$
This completes the solution. ∎