THINK FIRST·CODE LATER

← All labs
OS6.3 Review Chapter 6

PEFT: look-ahead with the optimistic cost table

Problem

Implement PEFT (Arabnejad and Barbosa, 2014).

Input: the Chapter 6 format.

  1. Optimistic cost table: OCT(i, k) = 0 for exit tasks; otherwise OCT(i, k) = max over successors j of [ min over processors x of ( OCT(j, x) + w(j, x) + (0 if x = k else c(i, j)) ) ]. rank_oct(i) = average of OCT(i, k) over processors.
  2. Scheduling: repeatedly take, among the ready tasks (all predecessors scheduled), the one with the highest rank_oct (ties → smaller task number). For each processor compute EFT exactly as in HEFT (with insertion) and O_EFT = EFT + OCT(i, k); choose the processor with the minimum O_EFT (ties → lowest processor number).

Output: OCT table: then one line per task Ti: v1 v2 ... vp rank_oct=R (values as integers when whole, otherwise two decimals; rank_oct with two decimals; note the two spaces before rank_oct), then one line per scheduled task Ti -> Pk start S finish F (O_EFT X) in scheduling order, then Makespan: M.

Example: on the small five-task DAG of OS6.1, PEFT produces the same schedule as HEFT (makespan 17); on the classic 10-task DAG it produces makespan 85 — see the tests.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.

← OS6.2 HEFT: reproduce a classic result OS6.4 Research tool: validate a schedule and compute its metrics →