Reordering algorithm to fragment consecutive sequences of ones as much as possible

Question

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chains with length $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an optimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, an optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of length $2$ (because of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n\geq2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.

Answer 1

You can find the optimal solution with a greedy algorithm.

Suppose you want to find if it is possible to find a partial permutation that achieves grouping of size $\leq k$.

You can take strings in order and put from left to right groups of size $k$ (separated by a single zero), until you run out of zeros. If it remains $k'> k$ ones, then it's not possible to find a solution. If $0 < k' \leq k$, continue with the next string, but the first group needs to be of size $k-k'$ (then the other ones of size $k$). If $k'=0$, put all the remaining zeros and go to next string.

Try increasing values of $k$ until you find a solution.

For example, if $k=3$ and your strings are $$001111111, 01111111, 0000111, 01111,0111111$$ you will get the following partial permutation: $$111011101, 110111011, 1011000, 11101,110111$$ and you find that you cannot place the last $1$, so you will not achieve a solution.

However, with $k=4$, you get by greedy search the partial permutation: $$111101110, 111101110, 1110000, 11110, 1111011$$

So $k=4$ is the optimal value.