Test 3

Jednalo se o podobné zadání jako varianta B z roku 2012. Navíc byla zadána matice

M = 1 0 1 0
    0 1 0 0
    1 0 1 0
    0 0 0 1

Kde 1 značí: Úloha i musí být vykonávána na stejném procesoru jako úloha j, i je řádkový a j je sloupcový index.

Řešení: Test vstupních podmínek. Matice M musí být symetrická, např. pokud úloha 1 musí být vykonávána na stejném procesoru jako úloha 3, tak úloha 3 musí být vykonávána na stejném procesoru jako úloha 1. Na diagonále musí být 1, samostatná úloha se vykonává na stejném (jednom) procesoru. Preempce nebyla povolena. Vektor proměnných obsahuje xij - x11 x21 x31 x41 x12 x22 x32 x42 Cmax, kdy i je číslo úlohy, j je procesor, více viz popis úlohy níže.

Matice M nám říká, že úloha 1 má běžet na stejném procesoru jako úloha 3. Tedy nemůže se stát, že pokud je úloha 1 rozvržena na procesor 1 (x11), tak bude úloha 3 rozvržena na procesor 2 (x32). Součet těchto proměnných musí být 1. Analogicky, nemůže se stát, že pokud je úloha 1 rozvržena na procesor 2 (x12), tak bude úloha 3 rozvržena na procesor 1 (x31). Součet těchto proměnných musí být opět 1. Matici A tedy rozšíříme o řádky pro omezení z matice M:

 A = [p , 0 0 0 0, -1;
     0 0 0 0, p , -1;
     1 0 0 0, 1 0 0 0,0;
     0 1 0 0, 0 1 0 0,0;
     0 0 1 0, 0 0 1 0,0;
     0 0 0 1, 0 0 0 1,0;  
     %pridané řádky pro matici M
     1 0 0 0, 0 0 1 0,0;
     0 0 1 0, 1 0 0 0,0];

Je třeba i upravit vektor b, rozšířit ho o dvě jedničky

b = [0; 0; ones(n,1); 1;1];

a porovnávací podmínky

ctype = ['L'; 'L'; repmat('E',n,1);'E';'E'];

Pokud bych něco opomenul, pište do diskuze, případně upravte s poznámkou.

P.S. Proč mne řešení napadnou vždy až v klidu při kávičce a příjemné hudbě, místo při psaní testu .

Par hintu na prvni pokuk:

• matice A bude obsahovat tenhle vzor: Apartial = [ 1 0 0 0 0 0 0 1; 1 1 0 0 0 0 0 0; 0 1 1 0 0 0 0 0; … ]; kazde cislo v radku je jedna 3hodinovka, vyznam je stejny jako v domacim ukolu s telefonim operatorem
• take se nam tam vyskytne -[bmin, bmax]';
• tipuju to na neco jako minimalizace pres vsechna x (tedy: c=ones(length(A),1)) pro matici A = [ Apartial -bmin'; -Apartial bmax'];
• vektor x obsahuje pocet sluzeb zacinajicich v te ktere hodine

Tim konci myslenkove pochody a prichazi vecerni odpocinek =D Je to jen tip reseni na prvni pohled. Melo by se stacit podivat na domacak s Telefonnim operatorem a brat jednu 3hodinovku jako 1h.

Jednalo se o planovaci ulohu ctyr uloh na dvou procesorech.

n = 4;          % pocet ulon (delka nasledujiciho vektoru)
p = [11 7 4 8]; % doba trvani jednotlivych uloh na procesorech 
m = 2;          % pocet procesoru

Meli jsme vytvorit plan pomoci ILP (prakticky 3. domaci uloha). Jednotlive parametry pro funkci ilinprog bylo mozne zapsat primo a nebylo potreba je generovat dynamicky podle velikosti vstupnich parametru.

Promenne ILP jsou

• - tedy mame m*n booleovskych promennych, ktere znaci, ze uloha i se vykonava na procesoru j
• - doba trvani cele prace (soucet dob trvani uloh na nejvytizenejsim procesoru), tuto promennou minimalizujeme.

Omezujici podminky linearniho programu jsou:

Prvni podminka rika, ze Cmax je vetsi nez soucet trvani uloh na kteremkoli procesoru. Druha podminka rika, ze se kazda uloha vykonava prave na jednom procesoru.

Soucasti reseni je vypis jake ulohy se kde maji provadet, jaky je vysledny vektor a hodnota kriteria a popis toho co je ve vektory vartype jako soucast komentare v kodu.

Posilam sem komplet reseni i s vysvetlivkami. Uz je po testu, tak verim, ze nikdo nebude mit moznost ho zneuzit. Pokud budete chtit tenhle kod dale sirit, tak prosim jedine pres link na tuhle dokuwiki.

clear all;

n = 4; % pocet uloh

p = [11 5 3 8]; % doby trvani uloh
m = 2;          % pocet procesoru
cmax = 0;       % vysledna delka rozvrhu (tu minimalizujeme)

% snese = minimalisation (see help ilinprog)

sense = 1;

% Prvni dva radky jsou soucet uloh na prvnim a druhem procesoru

% Lower-or-equal CMAX
% Nasledujicich n radku udava, ze kazda uloha se ma vykonat prave jednou na
% jednom z procesoru. Soucet jednicek pro kazdou ulohu bude Equal jedne.
ctype = ['L'; 'L'; repmat('E',n,1)];

% creation of A-matrix

A = [   p   , 0 0 0 0, -1; ...
     0 0 0 0,    p   , -1; ...
     1 0 0 0, 1 0 0 0,  0; ...
     0 1 0 0, 0 1 0 0,  0; ...
     0 0 1 0, 0 0 1 0,  0; ...
     0 0 0 1, 0 0 0 1,  0];
  
% rozdil na prvnich dvou radcich musi byt nula
% soucet na zbylych radcich se rovna jedne
b = [0; 0; ones(n,1)];

% Prvnich M*N cisel vektoru b jsou boolean hodnoty pro tasky x(1:n) na

% procesorech 1:m. Proto jsou celociselne. Matice A se na prvni pohled
% nejevi totalne unimodularni, proto zde nelze pouzit realne promenne. 
%vartype = [repmat('I', m*n+1, 1)];
%
% Predpokladam, ze aby se dala pouzit simplexova metoda, nebo jiny
% algoritmus pro necelociselne LP, je potreba aby vsechny promenne byly 
% realne, ne celociselne. Nasledujici radek proto parvdepodobne nicemu 
% nepomuze. Nicmene, kdybychom povolili necelociselne doby trvani 
% jednotlivych uloh, bylo by potreba nastavit typy prave takhle: 
vartype = [repmat('I', m*n, 1); 'C'];

% minimalizujeme pouze cmax

c = [zeros(m*n,1); 1];

% cmax bude maximalne soucet vsech casu, ostatni promenne budou maximalne

% jedna
lb = [zeros(m*n, 1);   0   ]; % dolni meze
ub = [ones(m*n, 1) ; sum(p)]; % horni meze

%Parametry optimalizace

schoptions=schoptionsset('ilpSolver','glpk','solverVerbosity',2);

%spusteni optimalizace z TORSCHE

[xmin,fmin,status,extra] = ...
    ilinprog(schoptions,sense,c,A,b,ctype,lb,ub,vartype);

fprintf('vektor kriteria: ');

xmin'

fprintf('hodnota kriteria (doba trvani): %d\n', fmin);

i=(1:n);

fprintf(strcat('# na prvnim procesoru pobezi ulohy: ',repmat(' %d',1,sum(xmin(1:n))), '\n'),  i(boolean(xmin(1:n)')));
fprintf(strcat('# na druhem procesoru pobezi ulohy: ',repmat(' %d',1,sum(xmin(n+1:n+n))), '\n'),  i(boolean(xmin(n+1:n+n)')));  

n(5) dam na sachovnici. (n queens problem)
zjednodusena uloha n vezi, z te pak dodelat uhlopricky pro damy. 
vychazelo se z ukolu na sudoku

problem batohu pomoci ILP 
nejaka omezeni, ktere veci nejdou vzit spolu (prosim doplnte)