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.
- For $t_i$, calculate $ult_i= |d_i-P|-(|D\cap(P+p_i)|-|D\cap P|)$. Here $D=d_{i+1}+...+d_{n}$
- 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.
- Remove task from the left task set.
- Delete $P\cap d_i$ from P
- 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?