Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose each variable $x_i$ appears $k_i$ times in the formula.
We design a colored DAG $G$ whose vertices consists of three parts:
- "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
- "Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing the variable $x_i$.
- "Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.
The edges include:
- $s_{i-1}v_i(1)$, $v_i(j)v_i(j+1)$, $v_i(k_i)s_i$;
- $s_{i-1}\bar{v}_i(1)$, $\bar{v}_i(j)\bar{v}_i(j+1)$, $\bar{v}_i(k_i)s_i$;
- and $s_{n+i'-1}w_{i'}(j')$, $w_{i'}(j')s_{n+i'}$.
For instance, from the 3CNF
$(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_4)$
the following graph is constructed (The edge directions are from left to right).
Now it is not hard to see that the original 3CNF is satisfiable if and only if there is a $s$-$t$ path with different vertex colors in $G$.
(By the way, it is a by-product that the existsence of $s$-$t$ path with different vertex colors in colored DAG is $\textsf{NP-hard}$. I didn't find many literatures about this problem in computational perspective. If you know, please comment!)
So what is the relation between $G$ and OP's problem? What we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and each part is mapped to a part of consecutive columns (time slots). A maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.
The cut vertices separate $G$ into $n+k$ parts. The last $k$ parts, corresponding to the $k$ clauses, are easy. For the $(n+i')$-th part, there is only one column, and the entries in the rows corresponding to the three literals are $1$ while others are $0$.
Now consider the $i$-th part corresponding to the assignment of $x_i$. In the $i$-th part there are $2k_i+3$ columns (labeled from $-1$ to $2k_i+1$), and we add two colors $x_i(0)$ and $\overline{x_i}(k_i+1)$ which will only be used here. The non-zero entries are:
- $h(x_i(0))=\{X,Z,Y,0,0,\ldots,0\}$, $h(\overline{x_i}(k_i+1))=\{0,0,\ldots,0,Y,Z,X\}$.
- $h(x_i(k_i),2k_i)=Y$, $h(\overline{x_i}(1),0)=Y$.
- $h(x_i(j),2j)=h(x_i(j),2j+1)=Y$, $\forall 1\leq j\leq k_i-1$.
- $h(\overline{x_i}(j),2j-3)=h(\overline{x_i}(j),2j-2)=Y$, $\forall 2\leq j\leq k_i$.
For example, if $k_i=3$ the corresponding submatrix is $$ \begin{array}{rccccccccc} x_i(0)\, & X & Z & Y & 0 & 0 & 0 & 0 & 0 & 0\\ x_i(1)\, & 0 & 0 & 0 & Y & Y & 0 & 0 & 0 & 0\\ x_i(2)\, & 0 & 0 & 0 & 0 & 0 & Y & Y & 0 & 0\\ x_i(3)\, & 0 & 0 & 0 & 0 & 0 & 0 & 0 & Y & 0\\ \overline{x_i}(1)\, & 0 & Y & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \overline{x_i}(2)\, & 0 & 0 & Y & Y & 0 & 0 & 0 & 0 & 0\\ \overline{x_i}(3)\, & 0 & 0 & 0 & 0 & Y & Y & 0 & 0 & 0\\ \overline{x_i}(4)\, & 0 & 0 & 0 & 0 & 0 & 0 & Y & Z & X \end{array} $$
Besides, for each cut vertex $s_1,\ldots,s_{n+k-1}$, there is a corresponding column with only one $X$ at the corresponding row. The values $X,Y,Z$ satisfy $1\ll Z\ll Y\ll X$. The ratios $Z/1, Y/Z, X/Y$ can be large powers of $k$ and $n$. Finally we glue all parts together in order.
Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+n+k-1)X+\sum_i 2k_iY+nZ+k$.
Consider the scheduling achieving the maximum value. Since there are exactly $(2n+n+k-1)$ columns in $h$ containing (actually only one) $X$, they should all be covered. Next we claim in each assignment part of $x_i$, the maximum value is 2k_iY+Z. It is done by the following simple observations:
- For two consecutive $Y$'s in a row, if one of them is chosen, it won't get worse if we also choose the other one.
- For the consecutive $ZY$ or $YZ$ in a row, if the $Y$ is chosen then the $Z$ must be chosen (because of the consecutiveness and the $X$ nearby is already chosen), and if the $Z$ is chosen it won't get worse if we also choose the $Y$.
Therefore, in the optimal scheduling we can assume for each conseutive $YY$, $YZ$ or $ZY$ in a row, either both of them are selceted or neither. It is easy to check that in this case, we either assign all the slots to $x_i$ or all to $\overline{x_i}$, which both give rise to a value of $2k_iY+Z$.
Now this can be regarded as an assignment, and since a person could only have consecutive blocks, if $x_i$ is chosen then it cannot be used in the clause part. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.
As a conclusion, deciding the maximum value of a legal scheduling is in $\textsf{NP-hard}$. Maybe that's why all our previous attempts to find an algorithm failed.