Optimal ordering of tasks

I came across the following problem. There are N tasks. Each task consumes several resources, produces several resources and generates a profit which is the difference between output and input resources. What is the best sequence of the tasks, i.e. which sequence generates the highest profit?

I could not find any effective solution and so retracted to an exhaustive search technique "generate and test". So, I generate all partial sequences of the numbers {1, 2, .. N}, compute the profit of the corresponding tasks and store the maximal achieved value. Notice that some partial sequences cannot be extended because the input resources of the remaining tasks have been already comsumed.

For example in the case of N = 3, I generate:

1
1 2
1 2 3
1 3
1 3 2
2 
2 1
2 1 3
2 3
2 3 1
3
3 1
3 1 2
3 2
3 2 1

This corresponds to all pathes in the search tree:

Notice that the complete pathes correspond to the N! permutations.

During my investigations I recognized that the problem at hand resembles the well-known N-queens problem: position N queens on a NxN chessboard such that they do not threaten each other. The queens are positioned in columns from 1 to N. I each new column the queen is placed in a row that is not yet occupied by a previous queen. Then it is tested whether the new queen is not attacked diagonally by the previous queens. If it is not attacked the position is accepted and a new column addressed. If it is attacked a new row is tried and if no row in the current column is available the state is backtracked to the previous column and continued there. The partial path, e.g. {2, 1} represents the rows of the queens in the first two columns.

In the following I will present various Java programs to produce all partial sequences of the {1, 2, ... N} and test them on the example of N queens.

under construction...

Comments