Is this greedy algorithm optimal? How to prove it?

54 Views Asked by At

Assuming a set does not allow duplicate elements, and a list allows duplicate elements below.

In a task scheduling problem, there are n tasks denoted by $t_1,t_2,...,t_n$. Each task requires a list of resources which can be represented by a list of numbers(e.g. {1,1,3,5,6,6,6} as a list of resources). In the meanwhile, when a task $t_i$ completes, $t_i$ produces a list of resources (e.g. {4,7,7}). The required and produced list of resources of a task do not share any common elements.

The total required resources may not match with the production of all the task. So there is a external resource pool which can provides any kinds and amount of resources.

Here comes the question:

Given the task set $t_1,t_2,...,t_n$ and $t_i$ requires resources list $d_i$ and produces resources list $p_i$. What is the optimal order of task execution? Here 'optimal' means that the total resources required from the external pool is minimum.

I make a greedy algorithm as follow:

Given a initial empty list production list donated by P.

At one certain step, assuming there are tasks $t_1,...,t_{i-1}$ that already completed in the greedy algorithm.

For each task left, let's take $t_i$ as an example.

Let $O$ represents the redundant production of completed tasks $t_1,...,t_{i-1}$. Here redundant means that the resource produced by a task is not used by the task after it.

  1. For $t_i$, calculate $ult_i= |d_i-P|-(|D\cap(P+p_i)|-|D\cap P|)$. Here $D=d_{i+1}+...+d_{n}$
  2. For each task left ($t_i,...,t_n$),calculate $ult_i$, choose the task with the least $utl_i$ as the next task to complete.
  3. Remove task from the left task set.
  4. Delete $P\cap d_i$ from P
  5. Add $p_i$ to $P$.

Repeat the steps above until all the task is selected.

In 1. $|d_i-P|$ (diff set,or diff list) means how many external resource $t_i$ need.

$(|D\cap(P+p_i)|-|D\cap P|)$ means the profit of $t_i$

$|D\cap(P+p_i)|$ means the profit of all the completed task if we choose $t_i$. $|D\cap P|$ means the profit without $t_i$.

Is this greedy algorithm optimal?

If yes, how to prove it?

If no, why?