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

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

f(4)  =  7 + f(3)  =  7 + 9  =  16;

f(5)  =  6 + f(3)  =  6 + 9  =  15;

f(6)  =  2 + f(5)  =  2 + 15  =  17;

f(8)  =  2 + f(6)  =  2 + 17  =  19;

f(11)  =  6 + f(9)  =  6 + 7  =  13;

f(12)  =  6 + f(10)  =  6 + 9  =  15;

f(3)  =  5 + max(f(1), f(2))  =  5 + 4  =  9;

f(7)  =  5 + max(f(4), f(6))  =  5 + 17  =  22.

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

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

Ответ: 9.

При­ведём ре­ше­ние Юрия Кра­силь­ни­ко­ва на языке Python:

Спер­ва не­об­хо­ди­мо со­хра­нить со­дер­жи­мое таб­ли­цы excel в тек­сто­вом файле.

Уда­ля­ем из таб­ли­цы первую стро­ку с за­го­лов­ка­ми столб­цов. Перед со­хра­не­ни­ем можно раз­де­лить тре­тий стол­бец на от­дель­ные столб­цы с по­мо­щью функ­ции «Текст по столб­цам», но это не­обя­за­тель­но: про­грам­ма ра­бо­та­ет и в том, и в дру­гом слу­чае. Вы­би­ра­ем фор­мат со­хра­ня­е­мо­го файл в Текст CSV. В ка­че­стве раз­де­ли­те­ля полей можно ис­поль­зо­вать точку с за­пя­той или про­бел.

По­яс­не­ние к про­грам­ме.

В 3-⁠й стро­ке со­зда­ет­ся спи­сок lines, каж­дый эле­мент ко­то­ро­го  — это спи­сок чисел, со­дер­жа­щих­ся в со­от­вет­ству­ю­щей стро­ке тек­сто­во­го файла. Для уни­вер­саль­но­сти все точки с за­пя­той и двой­ные ка­выч­ки в тек­сто­вой стро­ке за­ме­ня­ют­ся на про­бе­лы. Для при­ве­ден­ной стро­ки со­от­вет­ству­ю­щий эле­мент спис­ка будет таким: [3, 5, 1, 2].

В 4-⁠й стро­ке из этого спис­ка со­зда­ет­ся сло­варь w. Ключ эле­мен­та сло­ва­ря  — это номер про­цес­са, а зна­че­ние  — спи­сок, со­сто­я­щий из вре­ме­ни вы­пол­не­ния про­цес­са и но­ме­ров про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс. Со­от­вет­ству­ю­щий эле­мент сло­ва­ря будет вы­гля­деть так: 3:[5, 1, 2].

В 5-⁠й стро­ке вы­чис­ля­ет­ся final  — время, через ко­то­рое за­вер­шит­ся вы­пол­не­ние всей со­во­куп­но­сти про­цес­сов. Это мак­си­мум из вре­ме­ни на­ча­ла каж­до­го про­цес­са из сло­ва­ря w плюс его про­дол­жи­тель­ность. (Если мы ре­ша­ем за­да­чу со стан­дарт­ным во­про­сом «Опре­де­ли­те ми­ни­маль­ное время, через ко­то­рое за­вер­шит­ся вы­пол­не­ние всей со­во­куп­но­сти про­цес­сов», то зна­че­ние final  — это ответ к такой за­да­че.)

В 6-⁠й стро­ке стро­ит­ся спи­сок kolp. Эле­мент kolp[0]  — это ко­ли­че­ство про­цес­сов, вы­пол­ня­е­мых в мо­мент вре­ме­ни 0, kolp[1]  — их ко­ли­че­ство в мо­мент 1 и так далее. Зна­че­ние range(final+1) га­ран­ти­ру­ет, что мы про­ве­дем рас­чет для всех мо­мен­тов вре­ме­ни, пока идет вы­пол­не­ние про­цес­сов.

В 7-⁠й стро­ке пе­ча­та­ет­ся ко­ли­че­ство эле­мен­тов спис­ка kolp со зна­че­ни­ем 3.

Функ­ция tstart(p) вы­чис­ля­ет время на­ча­ла про­цес­са с но­ме­ром p. Если про­цесс не­за­ви­си­мый (то есть эле­мент сло­ва­ря w[p][1]==0), то это время  — ноль. Иначе бе­рет­ся мак­си­маль­ное время за­вер­ше­ния для всех про­цес­сов, от ко­то­рых за­ви­сит дан­ный. Время за­вер­ше­ния про­цес­са с но­ме­ром i  — это время его на­ча­ла плюс его про­дол­жи­тель­ность (то есть tstart(i)+w[i][0]).

При­ведём ре­ше­ние Юрия Кра­силь­ни­ко­ва в Excel:

Разо­бьем спис­ки про­цес­сов в столб­це C на от­дель­ные числа с по­мо­щью функ­ции «Текст по столб­цам».

В столб­це E у нас будет время на­ча­ла со­от­вет­ству­ю­ще­го про­цес­са, в столб­це F  — время его за­вер­ше­ния, а в столб­цах G и H  — вре­ме­на за­вер­ше­ний про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс (но­ме­ра этих про­цес­сов ука­за­ны в столб­цах C и D).

Впи­шем в ячей­ку E2 фор­му­лу =МАКС(G2:H2), в ячей­ку F2  — фор­му­лу =E2+B2 и ско­пи­ру­ем эти фор­му­лы в стро­ки 3-13.

В ячей­ку G2 впи­шем фор­му­лу =ЕСЛИ(C2>0;ВПР(C2;$A$2:$F$13;6;0);"") и ско­пи­ру­ем её во все ячей­ки диа­па­зо­на G2:H13.

Те­перь опре­де­лим ко­ли­че­ство про­цес­сов, ко­то­рые вы­пол­ня­ют­ся в каж­дый мо­мент вре­ме­ни.

Для этого в ячей­ку A15 за­пи­шем 0, в ячей­ку A16  — 1 и так далее до 30 (можно за­не­сти в ячей­ку А16 фор­му­лу =A15+1 и раз­мно­жить её вниз по столб­цу).

В ячей­ку B15 за­пи­шем фор­му­лу =СЧЁТЕС­ЛИМН($E$2:$E$13;"<="&A15;$F$2:$F$13;">"&A15) и раз­мно­жим её вниз по столб­цу B.

Те­перь за­пи­шем в любую сво­бод­ную ячей­ку (на­при­мер, C15) фор­му­лу =СЧЁТЕСЛИ(B15:B45;3) и по­лу­чим ответ  — 9.