Çoxprosessorlu Planlaşdırma#371

Çoxprosessorlu Planlaşdırma

2 saniyə

64 meqabayt

Çox çətin

Çoxprosessorlu bir maşında iki tətbiq işləyir. Hər bir tətbiq $i$ ( $i = 1, 2$ i = 1, 2) $N$ prosedurdan ibarətdir; prosedurlar $1$ -dən $N$ -ə qədər nömrələnmişdir və ardıcıllıqla ( $1, \dots, N$ 1, \ldots, N) icra olunmalıdır. Bir prosedur $(i, j)$ cütü ilə tanıdılır, burada $i = 1, 2$ i = 1, 2 tətbiqi müəyyən edir, $1 \leq j \leq N$ 1 \leq j \leq N isə tətbiq $i$ daxilində prosedurun indeksidir. Prosedur $(i, j)$ yalnız $P (i, j)$ P(i, j) prosessorunda icra oluna bilər və icrası $D (i, j)$ D(i, j) saniyə çəkir. Hər iki tətbiqin prosedurlarını elə planlaşdırmaq istəyirik ki, sonuncu prosedur (istənilən tətbiq üzrə) bitdikdə olan an (yəni makespan) minimum olsun. Hər iki tətbiq planlaşdırmaya $0$ vaxtından başlayaraq hazırdır.

Planlaşdırma aşağıdakı qaydalara tabe olmalıdır:

Hər hansı bir prosedur $(i, j)$ $P (i, j)$ P(i, j) prosessorunda icra olunmağa başladıqdan sonra onu dayandırmaq olmaz, yalnız bitdikdən sonra dayanır.
Eyni prosessorda eyni anda bir neçə prosedur icra oluna bilməz, amma müxtəlif prosessorlarda prosedurlar paralel icra oluna bilər.
$(i, j)$ prosedurunun icrasına ( $2 \leq j \leq N$ 2 \leq j \leq N) yalnız $(i, j - 1)$ (i, j-1) bitən anda və ya ondan sonra başlamaq olar.
Əgər bir prosedur $t m$ vaxtında başlayırsa, $t m + D (i, j)$ tm + D(i, j) vaxtında bitir.

Verilmiş prosedurlar üçün hər iki tətbiq üzrə minimum makespan-i tapmaq üçün proqram yazın.

Giriş

İlk sətirdə $T$ — testlərin sayı verilir.

Hər bir test üçün ilk sətirdə $N$ ( $1 \leq N \leq 300$ 1 \leq N \leq 300) — hər bir tətbiqdəki prosedurların sayı verilir. Sonra birinci tətbiq üçün $N$ sətir gəlir; bu sətirlərin $j$ -ci hər birində iki tam ədəd: $P (1, j)$ P(1, j) və $D (1, j)$ D(1, j), bir boşluqla ayrılmış halda verilir. Növbəti $N$ sətir isə eyni formatda ikinci tətbiqi təsvir edir: $j$ -ci sətirdə $P (2, j)$ P(2, j) və $D (2, j)$ D(2, j) verilir. $1 \leq P (i, j) \leq 10$ 1 \leq P(i, j) \leq 10, $1 \leq D (i, j) \leq 15000$ 1 \leq D(i, j) \leq 15000 ( $i = 1, 2$ i = 1, 2; $1 \leq j \leq N$ 1 \leq j \leq N).

Qeyd: Ola bilər ki, $P (i, j) = P (k, l)$ P(i, j) = P(k, l), bu halda $(i, j)$ və $(k, l)$ (k, l) prosedurlarının vaxtı üst-üstə düşə bilməz. Əgər $i = k$ i = k olarsa, bu problem deyil, çünki onlar, eyni tətbiqdə olduqlarından ardıcıl icra olunmalıdır.

Çıxış

Çıxışda dəqiq $T$ sətir olmalıdır, hər sətirdə müvafiq test üçün minimum makespan olacaq bir ədəd yazılmalıdır. Cavablar daxil olan ardıcıllığa uyğun olmalıdır (yəni $i$ -ci sətir $i$ -ci test üçün cavab olacaq).

Nümunələr

Nümunə 1