Stefan Palicki gr. I7X5S1

1. Opis problemu

Określona liczba typów procesorów wykonuje różne obliczenia z różną wydajnością. Ośrodek wykonuje projekt składający się z określonej liczby obliczeń każdego typu, jednak dysponuje ograniczoną liczbą procesorów każdego typu. Dokonać przydziału procesorów do danych obliczeń, tak aby czas wykonania projektu był jak najkrótszy.

1. Model matematyczny

   1. Cechy

P – zbiór numerów typów procesorów

L_p – liczba rodzajów procesorów

R_j – liczba posiadanych procesorów j-tego typu

O – zbiór numerów typów obliczeń

L_o – liczba rodzajów obliczeń

W_ij – liczba operacji i-tego typu na procesorze j-tego typu na sekundę

M_i – minimalna liczba obliczeń i-tego typu w projekcie

T – całkowity czas wykonania projektu

I_ij – liczba procesorów j-tego typu wykonujących obliczenia i-tego typu

$$\dot{\mathbf{X}}\mathbf{=}\begin{Bmatrix} \left\langle \mathbf{P,}\mathbf{2}^{\mathbf{N}} \right\rangle\mathbf{,}\left\langle \mathbf{L}_{\mathbf{p}}\mathbf{,N} \right\rangle\mathbf{,}\left\{ \left\langle \mathbf{R}_{\mathbf{j}}\mathbf{,N} \right\rangle \right\}_{\mathbf{j = 1}}^{\mathbf{L}_{\mathbf{p}}}\mathbf{,}\left\langle \mathbf{O,}\mathbf{2}^{\mathbf{N}} \right\rangle\mathbf{,} \\ \left\langle \mathbf{L}_{\mathbf{o}}\mathbf{,N} \right\rangle\mathbf{,}\left\{ \left\{ \left\langle \mathbf{W}_{\mathbf{\text{ij}}}\mathbf{,N} \right\rangle \right\}_{\mathbf{i = 1}}^{\mathbf{L}_{\mathbf{o}}} \right\}_{\mathbf{j = 1}}^{\mathbf{L}_{\mathbf{p}}}\mathbf{,}\left\{ \left\langle \mathbf{M}_{\mathbf{i}}\mathbf{,N} \right\rangle \right\}_{\mathbf{i = 1}}^{\mathbf{L}_{\mathbf{o}}}\mathbf{,} \\ \left\langle \mathbf{T,N} \right\rangle\mathbf{,}\left\{ \left\{ \left\langle \mathbf{I}_{\mathbf{\text{ij}}}\mathbf{,N} \right\rangle \right\}_{\mathbf{i = 1}}^{\mathbf{L}_{\mathbf{o}}} \right\}_{\mathbf{j = 1}}^{\mathbf{L}_{\mathbf{p}}} \\ \end{Bmatrix}$$

1. Związki

z₁ – moc zbioru numerów rodzajów procesorów

y₁ = ⟨P,L_p⟩

$$R_{1} = \left\{ \left\langle p,l_{p} \right\rangle \in 2^{N} \times N:\overset{}{p} = l_{p} \right\}$$

z₂ – moc zbioru numerów rodzajów obliczeń

y₂ = ⟨O,L_o⟩

$$R_{2} = \left\{ \left\langle o,l_{o} \right\rangle \in 2^{N} \times N:\overset{}{o} = l_{o} \right\}$$

z₃ – ograniczenie liczby procesorów

y₃ = ⟨{R_j}_j = 1^L_p,{{I_ij}_i = 1^L_o}_j = 1^L_p,L_o,L_p,P⟩

$$R_{3} = \begin{Bmatrix} \left\langle {\left\{ r_{j} \right\}_{j = 1}^{l_{p}},\left\{ \left\{ i_{\text{ij}} \right\}_{i = 1}^{l_{o}} \right\}_{j = 1}^{l_{p}},l_{p},l}_{o},p \right\rangle \in 2^{N} \times N^{2} \times N^{l_{p}} \times N^{l_{p}l_{o}}: \\ \bigwedge_{j \in p}^{}{r_{i} \geq \sum_{i = 1}^{l_{p}}i_{\text{ij}}} \\ \end{Bmatrix}$$

z₄ – całkowity czas wykonania projektu

y₄ = ⟨{{I_ij}_i = 1^L_o}_j = 1^L_p, {{W_ij}_i = 1^L_o}_j = 1^L_p, {M_i}_i = 1^L_o, L_o,L_p,T⟩

$$R_{4} = \begin{Bmatrix} \left\langle {\left\{ \left\{ i_{\text{ij}} \right\}_{i = 1}^{l_{o}} \right\}_{j = 1}^{l_{p}},\left\{ \left\{ w_{\text{ij}} \right\}_{i = 1}^{l_{o}} \right\}_{j = 1}^{l_{p}},\left\{ m_{i} \right\}_{i = 1}^{l_{o}},l}_{o},l_{p},t \right\rangle \in N^{3} \times N^{2l_{p}l_{o}} \times N^{l_{o}}: \\ t = \sum_{i = 1}^{l_{o}}\frac{m_{i}}{\sum_{i = 1}^{l_{p}}{w_{\text{ij}}*i_{\text{ij}}}} \\ \end{Bmatrix}$$

$$\dot{\mathbf{R}}\mathbf{=}\left\{ \left\langle \mathbf{z}_{\mathbf{1}}\mathbf{,}\mathbf{y}_{\mathbf{1}}\mathbf{,}\mathbf{R}_{\mathbf{1}} \right\rangle\mathbf{,}\left\langle \mathbf{z}_{\mathbf{2}}\mathbf{,}\mathbf{y}_{\mathbf{2}}\mathbf{,}\mathbf{R}_{\mathbf{2}} \right\rangle\mathbf{,}\left\langle \mathbf{z}_{\mathbf{3}}\mathbf{,}\mathbf{y}_{\mathbf{3}}\mathbf{,}\mathbf{R}_{\mathbf{3}} \right\rangle\mathbf{,}\left\langle \mathbf{z}_{\mathbf{4}}\mathbf{,}\mathbf{y}_{\mathbf{4}}\mathbf{,}\mathbf{R}_{\mathbf{4}} \right\rangle \right\}$$

1. Podział cech

   1. Dane

a=⟨P,L_p,O,L_o,{{W_ij}_i = 1^L_o}_j = 1^L_p,{R_j}_j = 1^L_p,{M_i}_i = 1^L_o⟩

1. Zmienne decyzyjne

x=⟨{{I_ij}_i = 1^L_o}_j = 1^L_p⟩

1. Wskaźniki

y = T

1. Analiza poziomu informacyjnego

Hgfghj.

1. Określenie zbiorów

   1. Poprawnych wartości danych

$$\mathbf{A =}\begin{Bmatrix} \left\langle P,L_{p},O,L_{o},\left\{ \left\{ W_{\text{ij}} \right\}_{i = 1}^{L_{o}} \right\}_{j = 1}^{L_{p}},\left\{ R_{j} \right\}_{j = 1}^{L_{p}},\left\{ M_{i} \right\}_{i = 1}^{L_{o}} \right\rangle\mathbf{\in}2^{2N} \times N^{2} \times N^{l_{p}l_{o}} \times N^{l_{p}} \times N^{l_{o}}: \\ \overset{}{P} = L_{p},\overset{}{O} = L_{o} \\ \end{Bmatrix}$$

1. Dopuszczalnych wartości zmiennych decyzyjnych

$$\mathbf{\Omega}\left( \mathbf{a} \right)\mathbf{=}\begin{Bmatrix} \left\{ \left\{ I_{\text{ij}} \right\}_{i = 1}^{L_{o}} \right\}_{j = 1}^{L_{p}} \in N^{l_{p}l_{o}}: \\ \bigwedge_{j \in P}^{}{R_{i} \geq \sum_{i = 1}^{L_{p}}I_{\text{ij}}} \\ \end{Bmatrix}$$

1. Możliwych wartości wskaźników

$$\mathbf{Y}\left( \mathbf{a,x} \right)\mathbf{=}\begin{Bmatrix} \mathbf{T \in N:} \\ T = \sum_{i = 1}^{L_{o}}\frac{M_{i}}{\sum_{i = 1}^{L_{p}}{W_{\text{ij}}*I_{\text{ij}}}} \\ \end{Bmatrix}$$

1. Definicja funkcji oceny osiągnięcia celu

$$\mathbf{E}_{\mathbf{a}}\left( \mathbf{y}^{\mathbf{*}} \right)\mathbf{=}\left\{ \begin{matrix} \mathbf{1,\ gdy\ }\mathbf{y}^{\mathbf{*}}\mathbf{=}\operatorname{}{\mathbf{f}\left( \mathbf{a,x} \right)} \\ \mathbf{0,\ w\ p.\ p.} \\ \end{matrix} \right.\ $$

$$\mathbf{f}\left( \mathbf{a,x} \right)\mathbf{= T =}\sum_{\mathbf{i = 1}}^{\mathbf{L}_{\mathbf{o}}}\frac{\mathbf{M}_{\mathbf{i}}}{\sum_{\mathbf{i = 1}}^{\mathbf{L}_{\mathbf{p}}}{\mathbf{W}_{\mathbf{\text{ij}}}\mathbf{*}\mathbf{I}_{\mathbf{\text{ij}}}}}$$

1. Zadanie optymalizacyjne

Dla danych a ∈ A wyznaczyć takie x^*∈Ω(a), aby

$$\bigwedge_{\mathbf{y \in Y}\left( \mathbf{a,x} \right)}^{}{\mathbf{E}_{\mathbf{a}}\left( \mathbf{x}^{\mathbf{*}} \right)\mathbf{= 1}}$$