Scheduling complete intrees on two uniform processors with communication delays

Scheduling chains on uniform processors

Scheduling chains on uniform processors with communication delays

✍ Wieslaw Kubiak1; Bernard Penz; Denis Trystram 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 200 KB

We show that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize makespan is NP-hard in the strong sense. We also give a heuristic that generates solutions with known, and relatively small, absolute error for this problem. Th