Úkol 6

function [s, Cmax] = bratleyAlg(p, r, d)
clear global;
k = [];

[ss,Cmaxx] = bratleyAlg_(p,r,d,0,1:length(p),k);
s = ss;
Cmax = Cmaxx;
end

function [poradi, optimum] = bratleyAlg_(p, r, d, c, task_list, s)

global Cmax_;
global s_;
%Initialize s, Cmax and estimate UB if it is empty (1st function call)
    
%Cmax = c;

%Condition 0
if (isempty(p) || isempty(r) || isempty(d))
    disp('we are done');
    if(isempty(Cmax_))
     Cmax_ = c;
     s_ = s;
    else
      if(c < Cmax_)
         Cmax_ = c;
         s_ = s;
      end
    end
    return %We are done
end

UB = max(d);

%Condition 1
estimated_deadlines = max(c, r) + p;
if 0 ~= (sum(estimated_deadlines > d))
    return          %This branching does not lead to feasible solution
end

%Condition 2
LB = max(min(r), c) + sum(p);
if LB > UB
    return          %This branching does not lead to feasible solution
end

%Branch each node to the appropriate number of other nodes
for i = 1:length(p)
    %Calculate c    
    c_upravene = max(c, r(i)) + p(i);
    %If only one job remains
    %OK that's good
        
    %If branching is still needed
    s_upravene = s; s_upravene(end+1) = task_list(i);
    %Solve subproblem by recursive call with modified inputs (e.g with use of the length of the partial solution)
    p_upravene = p;p_upravene(i)=[];
    r_upravene = r;r_upravene(i)=[];
    d_upravene = d;d_upravene(i)=[];
    task_list_upravene = task_list;task_list_upravene(i)=[];
    %s = bratleyAlg(p_upravene, r_upravene, d_upravene, c_upravene, ts_index, n);           
    bratleyAlg_(p_upravene, r_upravene, d_upravene, c_upravene, task_list_upravene,s_upravene);            
end
optimum = Cmax_;
poradi = s_;
end

Poznámka: Výše uvedený kód nebere v potaz situaci, kdy c < = min(ri), tedy sitauci, kdy již vytvořený rozvrh je optimální a daný uzel lze považovat za nový kořen. Pokud někdo umíte u rekurzivní verze „odstranit“ ostatní již existující zanoření, doplňte ho prosím. U iterativní verze to není problém.

Informace ohledně UB. V materiálech pro cvičení je nejasné, zda UB se počítá pouze jednou na začátku, či je to maximum z dosud nerozvrhnutých úloh. Na přednášce nebyl přednášející schopen říci více detailů, neboť přesně nezná materiály ze cvičení. Podle cvičícího je to možné stanovit jak na začátku, tak dynamicky v běhu algoritmu. Nastavování UB pouze jednou na začátku by bylo nevýhodné v situaci, kdy existuje tento set úloh r = [0 1 1 1 1 1 ….] p= [1 5 5 5 5 5 ….] deadlines = [10000 10 20 30 40 ….]. Dle tohoto rozvrhu by stanovení UB = deadline T1, pouze na začátku, nepřineslo kýžený efekt na osekání stav. prostoru.