CODEWITHSUNDEEP
algorithmgraph
Paweł Orliński
Paweł Orliński

Reputation: 249

Optimal task order

You have n tasks, with execution times depending on which tasks had been done before. If some of the task had been yet done, the execution time of the task may be shorter. Create algorithm that finds optimal task order which takes the shortest time possible.

E.g.

n=3

tasks A, B, C

T(A|B,C) = time of execution task A given that B, C had been done earlier

T(A|) = time of execution task A as first task

T(A|) = 50

T(A|B) = 40

T(A|C) = 40

T(A|B,C)= 30

T(B|) = 30

T(B|A) = 25

T(B|C) = 20

T(B|A,C)= 15

T(C|) = 20

T(C|A) = 15

T(C|B) = 10

T(C|A,B)= 10

Any hints? I was thinking about Dijkstra algorithm but in this case it seems not to be working.

Any help appreciated.

Upvotes: 0

Views: 203

Answers (1)

DAle
DAle

Reputation: 9127

Let's take minimal Hamiltonian path problem with known start vertex A and create the input data for this task order problem.

T(A|) = 0
T(i|) = inf, for any i ≠ A
T(i|j) = edge_weight(i, j), for any i,j

If we could solve this task order problem we could solve the minimal Hamiltonian path problem that is NP-hard. Thus, there is no known algorithm that solves this problem in polynomial time.

Now let's solve this problem for relatively small n. On every step of tasks execution, we have the set of already completed tasks S (it is empty in the beginning). Then we can execute the next task choosing the best available time among our data, add it to the set S and go to the next step. This naturally brings us to the dynamic programming approach with the state S - a set of already completed tasks (this can be implemented with a bitmask): enter image description here
where minTime(S, i) is a minimal execution time of task i when all tasks from the set S have been already executed.

Upvotes: 1

Related Questions