Finding smallest context free grammar that generates a set of sets
Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order.

Conjecture: the optimum is always obtained by some nicely-ordered language, i.e., if $G$ is the smallest such grammar that generates $S$, then there exists a grammar $G'$ of the same size that also generates $S$ and such that $L(G')$ is nicely-ordered. 

If this conjecture is true, then your problem reduces to a kind of grammar induction.  In particular, we are given a finite language, and the goal is to find the minimal context-free grammar that generates that language.

There are heuristics for this problem.  For instance, see the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms, as well as others.

In the general case (given an arbitrary finite language, find the smallest context-free language that generates it), the problem is NP-hard; I don't know if it remains NP-hard when restricted to nicely-ordered finite languages.  You could take a look at the standard proof of NP-hardness and see if it can be adjusted to apply to nicely-ordered languages.  See also Lower bounds on the size of CFGs for specific finite languages for other results in this space.



So, back to the conjecture.  One angle of attack on the problem might to try to prove or disprove this conjecture.  For instance, you might try writing a program to search for counterexamples (generate small random sets, look for the optimal grammar, check whether the conjecture holds, and repeat millions of times).  If the conjecture is true, it might make your problem much easier to solve.  If it's false, it might shed light on what makes the problem challenging.