Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > 0$. I would like to optimize $f$ over $\Pi$, i.e., $\Pi^*=\arg\min_{\Pi\in Perm(n)}f(X,\Pi)$. Is there any good approximate algorithm for this?
At lerast, simulated annealing is simple to program for your problem, so you could just try it ... 


Simulated annealing is a good answer, as given by Kjetil B Halvorsen. You can also try genetic algorithms to mix and crossover multiple tries at different permutations. Say that $\Pi_a$ and $\Pi_b$ are two permutations in your permutation space. If the function $f$ is not a black box, or if it is a black box which you are allowed to use as an oracle, find the value $f_a$ for $\Pi_a$ and $f_a$ for $\Pi_b$, or for a larger population of permutations. Take two or three of the highest scoring permutations based on the values of $f(X,\Pi_j)$ and use a genetic algorithm to crossover between these two permutations. Or take the single highest scoring permutation and then internally permute a short region of the permutation and recalculate $f$. Iterate as necessary. This presumes that $f$ if smoothly continuous and that you can use a hillclimbing style of approach to find local maxima or local minima, whichever you need in your case. 


It may be the case that simulated annealing and genetic algorithms are relatively complicated to understand, bound and implement in this instance. Instead, a very easy starting point would be a simple hillclimbing algorithm. Start with an arbitrary (or better, random) initial permutation $\pi$. The set of moves is the set $M$ of permutations that you can reach by transposing two elements of the permutation. While there is a move that decreases $f$,
This will get you to a local minimum at a cost of $O(n^2)\cdot C(n)$, per move, where $C(n)$ is the cost of calculating $f(\pi)$ for a permutation of $[n]$. Extremely simple and probably not too costly as a first step. You may be able to prove some sort of worst case bound between a local optimum and a global optimum. 


$f(\Pi) = \lambda(\Pi_1, \Pi_2, \ldots, \Pi_n)$
, this is the assignment problem en.wikipedia.org/wiki/Assignment_problem and there is an excellent algorithm. If there is a linear function $\mu$ such that $f(\Pi) = \sum \mu(\Pi_{i}, \Pi_{i+1})$, this is the Traveling Salesman problem and there is no good algorithm. Other situations, of course, may have intermediate difficulties. – David Speyer May 11 '10 at 12:15