C # Ordered Combination Algorithm

Question

I am trying to develop a C # application that will generate a list of all possible permutations within a limit and cost. For example, I have a list of 80 tasks. Each task has a value of (1-5) (usually 3), and each engineer has a limit on how much they can do, usually a value of 20.

At the moment, I started by creating a list of all possible combinations (n! / (K! * (Nk) !, where n is the total number of tasks, k - 2). The connection between each work should be weighted with the distance between each task.

From here I would like to choose the initial initial work and make a list of all possible combinations of tasks (from the starting task) to the limit of 20, and then sort by the sum of the weight. The lowest weight route will win and will be allocated to the engineer. My problem is that I do not know how to approach this - which data structure would be better?

Usually about 6-8 engineers (depending on the workload), I planned to route each engineer one at a time - as soon as the route was assigned to another engineer, these tasks will be removed from the list, and a new task will be launched with a new set of generated combinations. Does this sound like an acceptable approach?

Any help would be appreciated.

Answer 1

I would try simulated annealing, an algorithm for finding the global optimum by randomly testing configurations in accordance with the energy of the system.

http://en.wikipedia.org/wiki/Simulated_annealing

Check out the article for pseudocode.

Answer 2

You can look at the Microsoft Solver Foundation: http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx

Also, check out Bart de Smet Linq on Z3 if you're on Linq on Anything :) http://channel9.msdn.com/Shows/Going+Deep/Bart-De-Smet-LINQ-to-Z3

Answer 3

There is no efficient algorithm to solve this problem. I would use a genetic algorithm (it is not necessary to find the optimal solution, but found an acceptable solution).