Minimize same placed elements in a list of permutations (Heap)
My initial guess, based on some cursory knowledge about Permutohedrons:

Given your set $S = {1,2,3,...}$, generate all permutations $P(S)$ and define a multigraph $G(V,E)$ where $V = P(S)$ (each permutation is a vertex) and the edge-set $E$ consists of pairs of permutations that share an element at a common location (e.g. $123456$ and $123465$ are connected by $4$ edges).

Your problem is then picking a subset of $V' \subset V$ s.t. the subgraph induced by $V'$ has as few edges as possible.

Considerations: 


You can use a weighted graph instead of a multigraph. Replace $n$ edges with 1 edge with weight $n$. The optimization objective would then be total edge weight of the induced subgraph.
Based on the many symmetries, I would guess that it should be possible to achieve a very good (maybe even optimal) solution with a greedy algorithm.


Possible greedy algorithm:


Construct graph, initialize $V' = \emptyset$
Until $|V'| = n$:


For each $v \in V \setminus V'$: $v^+ :=$ total weight of edges between $v$ and $w\in V'$
If $v^+ = 0$, add $v$ to $V'$. Else, add vertex with lowest $v^+$.