От­сор­ти­ру­ем дан­ные в таб­ли­це так, чтобы все не­за­ви­си­мые про­цес­сы ока­за­лись в на­ча­ле таб­ли­цы и любой про­цесс был рас­по­ло­жен после всех про­цес­сов, от ко­то­рых он за­ви­сит. Также в таб­ли­цу до­ба­вим стол­бец «Время окон­ча­ния про­цес­са» и за­пи­шем туда дли­тель­но­сти не­за­ви­си­мых про­цес­сов.

Далее рас­счи­та­ем время вы­пол­не­ния остав­ших­ся про­цес­сов:

f(104)  =  4 + f(103)  =  4 + 14  =  18;

f(105)  =  18 + f(103)  =  18 + 14  =  32;

f(106)  =  1 + f(104)  =  1 + 18  =  19;

f(108)  =  3 + f(107)  =  3 + 33  =  36;

f(110)  =  14 + f(109)  =  14 + 8  =  22;

f(111)  =  6 + f(109)  =  6 + 8  =  14;

f(113)  =  11 + f(111)  =  11 + 14  =  25;

f(103)  =  2 + max(f(101), f(102))  =  2 + 12  =  14;

f(107)  =  1 + max(f(105), f(106))  =  1 + 32  =  33;

#f(1112)  =  15 + max(f(110), f(111))  =  15 + 22  =  37.

По­стро­им диа­грам­му вы­пол­не­ния каж­до­го про­цес­са.

За­ме­тим, что время окон­ча­ния ра­бо­ты всех про­цес­сов ми­ни­маль­но, это озна­ча­ет, что про­цес­сы нель­зя дви­гать.

Мак­си­маль­ная про­дол­жи­тель­ность от­рез­ка вре­ме­ни (в мс), в те­че­ние ко­то­ро­го воз­мож­но од­но­вре­мен­ное вы­пол­не­ние мак­си­маль­но­го ко­ли­че­ства про­цес­сов при усло­вии, что все не­за­ви­си­мые друг от друга про­цес­сы могут вы­пол­нять­ся па­рал­лель­но и время окон­ча­ния ра­бо­ты всех про­цес­сов ми­ни­маль­норавна 5.

Ответ: 5.