Muntz-Coffman Algorithm (Scheduling)

Question

I'm wondering how exactly do you calculate the time slices (2, 4, 5.5, 7, 8.5).

Answer 1

Muntz–Coffman is basically the critical path method. The priority of each job is the maximum duration of a chain of dependencies starting from that job. At each point in time, the running jobs are those with the highest priority.

Initial priorities are computed in linear time in reverse topological order.

K: 1 + max(0) = 1
H: 1 + max(0, K) = 2
I: 2 + max(0, K) = 3
J: 4 + max(0) = 4
E: 3 + max(0, H) = 5
F: 2 + max(0, H, I) = 5
G: 3 + max(0, I, J) = 7
A: 2 + max(0, E, F) = 7
B: 1 + max(0, E, F, G) = 8
C: 1 + max(0, G) = 8
D: 2 + max(0, F, G) = 9

D (2 units) is the unique maximum, so it gets a machine all to itself. B (1 unit) and C (1 unit) are tied, so they split the other machine 50/50. At time t, the priority of D is 9 - 2t, and the priority of B and C is 8 - t. Until these three jobs finish, they remain above priority 7, the next highest, D is above B and C, and B and C remain tied.

At time 2, the next highest are A (2 units) and G (3 units), which each receive their own machine. After 2 units of time, A is done, and G's priority has been reduced to 5, tying with E and F. Now E, F, and G are all scheduled with an even three-way split, which lasts until time 5.5 at which point G is finished and the the others are now at priority 4, tying them with J.

Three-way work continues until at time 7, F is done and E's and J's priorities have slipped to 3. Now E, I, and J are scheduled until E is done and I's and J's priorities are down to 2, at which point (time 8.5) H, I, and J are scheduled. H and I finish and J is at 1, at which point (time 10) J and K are scheduled 50/50 until the end at time 11.