Razvrščanje poslov na stroju

Iz MaFiRaWiki

UVOD:
\bullet n poslov
\bullet za i-ti posel poznamo vrednost vi in čas izgotovitve ti
\bullet na voljo imamo le en stroj
\bullet za vsak posel potrebuje stroj enoto časa
NALOGA:
Iščemo podmnožico J \subseteq \{ 1, 2, \ldots, n \} poslov in vrstni red njihovega izvajanja , ki je pravočasno končano in maksimira vrednost \sum_{j \in J}v_{j} končanih poslov.
OPOMBA:
Množica J je dopustna, če jo je možno končati v vsaj enem vrstnem redu.
Ali moramo prevriti vsa možna zaporedja v J?
Ne, zadošča da preverimo "požrešno" zaporedje.
"Požrešno" zaporedje poslov iz J=j_{1}, j_{2}, \ldots, j_{k} je permutacija (i_{1}, i_{2}, \ldots, i_{k}) teh poslov za katero je t_{i_{1}} \leq t_{i_{2}} \leq \ldots \leq t_{i_{k}}.
Množica poslov iz J je torej dopustna natanko tedaj, ko je "požrešno" zaporedje teh poslov dopustno.
IDEJA:
Optimalno množico I dobimo tako (na začetku je J= \emptyset, da ji v vsakem koraku dodamo posel z največjo vrednostjo med preostalimi posli, pri čemer mora I ostati dopustna.
ALGORITEM
Vhod: Množica poslov 1,2,...n in vi,ti za vsak i.
Izhod: Množica J poslov, ki je dopustna in ima maksimalno vrednost. 

(p1, p2, ..., pn)=UrediPoslePoVelikosti;
J=0;V=0;
for k=1 to n do
    if dopustna (J unija {pk}) then
       J=J unija {pk};
       V=V+V*pk
    end if
end for
Vzpostavljeno iz "http://wiki.fmf.uni-lj.si/wiki/Razvr%C5%A1%C4%8Danje_poslov_na_stroju"
Osebna orodja