optimisation algorithm for mathching positions

I am doing an RTS game and are trying to incorporate formations in it. I have nice tool that generates different formations, the problem comes when matching current positions with the generated ones so that the total walk distance will be the shortes. Or what I realy want, the shortes time for all units to get into its desired location. If I am not totaly wrong this is an NP-complete problem, so what I realy want is an algorithm that will just come up with a good aproximation to the best solution since the best solution is realy hard to find. To do this even harder it would have been nice to give each location a weight with front/back/left/right/midle and then have each unit have a prefered location. For example 0.5 front, 0.25 left, 0.25 right. This algorithm should then try to make the best distribution of the units on the posible locations consering both the total time to move and the best possible match with its desired location. So if any of you know something about this, or can give me some hits I would appriciate this a lot. Utopico