Is the implementation of HEFT correct?

[peerdavid]

Hello,

I think there are two problems with the current implementation of HEFT (findFinishTime):

        while (j >= 0) {
            Event current = sched.get(i);
            Event previous = sched.get(j);

            if (readyTime > previous.finish) {
                if (readyTime + computationCost <= current.start) {
                    start = readyTime;
                    finish = readyTime + computationCost;
                }

                break;
            }
            if (previous.finish + computationCost <= current.start) {
                start = previous.finish;
                finish = previous.finish + computationCost;
                pos = i;
            }
            i--;
            j--;
        }

(1) This loop assumes that sched is sorted by the start time right? But in this function we simply call sched.add such that a sorted list is no more guaranteed.
(2) In the code above we set the start time to the readyTime in one case. Shouldn't it be the previous.finish time? Otherwise it could. i.e. be that two tasks get the same start time...

Thank you, David

[BrokenPen]

1. The list is still in order by calling sched.add
2. No two tasks get the same start time..

---

However... I found out if use in Random schedule algorithm this loop will have two tasks get the same start time....

so you have to make a little change.. like the follow

        for(int i = 0; i < sched.size() -1; i++) {
            Event current = sched.get(i);
            Event previous = sched.get(i+1);

            // case of between two task
            if (previous.finish <= readyTime) {
                if (readyTime + computationCost <= current.start) {
                    start = readyTime;
                    finish = readyTime + computationCost;
                    pos = i;
                    break;
                }
            }

            // the case of delay readyTime
            if (previous.finish + computationCost <= current.start) {
                if (readyTime <= previous.finish) {
                    start = previous.finish;
                    finish = previous.finish + computationCost;
                    pos = i;
                    break;
                }
            }
        }

---

if (readyTime >= sched.get(0).finish)
if (readyTime > previous.finish) {

I wonder why these two conditions are greater equal and another is greater
the condition become inconsistent
So I change these as always >= or <=

---