An O(n) complex algorithm for solving P | p_{i}=1, in-tree | C_{max} problems.

Used to sequence jobs in parallel systems, when all jobs have processing time of 1 unit and precedence defined by in-tree.

In-tree precedence means that before we process job from given node we need to proceed jobs from its children nodes, so last processed job is always the one placed as tree root (note that root is at the bottom of in-tree).

For example:

- We need to complete jobs 1st and 2nd before we can start 3rd,
- We need to complete jobs 3rd and 4th before starting 5th,
- but we can start 1st, 2nd and 4th job right away,
- Jobs 1st and 2nd are 3-level jobs,
- 3rd and 4th are 2-level,
- 5th is 1-level.

Input:

Set of jobs. Each have up to three preluding jobs.

m – number of machines.

Algorithm consist of three steps.

1) Calculate level for each node in tree.

2) If number of jobs without preluding is less or equal to m – add these jobs to task queues and proceed to 3.

Else choose m highest level jobs without preluding, and add to task queues. Proceed to 3.

3) Remove chosen jobs from tree. Go to 2 until there are jobs left.

Implementation:

**Spreading the tree**

Well… implementation was quite difficult because MPD-helper GUI accepts jobs in form of a list:

I needed a way to spread jobs from list on tree. First step was finding tree root (**NOTE**: job ID isn’t equall to tree node ID. It’s possible to have 10 jobs and 5th as root). After that we simply descend from root via preluding jobs.

If we consider tree given in previous example: 5th is root and it needs 3rd, so add 3rd. 3rd needs 1st, so add 1st. 1st have no preluding jobs, so leave it, and go back to 3rds preluding jobs. 3rd also needs 2nd, so we add 2nd, leave it and go back to 3rd. 3rd have no more preluding jobs, so we go back to 5th job. 5th also need 4th so add it, and – because there are no preluding jobs for 4th, we leave it. There are no jobs left in list so spreading tree is completed.

How do we find root? Well… it’s job that have not following jobs. So we just take first job and iterate through list. If we find it’s preluding something – it’s not root.

while(jobs.size() != 0 && !found){ rootId = jobs.takeFirst()->getId(); for(int i=0; i < jobs.length(); ++i){ if(jobs[i]->preludes(rootId)) break; else if(i == jobs.length()-1) found = true; } }

Now we take newly finded root and pass it to recursive function that add nodes to tree:

int* preludingJobs= jobs[jobID+offsetForList]->getProceedingJobs(); for(int i=0; i<3; ++i){ if(preludingJobs[i] != 0){ workingTree->insertJob(&(preludingJobs[i]),jobID); addNode(workingTree, jobs, preludingJobs[i]); } }

For each preluding job of current node: add this job to node, and pass it to next ‘addNode’ call.

**Calculating node levels**

Simplest way is to use Breadth-first search algorithm, with memorizing first node from next level: when enqueuing node successors, we store first direct child node as ‘level delimeter’. Any jobs that came after delimeter have n+1 level. If we meet delimeter we change it to it’s first direct child.

**Moving jobs from tree to machines task queue**

Algorithm states that we just need to take “number of machines” jobs with greatest level and add to task queue, so at first I just took first two or three* jobs and add to optimal order lists, but it could create situations when in the same time 2nd machine is executing job that needs one executing on 1st (eq. 1st machine executes 3rd job, and 2nd executes 1st job from previous example set)

So I follow that little ‘algorithm’ when adding jobs:

1) We always add job for 1st machine.

2) For all other we check if last job on previous machines isn’t preluding job in question. (Eq. for 2nd machine we check if 1st machine isn’t occupied with preluding job, for 3rd we check 1st and 2nd). If we find preluding we skip current job, and check other from the same level. If we don’t have any jobs left we add one ’empty job’, and go back to 1st machine.

Consider we have 3 machines, and jobs with order described by in-tree I presented before.

- We start with 1st job and 1st machine, and we add it.
- Then we have 2nd job, and 2nd machine. We check last job on 1st machine: 1st isn’t necessary for 2rd job, so we add 2nd job to 2nd machine.
- We cleared jobs from 3rd level. Now we can go for next level.
- We check 3rd job and 3rd machine,
**but**last job from 1st machine is preluding job for current. (3rd job needs 1st and 2nd to be done first). So, we skip 3rd job. - We check 4th job and 3rd machine. Last job on 1st machine is 1, and last job on 2nd is 2. We don’t need them to finish before executing current job, so we add 4th job to 3rd machine.
- We have 3rd job and 1st machine, and we add it.

Now we filled all machines, and go back to 1st.

We cleared jobs from 2nd level, and now we can go for next one. We know that 5th job is root, so we can skip checking other machines and just add root to 1st machine.

In the end sequence plot for given example will look like this:

* It’s my MPD-helper limitation: for Hu algorithm user can solve problem only on 2 or 3 machines.

And that’s it. Output is vector of queues for each machine.