Research tool: validate a schedule and compute its metrics

Every scheduling paper needs a validator: a bug that produces an impossible schedule makes all results meaningless. Write one.

Input: the Chapter 6 format, followed by n lines task processor start describing a schedule (processor numbers start at 1; the finish time is start + w(task, processor)).

Check:

1. Precedence and communication: for every edge i → j, start(j) ≥ finish(i) + (0 if same processor else c(i, j)). Violation: INVALID: Tj starts at S before Ti's data is ready at R.
2. No overlap on a processor: two tasks on the same processor must not overlap in time. Violation: INVALID: Ta and Tb overlap on Pk (a < b).

Print the precedence problems (in edge input order) then the overlap problems (by processor, then a, then b), and Verdict: INVALID schedule (k problems) (problem if k = 1). If valid, print Verdict: VALID, Makespan: M, SLR: …, Speedup: …, Efficiency: … (three decimals, definitions as in OS6.2) and Processor utilization: U% = total busy time ÷ (makespan × p), one decimal. Times as integers when whole.

Input (the HEFT schedule of the small example):

5 2
4 6
5 3
6 8
3 5
4 2
5
1 2 2
1 3 3
2 5 4
3 4 1
4 5 2
1 1 0
3 1 4
2 2 6
4 1 10
5 1 13

Output:

Verdict: VALID
Makespan: 17
SLR: 1.133
Speedup: 1.294
Efficiency: 0.647
Processor utilization: 58.8%