  We consider so-called $N$-fold integer programs (IPs) of the form $\max\{c^T
x : Ax = b, \ell \leq x \leq u, x \in \mathbb Z^{nt}\}, where $A \in \mathbb
Z^{(r+sn)\times nt} consists of $n$ arbitrary matrices $A^{(i)} \in \mathbb
Z^{r\times t}$ on a horizontal, and $n$ arbitrary matrices $B^{(j)} \in \mathbb
Z^{s\times t} on a diagonal line. Several recent works design fixed-parameter
algorithms for $N$-fold IPs by taking as parameters the numbers of rows and
columns of the $A$- and $B$-matrices, together with the largest absolute value
$\Delta$ over their entries. These advances provide fast algorithms for several
well-studied combinatorial optimization problems on strings, on graphs, and in
machine scheduling. In this work, we extend this research by proposing
algorithms that additionally harness a partition structure of submatrices
$A^{(i)}$ and $B^{(j)}$, where row indices of non-zero entries do not overlap
between any two sets in the partition. Our main result is an algorithm for
solving any $N$-fold IP in time $nt
log(nt)L^2(S_A)^{O(r+s)}(p_Ap_B\Delta)^{O(rp_Ap_B+sp_Ap_B)}$, where $p_A$ and
$p_B$ are the size of the largest set in such a partition of $A^{(i)}$ and
$B^{(j)}$, respectively, $S_A$ is the number of parts in the partition of $A =
(A^{(1)},..., A^{(n)}), and $L = (log(||u - \ell||_\infty)\cdot
(log(max_{x:\ell \leq x \leq u} |c^Tx|))$ is a measure of the input. We show
that these new structural parameters are naturally small in high-multiplicity
scheduling problems, such as makespan minimization on related and unrelated
machines, with and without release times, the Santa Claus objective, and the
weighted sum of completion times. In essence, we obtain algorithms that are
exponentially faster than previous works by Knop et al. (ESA 2017) and
Eisenbrand et al./Kouteck{\'y} et al. (ICALP 2018) in terms of the number of
job types.
