# Optimize sequence when item costs are interdependent

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there.

You're given a list of media items--songs, let's say--to play. You must play every song once, with no repetitions, but you get to pick the play sequence. The goal of sequencing is to maximize variety. For example, it would be undesirable to play two songs by the same artist back-to-back.

My initial thought was to treat items analogously to magnets that repel each other according to their degree of similarity. (Details below.) A simple brute-force implementation shows that this approach works well. However, it's of course computationally intractable. Not only are there $n!$ permutations to evaluate, but calculating the cost of a given permutation is $O(n^2)$, because every song exerts force on every other song.

Formally: Given a set of $n$ items $\{T_1, T_2, ... T_n\}$, find the permutation $P$ $\{T_{p1}, T_{p2}, ... T_{pn} \}$ that minimizes cost function $C(P)$:

$$C(P) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{S(T_{pi}, T_{pj})D(T_{pi})D(T_{pj})}{R(T_{pi}, T_{pj})^2}$$

where $S()$ is a measure of similarity between two items (take this as given), $D()$ is the duration (think "mass") of a given item, and $R()$ is the time-distance between item centerpoints.

Scheduling problems of this type often seem to have dynamic programming solutions, but those solutions usually rely on the incremental cost of the sequence-ending item being dependent only on the item's completion time. Here, the cost of the final item depends on the positioning of all other items in the sequence, which would seem to rule out that approach.

Possible ameliorating factors: A) Total cost is a monotonically increasing value as items are added to a sequence, so some unpromising starts can be pruned from the search if they already exceed the best-so-far result. B) For a given sequence prefix, interactions internal to the prefix need be calculated only once. C) True optimality is not necessary, although it would be helpful to have some guarantee of reasonability.

Questions: The usual. :-) Is this a known problem that has a literature behind it? What would the standard name be? Does any particular search method stick out as being especially appropriate? In particular, would simulated annealing be a good approach? Is there a better formulation of the problem that would have better tractability?