Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively.
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 this literal.
- "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_3)$
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? Intuitively 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 the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.
Our matrix $h$ have $2n+1+\sum_i 2k_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K_i=2i+2\sum_{j=1}^i k_i$.
- For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
- For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
- For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
- All the other entries are 0.
For example, for the above example graph the corresponding matrix is
Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.
Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered. For the column $K_i+k_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s_i$. Since column $K_i$ must be assigned to $s_i$, by the consecutiveness we have to lose the columns $K_i+1$ to $K_i+k_i$. Same things happen if the scheduling assign the column $K_i+k_i+1$ to $s_{i+1}$.
Therefore, in order to have the value $\sum_i k_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. 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.