THINK FIRST·CODE LATER

← All labs

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.

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os6-3-data-1.txt — first 14 lines of 27

10 3
14 16 9
13 19 18
11 13 19
13 8 17
12 13 10
13 16 9
7 15 11
5 11 14
18 12 20
21 7 16
15
1 2 18
1 3 12
What your program must print for os6-3-data-1.txt
OCT table:
T1: 48 38 53  rank_oct=46.33
T2: 35 19 35  rank_oct=29.67
T3: 28 22 27  rank_oct=25.67
T4: 38 19 36  rank_oct=31.00
T5: 32 19 32  rank_oct=27.67
T6: 23 18 30  rank_oct=23.67
T7: 21 7 16  rank_oct=14.67
T8: 18 7 16  rank_oct=13.67
T9: 20 7 16  rank_oct=14.33
T10: 0 0 0  rank_oct=0.00
T1 -> P2 start 0 finish 16 (O_EFT 54)
T4 -> P2 start 16 finish 24 (O_EFT 43)
T2 -> P2 start 24 finish 43 (O_EFT 62)
T5 -> P3 start 27 finish 37 (O_EFT 69)
T3 -> P1 start 28 finish 39 (O_EFT 67)
T6 -> P1 start 39 finish 52 (O_EFT 75)
T7 -> P1 start 52 finish 59 (O_EFT 80)
T9 -> P2 start 50 finish 62 (O_EFT 69)
T8 -> P1 start 62 finish 67 (O_EFT 85)
T10 -> P2 start 78 finish 85 (O_EFT 85)
Makespan: 85

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os6-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content os6-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

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.