Execution process with properties of relations

Question

So, I had a quiz last night in my discrete structures class and this question came up:

"There are 3 processors in a computer. The instructions to a computer are labeled 1,2,3,4,5,6,7,8,9,10 each taking 1 second to execute. The relation between a pair of instructions (x,y) is given by R:'x' is executed at the same time or before 'y'. Using the properties of relations, design an execution process including the sequence of execution that takes the minimum time. Relation between the instructions is R={(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9)(10,10)(1,7)(5,8)(2,3)(8,10)(5,10)}"

How would I go about solving this? I want to understand how to do it....but I don't know where to start...

Answer 1

I dont think so. youve got the first instruction called more than once. ive got this:

P1: 1 | 4 | 7 | 10

P2: 2 | 5 | 8

P3: 3 | 6 | 9

Its simple. It only takes four seconds, and all the relationships are satisfied. It is partial order (transitive, reflexive, and antisymmetric) so there is more than one right answer. Also, the 10 could be executed by any of the processors.

Answer 2

The interesting part of $R$ is $$ \begin{align*} &1 \leq 7 \\ &2 \leq 3 \\ &5 \leq 8 \leq 10 \end{align*} $$ Missing are $4,6,9$.

Does that help?