\documentclass[10pt,b5paper]{book}
\usepackage{InfAlgMaj28}
\usepackage[magyar]{babel}
\usepackage{hhline}
\usepackage{color}
\usepackage{mycolortbl}
\usepackage{graphics}
\usepackage{enumerate}
\usepackage{fancybox}
%\usepackage{txfonts}
%\renewcommand{\sfdefault}{ufu}

\addtocounter{chapter}{0}
\setcounter{section}{0}
\setcounter{page}{1}
\setcounter{tocdepth}{3}

\hyphenation{prog-ram prog-ra-mok}

\makeindex
\sloppy

\newcommand*{\mc}[3]{\multicolumn{#1}{#2}{#3}}
\newcommand*{\m}[1]{\textit{#1}}
\newcommand*{\grn}[2]{\mc{#1}{>{\columncolor[gray]{.88}[.95\tabcolsep]}c|}{#2}}
\newcommand*{\gr}[1]{\mc{1}{>{\columncolor[gray]{.88}[.95\tabcolsep]}c|}{#1}}
\newcommand*{\fgr}[1]{\mc{1}{|>{\columncolor[gray]{.88}[.95\tabcolsep]}c|}{#1}}
\newcommand*{\T}{\textit{T}}
\renewcommand*{\t}{{\bf t}}


\renewcommand*{\P}{{\bf P}}
%\newcommand*{\R}{{\bf R}}
\renewcommand*{\r}{{\bf r}}
\renewcommand*{\b}{{\bf b}}
\renewcommand*{\d}{{\bf d}}
\renewcommand*{\t}{{\bf t}}
\newcommand*{\p}{{\bf p}}
%\newcommand*{\T}{{\bf T}}
\newcommand*{\acsa}{\Leftrightarrow}
\newcommand*{\akkor}{\Rightarrow}
\newcommand*{\ha}{\Leftarrow}
\newcommand*{\no}{\!\!\nearrow}
\newcommand*{\csokk}{\!\!\searrow}
\newcommand*{\maxim}{\!\uparrow}
\newcommand*{\minim}{\!\downarrow}
\newcommand*{\Fmax}{\ensuremath{F_\mathrm{max}}}
\newcommand*{\Fmin}{\ensuremath{F_\mathrm{min}}}
\newcommand*{\Fav}{\ensuremath{F_\mathrm{av}}}
\newcommand*{\Wmax}{\ensuremath{W_\mathrm{max}}}
\newcommand*{\Wmin}{\ensuremath{W_\mathrm{min}}}
\newcommand*{\Wav}{\ensuremath{W_\mathrm{av}}}
\newcommand*{\Nmax}{\ensuremath{N_\mathrm{max}}}
\newcommand*{\Nmin}{\ensuremath{N_\mathrm{min}}}
\newcommand*{\Nav}{\ensuremath{N_\mathrm{av}}}
\newcommand*{\Lmax}{\ensuremath{L_\mathrm{max}}}
\newcommand*{\Lmin}{\ensuremath{L_\mathrm{min}}}
\newcommand*{\Lav}{\ensuremath{L_\mathrm{av}}}
\newcommand*{\Emax}{\ensuremath{E_\mathrm{max}}}
\newcommand*{\Emin}{\ensuremath{E_\mathrm{min}}}
\newcommand*{\Eav}{\ensuremath{E_\mathrm{av}}}%%
\newcommand*{\Amax}{\ensuremath{A_\mathrm{max}}}
\newcommand*{\Amin}{\ensuremath{A_\mathrm{min}}}
\newcommand*{\Aav}{\ensuremath{A_\mathrm{av}}}
\renewcommand*{\d}[1]{\ensuremath{\mathrm{d}#1}}
\newcommand*{\dgr}[1]{\mc{1}{>{\columncolor[gray]{.75}[.95\tabcolsep]}c|}{#1}}
\newcommand*{\ind}[1]{\ensuremath{C(\mathrm{#1})}}
\newcommand*{\lev}[1]{\ensuremath{L(\mathrm{#1})}}

\begin{document}

\begin{center}
\vspace{5mm}
\Large
\textbf{PROCESSZORÜTEMEZÉS}

\vspace{5cm}
\large
\textbf{Iványi Antal}

\vspace{8cm}
\textbf{Budapest, 2011. március 31.}
\end{center}

\tableofcontents

\normalsize
\chapter{A determinisztikus ütemezés alapfogalmai}
\section{Bevezetés}
A termel\'es k\"ul\"onb\"oz\H o ter\"uletein gyakran jelentkezik a k\"ovetkez\H o feladat: adott
munk\'akat kell elv\'egezni adott eszk\"oz\"ok felhaszn\'al\'as\'aval, adott korl\'atoz\'o
felt\'etelek betart\'asa mellett, adott \'ertelemben optimumra t\"orekedve. Az ilyen
t\'\i pus\'u feladatok jelent\H os\'ege a nagy \'ert\'ek\H u termel\H oeszk\"oz\"ok, bonyolult termel\'esi
folyamatok terjed\'es\'evel egy\"utt n\H o. Ezen feladatk\"or kutat\'asa nagy lend\"uletet
kapott a sz\'am\'\i t\'og\'epek elterjed\'es\'evel, mivel a gyors m\H uveletv\'egz\'esi lehet\H os\'eg
kisz\'eles\'\i tette a re\'alis id\H o alatt megoldhat\'o feladatok k\"or\'et.

A t\'emak\"or fontoss\'ag\'at mutatja, hogy az \"osszegy\H ult ismeretek egy r\'esze
{\sl \"utemez\'es elm\'elet} (scheduling theory) n\'even a sz\'am\'\i t\'astudom\'any \"on\'all\'o
\'ag\'av\'a fejl\H od\"ott. Az oper\'aci\'os rendszerekkel kapcsolatos, tipikus \"utemez\'esi
feladat: k\"otegelt programfeldolgoz\'as eset\'en az adott perif\'eri\'akat adott ideig
haszn\'al\'o, egym\'ast\'ol f\"uggetlen programokb\'ol \'all\'o k\"oteg minim\'alis id\H o alatt val\'o
futtat\'asa adott konfigur\'aci\'oj\'u sz\'am\'\i t\'og\'epen. M\'asik tipikus feladat egym\'ashoz
adott m\'odon kapcsol\'od\'o alprogramokb\'ol \'all\'o program futtat\'asa egyprocesszoros
sz\'am\'\i t\'og\'epen vagy t\"obb processzort tartalmaz\'o h\'al\'ozatban.

Ebben a jegyzetben az elv\'egzend\H o munk\'akat (p\'eld\'aul lefuttatand\'o programokat)
{\sl taszkoknak} vagy {\sl feladatoknak}\footnote{Az angol nyelv\H u szakirodalom
a {\sl task} sz\'ot haszn\'alja.},  a rendelkez\'esre \'all\'o eszk\"oz\"oket (p\'eld\'aul
processzorokat, perif\'eri\'akat) {\sl er\H oforr\'asoknak} fogjuk nevezni.

Ha a feladatok \'es er\H oforr\'asok jellemz\H o adatai r\"ogz\'\i tett (rendszerint el\H ore
ismert) \'ert\'ekek, akkor {\sl determinisztikus \"utemez\'esr\H ol} besz\'el\"unk. A
nemdeterminisztikus \"utemez\'esben gyakori, hogy a nem r\"ogz\'\i tett param\'eterek
eloszl\'asf\"uggv\'enyeikkel adottak. Ilyenkor a feladatok v\'egrehajt\'as\'at jellemz\H o
mennyis\'eg v\'arhat\'o \'ert\'ek\'enek optimaliz\'al\'asa a tipikus c\'el.

Ebben a jegyzetben csak a determinisztikus \"utemez\'essel foglalkozunk. El\H osz\"or
\"osszefoglaljuk az alapfogalmakat, alapvet\H o ismereteket (1.\ fejezet), majd a
legegyszer\H ubb egyprocesszoros eredm\'enyeket ismertetj\"uk (2.\ fejezet). Ezut\'an a
maxim\'alis befejez\'esi id\H o \'es az \'atlagos befejez\'esi id\H o optimaliz\'al\'as\'aval
foglalkozunk (3.\ fejezet). K\"ul\"on r\'eszben foglalkozunk a k\"ul\"onb\"oz\H o \"utemez\'esi
algoritmusok \"osszehasonl\'\i t\'as\'aval (4.\ fejezet).

\section{\"Utemez\'esi probl\'ema}
A $\pi=(\rho,\tau,\mu)$ \"utemez\'esi probl\'ema egy h\'armas, melynek elemei a
$\rho$ er\H oforr\'asrendszer, a $\tau$ taszkrendszer \'es a $\mu$
teljes\'\i tm\'enym\'ert\'ek.

\subsection{Er\H oforr\'asrendszer}
A taszkok egy r\'esz\'enek v\'egrehajt\'as\'ahoz egyf\'ele er\H oforr\'as elegend\H o. Ezeket az
er\H oforr\'asokat {\sl processzoroknak} nevezz\"uk: $m$-mel jel\"olj\"uk a processzorok
sz\'am\'at, $\P=\{P_1,\dots,P_m\}$-mel pedig a processzorok halmaz\'at, illetve az
egyes processzorokat.

Ha a $P_i$ \'es $P_j \in \P$ processzorokon v\'egrehajthat\'o feladatok halmazai
k\"ul\"onb\"oz\H oek, akkor azt mondjuk, hogy $P_i$ \'es $P_j$ {\sl k\"ul\"onb\"oz\H o}
processzorok. Ha k\'et processzoron ugyanazok a taszkok hajthat\'ok v\'egre, de a
v\'egrehajt\'asi id\H ok nem minden taszkra azonosak, akkor {\sl k\"ul\"onb\"oz\H o sebess\'eg\H u}
processzorokr\'ol besz\'el\"unk. Ha k\'et processzoron ugyanazok a taszkok hajthat\'ok
v\'egre, \'es a v\'egrehajt\'asi id\H ok is megegyeznek, akkor a processzorok
{\sl azonosak}.

\'Altal\'anos esetben a processzorokon k\'\i v\"ul tov\'abbi, \'ugynevezett {\sl kieg\'esz\'\i t\H o
er\H oforr\'asokra} is sz\"uks\'eg van. Ezek t\'\i pusainak sz\'am\'at jel\"olj\"uk $s$-sel, a
t\'\i pusok halmaz\'at, illetve az egyes t\'\i pusokat $\R=\{R_1,\dots,R_s\}$-sel,
tov\'abb\'a jel\"olje az $\r=(r_1,\dots,r_s)$ vektor az egyes kieg\'esz\'\i t\H o
er\H oforr\'as t\'\i pusokb\'ol rendelkez\'esre \'all\'o mennyis\'egeket.

A $\rho=(\P,\R,\r)$ rendezett h\'armast nevezz\"uk {\sl er\H oforr\'asrendszernek}.

\subsection{Taszkrendszer}
A taszkok legfontosabb tulajdons\'agai rendszerint le\'\i rhat\'ok a k\"ovetkez\H o jel\"ol\'esek
seg\'\i ts\'eg\'evel. Adott $\rho=(\P,\R,\r)$ er\H oforr\'asrendszerre vonatkoz\'o
taszkrendszer egy $\tau=(\T,<,[t_{ij}],[r_{ik}],\b,\d,\p)$ hetes, ahol
\begin{enumerate}[{\shadowbox{\arabic{enumi}.}}]
\item $\T=\{T_1,\dots,T_n\}$ a v\'egrehajtand\'o taszkok halmaza,

\item $<$ egy a $\T$ halmazon \'ertelmezett tranzit\'\i v, irreflex\'\i v, aszimmetrikus
bin\'aris rel\'aci\'o ($< \; \subseteq \T\times\T$). \\
Ha $T_i,T_j \in \T$, akkor $T_i<T_j$ azt jelenti, hogy $T_i$ v\'egrehajt\'as\'at be
kell fejezni, miel\H ott $T_j$ v\'egrehajt\'as\'at elkezden\'enk. Ilyenkor azt mondjuk,
hogy $T_i$ megel\H ozi $T_j$-t. $<$-t a taszkrendszer {\sl megel\H oz\'esi rel\'aci\'oj\'anak}
h\'\i vjuk. \\
Ha sem $T_i<T_j$, sem $T_j<T_i$ nem teljes\"ul, akkor azt mondjuk, hogy
$T_i$ \'es $T_j$ f\"uggetlenek egym\'ast\'ol. Ha egy adott id\H opontban minden olyan $T_k$
feladatot v\'egrehajtottunk, amelyre $T_k<T_i$, \'es a $T_i$ v\'egrehajt\'as\'ahoz
sz\"uks\'eges er\H oforr\'asok rendelkez\'esre \'allnak, akkor $T_i$ az adott id\H opontban
{\sl v\'egrehajthat\'o} (v\'egrehajt\'asa megkezdhet\H o). A megel\H oz\'esi rel\'aci\'o gyakran
el\H ofordul\'o p\'eld\'ai: l\'anc, fa \'es f\"uggetlen taszkok.

\item $[t_{ij}]$ a {\sl v\'egrehajt\'asi id\H ok} m\'atrixa: $t_{ij} \ (1 \le i \le n, \
1 \le j \le m)$ azt az id\H ot jelenti, amely alatt $T_i$ v\'egrehajthat\'o $P_j$-n.
Annak szok\'asos jel\"ol\'ese, hogy $T_i$ nem hajthat\'o v\'egre $P_j$-n:
$t_{ij}=\infty$. 
\'Altal\'aban feltessz\"uk, hogy a m\'atrix minden eleme pozit\'\i v (a taszkok
v\'egrehajt\'as\'ahoz minden processzoron id\H ore van sz\"uks\'eg), \'es a m\'atrix minden
sor\'aban van v\'eges \'ert\'ek (minden taszk legal\'abb egy processzoron v\'egrehajthat\'o).
Ha a processzorok azonosak, akkor $t_{i1}=t_{i2}=\dots=t_{im} \ 
(i=1,2,\dots,n)$. Ilyenkor $T_i$ v\'egrehajt\'asi idej\'et egyszer\H uen $t_i$-vel
jel\"olj\"uk (\'es v\'egrehajt\'asi id\H ok $[t_{ij}]$ m\'atrixa helyett v\'egrehajt\'asi id\H ok
$\t$ vektora szerepel $\tau$-ban).

\item $[r_{ik}]$ a {\sl kieg\'esz\'\i t\H o er\H oforr\'asokra vonatkoz\'o ig\'enyek} m\'atrixa: 
$r_{ik} \ (1 \le i \le n, \ 1 \le k \le s)$ azt adja meg, hogy a $T_i$ taszk
v\'egrehajt\'as\'ahoz az $R_k$ er\H oforr\'ast\'\i pusb\'ol h\'any egys\'egre van sz\"uks\'eg (a
v\'egrehajt\'as eg\'esz id\H otartam\'ara). \'Altal\'aban feltessz\"uk, hogy
$r_{ik} \le r_k \ (1 \le i \le n,\ 1 \le k \le s)$ teljes\"ul, azaz a taszkok
er\H oforr\'asig\'enye kiel\'eg\'\i thet\H o. Ha $s=0$, akkor ezzel a m\'atrixszal nem kell
foglalkozni.

\item $\b=(b_1,\dots,b_n)$ a {\sl bel\'ep\'esi id\H oponto}k vektora: $b_i$ jelenti azt
az id\H opontot, amely el\H ott $T_i$ v\'egrehajt\'asa nem kezdhet\H o el.

\item $\mathbf{d}=(d_1,\dots,d_n)$ a {\sl hat\'arid\H ok} vektora: $d_i$ jelenti azt az
id\H opontot, ameddig a $T_i$ taszk v\'egrehajt\'as\'at be kell fejezni. A hat\'arid\H ok
lehetnek {\sl szigor\'uak,} illetve {\sl aj\'anlottak}. Szigor\'u hat\'arid\H o eset\'en csak
a taszkok olyan v\'egrehajt\'asa fogadhat\'o el, amely biztos\'\i tja a hat\'arid\H ok
betart\'as\'at, m\'\i g az aj\'anlott hat\'arid\H ok t\'ull\'ep\'ese megengedett (b\'ar a t\'ull\'ep\'esnek
h\'atr\'anyos k\"ovetkezm\'enyei lehetnek).

\item $\p=(p_1,\dots,p_n)$ a {\sl s\'ulyok} vektora: $p_i$ a $T_i$ taszk
fontoss\'ag\'at jellemzi (a teljes\'\i tm\'enym\'ert\'ekek \'ert\'ek\'en kereszt\"ul befoly\'asolja a
taszkok v\'egrehajt\'as\'at).
\end{enumerate}

\subsection{Teljes\'\i tm\'enym\'ert\'ekek}
A taszkok jellemz\H oit k\'et csoportba oszthatjuk: az egyik csoportba tartoz\'ok (mint
$b_i, d_i, p_i, t_{ij}, r_{ik}$) az \"utemez\'es elk\'esz\'\i t\'esekor ismert, \'alland\'o
\'ert\'ekek --- a m\'asik csoportba tartoz\'ok pedig az \"utemez\'es elk\'esz\'\i t\'ese sor\'an
kapj\'ak meg az \'ert\'ek\"uket (att\'ol f\"ugg az \'ert\'ek\"uk, hogy milyen \"utemez\'est
v\'alasztunk): \\
Az \"utemez\'est $S$-sel jel\"olve vezess\"uk be a k\"ovetkez\H o jel\"ol\'eseket: \\
\begin{center}
\begin{tabular}[c]{| l | @{\ \ a $T_i$ taszk } l |}
\hline
$s_i(S)$ & {\sl kezd\'esi id\H opontja} \\
$f_i(S)$ & {\sl befejez\'esi id\H opontja} \\
$w_i(S)=s_i(S)-b_i$ & {\sl v\'arakoz\'asi ideje} \\
$n_i(S)=f_i(S)-d_i$ & {\sl pontatlans\'aga} \\
$l_i(S)=\max(n_i(S),0)$ & {\sl k\'es\'ese} \\
\hline
\end{tabular}
\end{center}

\noindent
Ezen \"utemez\'est\H ol f\"ugg\H o taszkjellemz\H ok seg\'\i ts\'eg\'evel fogjuk megadni a
$\mu=\{\Fmax$, \Fmin, \Fav,
      \Wmax, \Wmin, \Wav,
      \Nmax, \Nmin, \Nav,
      \Lmax, \Lmin, \Lav,
      \Emax, \Emin, \Eav,
      \Amax, \Amin, $\Aav\}$
teljes\'\i tm\'enym\'ert\'ekeket (amelyek az \"utemez\'est jellemzik). Pontosabban csak
$F_{\dots}$, $W_{\dots}$, $N_{\dots}$ \'es $L_{\dots}$ sz\'armazik k\"oz\"ul\"uk a fenti
taszkjellemz\H okb\H ol, $E_{\dots}$ \'es $A_{\dots}$ pedig rendre az
$E(S,t)=\left|\{T_i:f_i(S)>t\}\right|$ ($S$ \"utemez\'es mellett a $t$ id\H opontban
befejezetlen taszkok sz\'ama), illetve az $A(S,t)=\sum_{1\le i\le n, \;
f_i(S)>t}p_i$ ($S$ \"utemez\'es mellett a $t$ id\H opontban befejezetlen taszkok
s\'ulyainak \"osszege) jellemz\H okb\H ol sz\'armaznak.

A teljes\'\i tm\'enym\'ert\'ekek indexe azt jel\"oli, hogy maxim\'alis, minim\'alis
avagy s\'ulyozott \'atlagos jellemz\H or\H ol van-e sz\'o (a taszkjellemz\H ok k\"oz\"ul a
maxim\'alis, minim\'alis, illetve s\'ulyokkal sz\'amolt \'atlagos \'ert\'ek). Teh\'at p\'eld\'aul
\Fmax\ a maxim\'alis befejez\'esi id\H o, \Fmin\ a minim\'alis
befejez\'esi id\H o, \Fav\ pedig a s\'ulyozott \'atlagos befejez\'esi id\H o.
(Hasonl\'oan $W_{\dots}$ a v\'arakoz\'asi id\H o, $N_{\dots}$ a pontatlans\'ag,
$L_{\dots}$ pedig a k\'es\'es taszkonk\'ent vett maximuma, minimuma, illetve
s\'ulyozott \'atlaga.) Az $E_{\dots}$ \'es $A_{\dots}$ jellemz\H ok term\'eszetszer\H uleg nem
taszkonk\'ent vett maximumot, minimumot, illetve \'atlagot adnak meg, hanem id\H o
szerintit, ahogy az az al\'abbi \"osszefoglal\'o t\'abl\'azatban l\'athat\'o:

\scriptsize
\begin{center}
\begin{tabular}[c]{| c | c | c |}
\hline
$\Fmax(S)=\max\limits_{1\le i\le n} f_i(S)$ &
$\Fmin(S)=\min\limits_{1\le i\le n} f_i(S)$ &
$\Fav(S)=\displaystyle{\frac1n\sum\limits_{i=1}^{n} p_i f_i(S)}$ \\
\hline
$\Wmax(S)=\max\limits_{1\le i\le n} w_i(S)$ &
$\Wmin(S)=\min\limits_{1\le i\le n} w_i(S)$ &
$\Wav(S)=\displaystyle{\frac1n\sum\limits_{i=1}^{n} p_i w_i(S)}$ \\
\hline
$\Nmax(S)=\max\limits_{1\le i\le n} n_i(S)$ &
$\Nmin(S)=\min\limits_{1\le i\le n} n_i(S)$ &
$\Nav(S)=\displaystyle{\frac1n\sum\limits_{i=1}^{n} p_i n_i(S)}$ \\
\hline
$\Lmax(S)=\max\limits_{1\le i\le n} l_i(S)$ &
$\Lmin(S)=\min\limits_{1\le i\le n} l_i(S)$ &
$\Lav(S)=\displaystyle{\frac1n\sum\limits_{i=1}^{n} p_i l_i(S)}$ \\
\hline
$\Emax(S)=\scriptstyle\mathop{\textstyle\max}\limits_{0\le t\le \Fmax(S)}\textstyle E(S,t)$ &
$\Emin(S)=\scriptstyle\mathop{\textstyle\min}\limits_{0\le t\le \Fmax(S)}\textstyle E(S,t)$ &
$\Eav(S)=\displaystyle{\frac{1}{\Fmax(S)} \int\limits_0^{\Fmax(S)} E(S,t) \; \d t}$ \\
\hline
$\Amax(S)=\scriptstyle\mathop{\textstyle\max}\limits_{0\le t\le \Fmax(S)}\textstyle A(S,t)$ &
$\Amin(S)=\scriptstyle\mathop{\textstyle\min}\limits_{0\le t\le \Fmax(S)}\textstyle A(S,t)$ &
$\Aav(S)=\displaystyle{\frac{1}{\Fmax(S)} \int\limits_0^{\Fmax(S)} A(S,t) \; \d t}$ \\
\hline
\end{tabular}
\end{center}

\normalsize
\begin{megj}
\begin{enumerate}
\item $\Emax(S)=E(S,0)=n$,
   \\ $\Amax(S)=A(S,0)=\sum_{i=1}^n p_i,$
\item $\Emin(S)=E(S,\Fmax(S))=0$,
   \\ $\Amin(S)=A(S,\Fmax(S))=0$,
\item $\Eav(S)
%=\frac{1}{F_\m{max}}\left(n f_1(S) +
%\sum\limits_{i=1}^{n-1}(n-i)\left(f_{i+1}(S) - f_i(S)\right) \right)
=\frac{1}{\Fmax(S)} \sum_{i=1}^n f_i(S)$
\textsl{(l\'asd \ref{abra:intE}.\ \'abra)},
   \\ $\Aav(S)
%=\frac{1}{F_\m{max}} \left(f_1(S) \sum\limits_{i=1}^n p_i +
%\sum\limits_{i=1}^{n-1} \left( (f_{i+1}(S)-f_i(S)) \sum\limits_{j=1}^{n-1} p_j
%\right) \right)
=\frac{1}{\Fmax(S)} \sum_{i=1}^n p_i f_i(S)$
\textsl{(l\'asd \ref{abra:intA}.\ \'abra)}.
\end{enumerate}
\end{megj}

\begin{figure}[!h]
\begin{center}
\resizebox{12cm}{!}{ \includegraphics{intE} }
\end{center}
\caption{\label{abra:intE}$\int_0^{\Fmax(S)} E(S,t) \, \d t$ kisz\'am\'\i t\'asa}
\end{figure}

\begin{figure}[!h]
\begin{center}
\resizebox{12cm}{!}{ \includegraphics{intA.eps} }
\end{center}
\caption{\label{abra:intA}$\int_0^{\Fmax(S)} A(S,t) \, \d t$ kisz\'am\'\i t\'asa}
\end{figure}


\chapter{Egyprocesszoros eredmények}
\section{Bevezetés}
Ebben a fejezetben viszonylag egyszer\H u \"utemez\'esi probl\'em\'akat vizsg\'alunk,
melyekben egyetlen moh\'o \'es oszthatatlan processzor van ($m=1$), kieg\'esz\'\i t\H o
er\H oforr\'as nincs ($s=0$), a feladatok f\"uggetlenek ($<$ \"ures), \'es a taszkok
v\'egrehajt\'asa nem szak\'\i that\'o meg. A taszkokhoz aj\'anlott hat\'arid\H ok tartoznak,
list\'at nem alkalmazunk.

A vizsg\'alt \"utemez\'esi probl\'em\'ak k\"oz\"os formaliz\'alt le\'\i r\'asa ez\'ert a k\"ovetkez\H o
alakra egyszer\H us\"odik: $\pi=(\rho, \tau, \mu)$, $\rho=(\P)$, $\P=\{P_1\}$,
$\tau=(\T,\t,\d,\p)$, $\T=(T_1,\dots,T_n)$, $\t=(t_1,\dots,t_n)$,
$\mathbf{d}=(d_1,\dots,d_n)$, $\p=(p_1,\dots,p_n)$.  Tov\'abb\'a --- mivel egyetlen moh\'o \'es
oszthatatlan processzor van, \'es csak megszak\'\i t\'as n\'elk\"uli algoritmusok j\"ohetnek
sz\'oba, ez\'ert --- az \"utemez\'es a taszkok egy permut\'aci\'oj\'anak kiv\'alaszt\'as\'at jelenti.

Ezen feltev\'esek mellett a minim\'alis v\'arakoz\'asi id\H o a taszkok v\'egrehajt\'asi
sorrendj\'et\H ol f\"uggetlen\"ul nulla ($\Wmin(S)=0,\ \forall S$-re).
Ugyancsak a sorrendt\H ol f\"uggetlen a maxim\'alis befejez\'esi id\H o:
$\Fmax(S)=\sum_{i=1}^n t_i$ mind az $n!$ permut\'aci\'ora.

\Fmin\ akkor \'es csak akkor lesz minim\'alis, ha a taszkok v\'egrehajt\'as\'at
a legkisebb v\'egrehajt\'asi idej\H u taszkkal kezdj\"uk, m\'\i g \Fmin\ maxim\'alis
\'ert\'eke a legnagyobb v\'egrehajt\'asi idej\H u taszkkal val\'o kezd\'es eset\'en \'erhet\H o el.

A maxim\'alis v\'arakoz\'asi id\H o az utolj\'ara v\'egrehajtott taszk j\'o megv\'alaszt\'as\'aval
befoly\'asolhat\'o: a v\'egrehajt\'ast a legkisebb v\'egrehajt\'asi idej\H u taszkkal befejezve
\Wmax\ maxim\'alis lesz, m\'\i g a legnagyobb v\'egrehajt\'asi idej\H u taszkkal befejezve
minim\'alis lesz.

\paragraph{Jel\"ol\'esek}
A tov\'abbiakban az ,,a taszkokat a $\beta_i$ szerint n\"ovekv\H o sorrendben hajtjuk
v\'egre'' kifejez\'es helyett a ,,$\beta_i\no$'' jel\"ol\'est, az ,,akkor \'es csak
akkor, ha'' kifejez\'es helyett pedig a ,,$\acsa$'' jel\"ol\'est is haszn\'aljuk.
\'Ertelemszer\H u jelent\'essel a ,,$\beta_i\csokk$'', ,,$\akkor$'' \'es ,,$\ha$''
jel\"ol\'eseket is alkalmazzuk. Az adott \"utemez\'es szerint $j$.-k\'ent v\'egrehajtott
feladat index\'et pedig $i_j$-vel ($j=1,\dots,n$) jel\"olj\"uk. V\'eg\"ul a ,,$\mu$
maxim\'alis'' \'es ,,$\mu$ minim\'alis'' r\"ovid\'\i t\'es\'ere a ,,$\mu\maxim$'', illetve
,,$\mu\minim$'' jel\"ol\'esek szolg\'alnak.

Ezekkel a jel\"ol\'esekkel p\'eld\'aul az \Fmin-re vonatkoz\'o \'all\'\i t\'asok
r\"oviden \'\i gy \'\i rhat\'ok fel: 
$\Fmin \minim \acsa t_{i_1}=\min\limits_{1\le i\le n} t_i,$ illetve
$\Fmin \maxim \acsa t_{i_1}=\max\limits_{1\le i\le n} t_i$.

\vspace{3ex}\noindent
A k\"ovetkez\H o h\'arom alfejezetben n\'eh\'any \'atlagos, maxim\'alis, illetve minim\'alis
jellemz\H o sz\'els\H o\'ert\'ekeinek el\'er\'es\'et biztos\'\i t\'o felt\'etelt adunk meg.

\section{\'Atlagos jellemz\H ok}
Az \'atlagos s\'ulyozott befejez\'esi id\H o, v\'arakoz\'asi id\H o \'es pontatlans\'ag
sz\'els\H o\'ert\'ekei a $\frac{t_i}{p_i}$ szerint rendezett permut\'aci\'okhoz tartoznak.


\begin{tetel}
\label{tetel:Fav, Nav es Wav}
\Fav\, \Nav\ \'es \Wav\ akkor \'es csak akkor lesz
minim\'alis (maxim\'alis), ha a taszkokat $\frac{t_{i_j}}{p_{i_j}}$ szerint n\"ovekv\H o
(cs\"okken\H o) sorrendben hajtjuk v\'egre.\\
Ennek az \'all\'\i t\'asnak t\"om\"or \'\i r\'asm\'odja: 
\[\Fav, \Nav, \Wav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no,\ \textrm{\'es}\
  \Fav, \Nav, \Wav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk.\]
\end{tetel}

\begin{biz}
\begin{enumerate}[a{)}]
\item Mivel a feladatoknak csak v\'eges sok ($n!$) \"utemez\'ese van, ezek k\"oz\"ott kell
lennie optim\'alisnak.
\item\label{item:szuks} Megmutatjuk, hogy \Fav\ csak akkor lehet minim\'alis, ha a
taszkokat a $\frac{t_{i_j}}{p_{i_j}}$ szerint n\"ovekv\H o sorrendben hajtjuk v\'egre.\\[1ex]
Tegy\"uk fel, hogy van olyan $S$ \"utemez\'es, azaz a taszkoknak olyan
$T_{i_1},\dots,T_{i_n}$ permut\'aci\'oja, amelyre $\Fav(S)$ minim\'alis, de
ugyanakkor van olyan $k\ (1\le k\le n-1)$ index, amelyre
\begin{equation}
\label{eq:t per p nem monoton no}
\frac{t_{i_k}}{p_{i_k}} > \frac{t_{i_{k+1}}}{p_{i_{k+1}}} \ .
\end{equation}
Vizsg\'aljuk most meg  a $T_{i_k}$ \'es $T_{i_{k+1}}$ taszkok sorrendj\'enek
felcser\'el\'es\'evel $S$-b\H ol el\H o\'all\'\i that\'o $S'$ \"utemez\'est, \'es a hozz\'a tartoz\'o
$\Fav(S')$ \'atlagos befejez\'esi id\H ot.\\[1ex]
\Fav\ \'uj \'ert\'eke k\'et ok miatt k\"ul\"onb\"ozik a r\'egit\H ol: $T_{i_k}$
befejez\'esi id\H opontja a csere miatt $t_{i_{k+1}}$-gyel n\H ott, m\'\i g $T_{i_{k+1}}$
befejez\'esi id\H opontja $t_{i_k}$-val cs\"okkent. Ez\'ert
\begin{equation}
\label{eq:ujFav}
\Fav(S')=\frac1n\left( p_{i_k} t_{i_{k+1}} - p_{i_{k+1}} t_{i_k}
\right) + \underbrace{\frac1n\sum_{i=1}^n p_i f_i(S)}_{\Fav(S)}.
\end{equation}
(\ref{eq:t per p nem monoton no}) \'atrendez\'es\'evel azt kapjuk, hogy
$p_{i_k}t_{i_{k+1}} < p_{i_{k+1}}t_{i_k}$,
amib\H ol (\ref{eq:ujFav}) alapj\'an $\Fav(S') < \Fav(S)$ k\"ovetkezik.
Mivel ez ellentmond annak, hogy $\Fav(S)$
minim\'alis, ez\'ert csak $\frac{t_i}{p_i}$ szerint n\"ovekv\H o sorrendhez tartozhat
minim\'alis $\Fav$.
\item\label{item:elegs} A sz\"uks\'egess\'eg ut\'an most a vizsg\'alt felt\'etel el\'egs\'egess\'eg\'et is bel\'atjuk. 
A bizony\'\i t\'as \ref{item:szuks}) r\'esze szerint teh\'at az egyik ,,j\'o'' (n\"ovekv\H o)
permut\'aci\'o adja az optimumot. Ha a $\frac{t_i}{p_i}$ h\'anyados k\'et taszkra n\'ezve
azonos, akkor (\ref{eq:t per p nem monoton no}) \'es (\ref{eq:ujFav}) alapj\'an
sorrendcser\'ej\"uk \Fav\ \'ert\'ek\'et nem befoly\'asolja, teh\'at valamennyi ,,j\'o'' sorrend
minim\'alis \Fav\ \'ert\'ekre vezet.\\
Ezzel a t\'etel \Fav\-re vonatkoz\'o r\'esz\'et bebizony\'\i tottuk.
\item\label{item:Wav es Nav} Az \'atlagos s\'ulyozott v\'arakoz\'asi id\H o \'es pontatlans\'ag defin\'\i ci\'oja alapj\'an
\begin{equation}
\label{eq:Wav}
\Wav(S)=\frac1n \sum_{i=1}^n p_i w_i(S)=
\frac1n \sum_{i=1}^n p_i\underbrace{\left( f_i(S)-t_i \right)}_{s_i(S)} =
\Fav(S)-\frac1n \sum_{i=1}^n p_i t_i,
\end{equation}
\begin{equation}
\label{eq:Nav}
\Nav(S)=\frac1n \sum_{i=1}^n p_i n_i(S)=
\frac1n \sum_{i=1}^n p_i\left( f_i(S)-d_i \right) =
\Fav(S)-\frac1n \sum_{i=1}^n p_i d_i.
\end{equation}
(\ref{eq:Wav}) \'es (\ref{eq:Nav}) szerint \Wav\, illetve\ \Nav\
csak egy addit\'\i v konstanssal k\"ul\"onb\"oznek \Fav-t\H ol, teh\'at akkor \'es
csak akkor lesznek minim\'alisak, ha \Fav\ is az.
\item Az eddigiekben megadtuk annak sz\"uks\'eges \'es el\'egs\'eges felt\'etel\'et, hogy a
vizsg\'alt teljes\'\i tm\'enym\'ert\'ekek \'ert\'ekei minim\'alisak legyenek. Ha
\aref{item:szuks}), \ref{item:elegs}) \'es \ref{item:Wav es Nav}) r\'eszben a
,,minim\'alis'' helyett ,,maxim\'alis'', ,,n\"ovekv\H o'' helyett ,,cs\"okken\H o'', ,,<''
helyett ,,>'' \'es ,,>'' helyett ,,<'' szerepel, akkor a maxim\'alis \'ert\'ekhez
tartoz\'o bizony\'\i t\'ast kapjuk.
\end{enumerate}
\end{biz}
Most megmutatjuk, hogy \aref{tetel:Fav, Nav es Wav}.\ t\'etelhez hasonl\'o \'all\'\i t\'as
teljes\"ul \Eav\ \'es \Aav\ \'ert\'ek\'ere is. L\'attuk, hogy
\begin{equation}
\label{eq:Eav}
\Eav(S)=\frac1{\Fmax(S)} \sum_{i=1}^n f_i(S).
\end{equation}
Mivel $\Fmax(S)$ \'ert\'eke \'alland\'o, \'\i gy (\aref{eq:Eav}) egyenl\H os\'egb\H ol \'es
\aref{tetel:Fav, Nav es Wav}.\ t\'etelb\H ol k\"ovetkezik, hogy \Eav\ akkor \'es csak
akkor minim\'alis, ha a taszkokat $t_i$ n\"ovekv\H o sorrendj\'eben \"utemezz\"uk (ugyanis
$\Fav(S)=\frac1n \sum_{i=1}^n f_i(S)$, \'\i gy $p_i=1$, $(i=1,\dots,n)$ eset\'en
$\Eav(S)=\frac1{\Fmax(S)} n \Fav(S)$, amib\H ol k\"ovetkezik, hogy $\Eav\minim \acsa
\Fav\minim$, vagyis $\Eav\minim \acsa t_i\no$.

Hasonl\'o gondolatmenet alkalmazhat\'o \Aav\ eset\'en is: L\'attuk, hogy
\begin{equation}
\Aav(S)=\frac1{\Fmax(S)} \sum_{i=1}^n p_i f_i(S).
\end{equation}
Ezt felhaszn\'alva $\Aav=\frac1{\Fmax(S)} n \Fav(S)$, amib\H ol --- mivel $\Fmax(S)$
konstans --- k\"ovetkezik, hogy $\Aav\minim \acsa \Fav\minim$, vagyis $\Aav\minim
\acsa t_i\no$.

Term\'eszetesen ugyan\'\i gy \Eav\ \'es \Aav\ maximum\'ara is levezethetj\"uk a sz\"uks\'eges \'es
el\'egs\'eges felt\'etelt.

\section{Maxim\'alis jellemz\H ok}
\label{section:maximalis jellemzok}
A maxim\'alis k\'es\'es \'es a maxim\'alis pontatlans\'ag minimaliz\'al\'as\'ahoz el\'egs\'eges
felt\'etelt biztos\'\i t a k\"ovetkez\H o \'all\'\i t\'as.
\begin{tetel}
\label{tetel:Nmax es Lmax minim}
Ha a taszkokat a $d_{i_j}$ aj\'anlott hat\'arid\H ok n\"ovekv\H o sorrendj\'eben \"utemezz\"uk, akkor
az \Nmax\ maxim\'alis pontatlans\'ag \'es az \Lmax\ maxim\'alis k\'es\'es minim\'alis lesz.
\end{tetel}
\begin{biz}
\begin{enumerate}[a{)}]
\item Mivel a taszkoknak csak v\'eges sok permut\'aci\'oja van, ez\'ert biztosan van
optim\'alis \"utemez\'es.
\item El\H osz\"or a maxim\'alis pontatlans\'agra vonatkoz\'o r\'eszt l\'atjuk be. Tegy\"uk fel,
hogy van olyan $S$ \"utemez\'es, azaz a taszkoknak olyan $T_{i_1},\dots,T_{i_n}$
permut\'aci\'oja, melyre $\Nmax(S)$ minim\'alis, de ugyanakkor van olyan $j$ index
$(1\le j\le n-1)$, melyre
\begin{equation}
\label{eq:d nem monoton no}
d_{i_j} > d_{i_{j+1}}.
\end{equation}
Ekkor a $T_{i_j}$ \'es $T_{i_{j+1}}$ taszkok pontatlans\'agai:
\begin{equation}
\label{eq:eredeti pontatlansagok}
n_{i_j}(S)=f_{i_j}(S)-d_{i_j},\ n_{i_{j+1}}(S)=f_{i_{j+1}}(S)-d_{i_{j+1}}=
f_{i_j}(S)+t_{i_{j+1}}-d_{i_{j+1}}.
\end{equation}
Innen (\ref{eq:d nem monoton no}) \'es $t_{i_{j+1}}>0$ figyelembev\'etel\'evel
$n_{i_{j+1}} < n_{i_j}$, \'es \'\i gy $\Nmax(S)=\max\limits_{1\le k\le n} n_{i_k}
\ge n_{i_{j+1}}$.\\[1ex]
Cser\'elj\"uk fel az $S$ \"utemez\'esben a $T_{i_j}$ \'es $T_{i_{j+1}}$ taszkok
sorrendj\'et, \'es az \'\i gy kapott \'uj \"utemez\'est jel\"olj\"uk $S'$-vel. A tov\'abbiakban az
$S'$-h\"oz tartoz\'o jellemz\H ok jel\'et vessz\H ovel, az $S$-hez tartoz\'ok jel\'et pedig
vessz\H o n\'elk\"ul haszn\'aljuk. Az \'uj \"utemez\'essel a pontatlans\'agok:
\begin{equation}
n_{i_j}'=f_{i_j}'-d_{i_j}=f_{i_j}+t_{i_{j+1}}-d_{i_j},\ 
n_{i_{j+1}}'=f_{i_{j+1}}'-d_{i_{j+1}}=
\underbrace{f_{i_j}+t_{i_{j+1}}}_{f_{i_{j+1}}}-t_{i_j}-d_{i_{j+1}}.
\end{equation}
Figyelj\"uk meg, hogy $n_{i_j}'<n_{i_{j+1}}$ \'es $n_{i_{j+1}}'<n_{i_{j+1}}$, ez\'ert
$\Nmax(S') \le \Nmax(S)$, teh\'at a cser\'et\H ol az \Nmax\ \'ert\'eke nem n\H ott.\\[1ex]
V\'eges sok hasonl\'o cser\'evel el\'erhet\H o, hogy a feladatok hat\'arid\H ok szerint n\"ovekv\H o
sorrendj\'ehez jussunk. Ha ak\'ar egyetlen cser\'evel a kor\'abbin\'al kisebb
pontatlans\'agot kapunk, akkor az ellentmond\'as \'all\'\i t\'asunk helyess\'eg\'et bizony\'\i tja.
Ha minden csere ut\'an v\'altozatlan marad a maxim\'alis pontatlans\'ag, akkor is igaz,
hogy az \'\i gy megadott algoritmus minimaliz\'alja \Nmax-ot.
\item Hasonl\'ok\'eppen l\'athatjuk be, hogy a hat\'arid\H ok szerint n\"ovekv\H o sorrend
eset\'en \Lmax\ minim\'alis lesz. Itt is igaz, hogy csak v\'eges sok \"utemez\'es van.\\
Ism\'et tegy\"uk fel, hogy van olyan $T_{i_1},\dots,T_{i_n}$ permut\'aci\'o, melyre
\Lmax\ minim\'alis, \'es ugyanakkor van olyan $j$ index, melyre (\ref{eq:d nem
monoton no}) fenn\'all. Cser\'elj\"uk fel a $T_{i_j}$ \'es $T_{i_{j+1}}$ taszkokat. A
csere el\H otti \"utemez\'est jel\"olj\"uk $S$-sel, a csere ut\'anit $S'$-vel. Ekkor a csere
el\H otti k\'es\'esek:
\begin{equation}
l_{i_j}=\max(0,f_{i_j}-d_{i_j}),\quad 
l_{i_{j+1}}=\max(0,f_{i_j}+t_{i_{j+1}}-d_{i_{j+1}}.
\end{equation}
Mivel most (\ref{eq:d nem monoton no}) \'es $t_{i_{j+1}}>0$ alapj\'an
$l_{i_{j+1}} \ge l_{i_j}$, ez\'ert $\Lmax(S)=\max\limits_{1\le i\le n}l_i\ge
l_{i_{j+1}}$. Az \'uj k\'es\'esek \'ert\'eke:
\begin{equation}
l_{i_j}'=\max(0,f_{i_j}+t_{i_{j+1}}-d_{i_j}),\quad
l_{i_{j+1}}=\max(0,f_{i_j}+t_{i_{j+1}}-t_{i_j}-d_{i_{j+1}}).
\end{equation}
Mivel most $l_{i_j}'<l_{i_{j+1}}$ \'es $l_{i_{j+1}}'<l_{i_{j+1}}$, ez\'ert
$\Lmax(S') \le \Lmax(S)$.\\[1ex]
V\'eges sok hasonl\'o cser\'evel a hat\'arid\H ok szerint n\"ovekv\H o taszk sorrendet kapunk.
Ak\'ar volt olyan csere, amely ut\'an a maxim\'alis k\'es\'es cs\"okkent, ak\'ar minden
cser\'en\'el v\'altozatlan maradt \Lmax\ \'ert\'eke, mindk\'et esetben igaz, hogy a t\'etel
\Lmax\-ra vonatkoz\'o r\'esz\'et is bizony\'\i tottuk.
\end{enumerate}
\end{biz}
Tekints\"uk most azokat a $T_1$, $T_2$ \'es $T_3$ feladatokat, melyekre $d_1=1$,
$d_2=2$, $d_3=3$, a v\'egrehajt\'asi id\H ok pedig $t_1=t_2=t_3=10$. Ezeket a taszkokat
a hat\'arid\H ok n\"ovekv\H o sorrendj\'eben v\'egrehajtva
$\Nmax(S)=\Lmax(S)=\max(9,18,27)=27$, m\'\i g az el\H oz\H ot\H ol elt\'er\H o $T_2$, $T_1$, $T_3$
sorrend eset\'en ugyancsak $\Nmax(S)=\Lmax(S)=\max(8,19,27)=27$. A p\'eld\'ab\'ol
l\'athat\'o, hogy --- \aref{tetel:Fav, Nav es Wav}.\ t\'etelben tapasztaltakkal
ellent\'etben --- m\'eg k\"ul\"onb\"oz\H o jellemz\H ok (itt: hat\'arid\H ok) eset\'en sem egy\'ertelm\H u
az optim\'alis sorrend.

A teljess\'eg kedv\'e\'ert vizsg\'aljuk meg annak felt\'etel\'et is, hogy \Nmax\, illetve\
\Lmax\ maxim\'alis legyen. A maxim\'alis pontatlans\'ag akkor \'es csak akkor lesz
maxim\'alis, ha utolj\'ara a legkisebb hat\'aridej\H u taszkot hajtjuk v\'egre. \Lmax\
maximaliz\'al\'asakor k\'et esetet kell megk\"ul\"onb\"oztetn\"unk: ha a legkisebb hat\'arid\H o
sem kisebb, mint a v\'egrehajt\'asi id\H ok \"osszege, akkor $\Lmax(S)=0$ mind az $n!$
lehets\'eges \"utemez\'esre. Ha viszont van a v\'egrehajt\'asi id\H ok \"osszeg\'en\'el kisebb
hat\'arid\H o, akkor a sz\"uks\'eges \'es el\'egs\'eges felt\'etel $d_{i_n}=\min\limits_{1\le
i\le n}d_i$ lesz.

\section{Minim\'alis jellemz\H ok}
A minim\'alis pontatlans\'ag \'es a minim\'alis k\'es\'es minimaliz\'al\'as\'ahoz j\'o elvnek t\H unhet
a tartal\'ekid\H ok ($sp_i=d_i-t_i$) alapj\'an val\'o \"utemez\'es. N\'emik\'epp meglep\H o ez\'ert a
k\"ovetkez\H o \'all\'\i t\'as.
\begin{tetel}
\label{tetel:Nmin es Lmin maxim}
Ha a taszkokat a tartal\'ekid\H ok n\"ovekv\H o sorrendj\'eben \"utemezz\"uk, akkor az \Nmin\
minim\'alis pontatlans\'ag \'es az \Lmin\ minim\'alis k\'es\'es maxim\'alis lesz.
\end{tetel}
\begin{biz}
\begin{enumerate}[a{)}]
\item Mivel a taszkoknak csak v\'eges sok permut\'aci\'oja van, az optim\'alis megold\'as
l\'etezik.
\item Megmutatjuk, hogy a tartal\'ekid\H ok n\"ovekv\H o sorrendje eset\'en \Nmin\ maxim\'alis
lesz. Tegy\"uk fel, hogy van olyan $S$ \"utemez\'es, azaz a taszkoknak olyan
$T_{i_1},\dots,T_{i_n}$ sorrendje, amelyre \Nmin\ maxim\'alis, de ugyanakkor van
olyan $j$ index $(1\le j\le n-1)$, amelyre
\begin{equation}
\label{eq:sp nem monoton no}
sp_{i_j}(S)>sp_{i_{j+1}}(S).
\end{equation}
Cser\'elj\"uk fel az $S$ \"utemez\'esben a $T_{i_j}$ \'es a $T_{i_{j+1}}$ taszkokat (\'\i gy
kapjuk az $S'$ \"utemez\'est). A felcser\'elt taszkok eredeti pontatlans\'agai:
\begin{equation}
n_{i_j}=f_{i_j}-d_{i_j}=f_{i_j}-t_{i_j}-sp_{i_j},\enskip 
n_{i_{j+1}}=f_{i_{j+1}}-d_{i_{j+1}}=f_{i_j}+t_{i_{j+1}}-d_{i_{j+1}}=
f_{i_j}-sp_{i_{j+1}}.
\end{equation}
Innen (\ref{eq:sp nem monoton no}) \'es $t_{i_j}>0$ figyelembev\'etel\'evel
$n_{i_j}<n_{i_{j+1}}$, \'es \'\i gy $\Nmin=\min\limits_{1\le i\le n} n_i \le
n_{i_j}$. A csere ut\'ani pontatlans\'agok:
\begin{eqnarray}
\\
\nonumber n_{i_j}'&=&f_{i_j}'-d_{i_j}=f_{i_j}+t_{i_{j+1}}-d_{i_j}=
f_{i_j}+t_{i_{j+1}}-t_{i_j}-sp_{i_j}=n_{i_j}+t_{i_{j+1}},\\
\nonumber n_{i_{j+1}}'&=&f_{i_{j+1}}'-d_{i_{j+1}}=
\underbrace{f_{i_j}+t_{i_{j+1}}}_{f_{i_{j+1}}}-t_{i_j}-d_{i_{j+1}}=
f_{i_j}-t_{i_j}-sp_{i_{j+1}}.
\end{eqnarray}
Mivel $n_{i_j}'>n_{i_j}$ \'es $n_{i_{j+1}}'>n_{i_j}$, \'\i gy $\Nmin(S')\ge\Nmin(S)$.
Teh\'at a cser\'et\H ol a minim\'alis pontatlans\'ag \'ert\'eke nem cs\"okkent, \'\i gy --- $S$
optimalit\'asa miatt --- ugyanakkora maradt.\\[1ex]
V\'eges sok cser\'evel el\'erhet\H o, hogy a taszkoknak a tartal\'ekid\H ok szerint n\"ovekv\H o
sorrendj\'ehez jussunk. Teh\'at a tartal\'ekid\H ok n\"ovekv\H o sorrendj\'eben val\'o \"utemez\'es
maximaliz\'alja \Nmin-t.
\item Hasonl\'o m\'odon l\'atjuk be, hogy a n\"ovekv\H o tartal\'ekid\H ok szerinti \"utemez\'es
eset\'en \Lmin\ maxim\'alis. Tegy\"uk fel, hogy van olyan $S$ optim\'alis permut\'aci\'o \'es
ahhoz olyan $j\ (1\le j\le n-1)$ index, melyre (\ref{eq:sp nem monoton no})
fenn\'all. Ekkor
\begin{eqnarray}
\\
\nonumber l_{i_j}&=&\max(0,f_{i_j}-d_{i_j})=\max(0,f_{i_j}-t_{i_j}-sp_{i_j}),\\
\nonumber l_{i_{j+1}}&=&\max(0,f_{i_{j+1}}-d_{i_{j+1}})=\max(0,f_{i_j}+t_{i_{j+1}}-d_{i_{j+1}})=\max(0,f_{i_j}-sp_{i_{j+1}}).
\end{eqnarray}
Innen (\ref{eq:sp nem monoton no}) \'es $t_{i_j}>0$ alapj\'an $l_{i_j}\le
l_{i_{j+1}}$, \'\i gy $\Lmin=\min\limits_{1\le k\le n} l_k \le l_{i_j}$.
Cser\'elj\"uk fel most a $T_{i_j}$ \'es $T_{i_{j+1}}$ taszkokat. Az \'\i gy kapott $S'$
\"utemez\'es szerinti k\'es\'esek:
\begin{eqnarray}
\\
\nonumber l_{i_j}'&=&\max(0,\underbrace{f_{i_j}+t_{i_{j+1}}}_{f_{i_j}'}-d_{i_j})=\max(0,f_{i_j}+t_{i_{j+1}}-t_{i_j}-sp_{i_j}),\\
\nonumber l_{i_{j+1}}'&=&\max(0,\underbrace{\overbrace{f_{i_j}+t_{i_{j+1}}}^{f_{i_{j+1}}}-t_{i_j}}_{f_{i_{j+1}}'}-d_{i_{j+1}})
=\max(0,f_{i_j}-t_{i_j}-sp_{i_{j+1}}).
\end{eqnarray}
Mivel $l_{i_j}\ge l_{i_j}'$ \'es $l_{i_j}\ge l_{i_{j+1}}'$, \'\i gy $\Lmin(S')\ge
\Lmin(S)$. Ebb\H ol $S$ optimalit\'asa miatt a k\'et ut\'obbi \'ert\'ek egyenl\H os\'ege
k\"ovetkezik.\\[1ex]
V\'eges sok hasonl\'o cser\'evel el\'erhet\H o a n\"ovekv\H o tartal\'ekid\H ok szerinti sorrend,
amib\H ol \'all\'\i t\'asunk k\"ovetkezik.
\end{enumerate}
\end{biz}
Tekints\"uk most \'ujra \aref{section:maximalis jellemzok}.\ r\'esz v\'eg\'en vizsg\'alt
taszkrendszert. Legyen az $S$ \"utemez\'es a $T_1$, $T_2$, $T_3$ permut\'aci\'oval
adott, m\'\i g az $S'$ \"utemez\'es a $T_1$, $T_3$, $T_2$ sorrendhez tartozzon. Most a
tartal\'ekid\H ok $sp_1=-9,\ sp_2=-8,\ sp_3=-7$, azaz $S$ 
\aref{tetel:Nmin es Lmin maxim}.\ t\'etel szerinti \"utemez\'es. Ezekkel az adatokkal
$\Nmin(S)=\Lmin(S)=\min(9,18,27)=9$ \'es $\Nmin(S')=\Lmin(S')=\min(9,17,28)=9$. A
p\'eld\'ab\'ol l\'athat\'o, hogy a t\'etelben szerepl\H o felt\'etel val\'oban csak el\'egs\'eges, de
nem sz\"uks\'eges.

\vspace{2ex}
Vizsg\'aljuk meg most annak felt\'eteleit is, hogy ez a k\'et teljes\'\i tm\'enym\'ert\'ek
minim\'alis \'ert\'eket vegyen fel. \Nmin\ akkor \'es csak akkor lesz minim\'alis, ha
el\H osz\"or a legnagyobb tartal\'ekidej\H u taszkot hajtjuk v\'egre. \Lmin\ eset\'eben k\'et
lehet\H os\'eg van att\'ol f\"ugg\H oen, hogy van-e nemnegat\'\i v tartal\'ekidej\H u taszk. Ha van,
\'ugy \Lmin\ akkor \'es csak akkor lesz minim\'alis, ha van olyan taszk, amelynek
v\'egrehajt\'as\'at hat\'arid\H ore befejezz\"uk (ekkor a minim\'alis k\'es\'es nulla). Ha viszont
minden tartal\'ekid\H o negat\'\i v, \'ugy az a keresett sz\"uks\'eges \'es el\'egs\'eges felt\'etel,
hogy a legnagyobb tartal\'ekidej\H u taszkot hajtsuk v\'egre el\H osz\"or.

\section{Egyprocesszoros eredm\'enyek \"osszefoglal\'asa}
\Aref{tablazat:egyprocesszoros eredmenyek}.\ t\'abl\'azatban \"osszefoglaltuk az
egyprocesszoros \"utemez\'esi eredm\'enyeket. A t\'abl\'azatb\'ol hi\'anyzik az \'atlagos
s\'ulyozott k\'es\'es sz\'els\H o\'ert\'ekeihez tartoz\'o felt\'etel, mivel nem ismeretes olyan
polinomi\'alis algoritmus, amely ezt az \"utemez\'esi probl\'em\'at megoldan\'a.
\begin{table}[!h]
\begin{center}
\begin{tabular}[c]{|| c || c | c ||}
\hhline{|t:===:t|}
Sorsz. & Minimum felt\'etele & Maximum felt\'etele \\
\hhline{|:===:|}
1. & $\Wmin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
2. & $\Emin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
3. & $\Amin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
4. & $\Fmax=\sum\limits_{i=1}^n t_i$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
5. & $\Emax=n$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
6. & $\Amin=\sum\limits_{i=1}^n p_i$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
\hhline{||-||--||}
7. & $\Fmin\minim \acsa t_{i_1}=\min\limits_{1\le j\le n} t_j$ & $\Fmin\maxim \acsa t_{i_1}=\max\limits_{1\le j\le n} t_j$ \\
8. & $\Wmax\minim \acsa t_{i_n}=\max\limits_{1\le j\le n} t_j$ & $\Wmax\maxim \acsa t_{i_n}=\min\limits_{1\le j\le n} t_j$ \\
\hhline{||-||--||}
9. & $\Fav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Fav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
10. & $\Wav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Wav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
11. & $\Nav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Nav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
12. & $\Eav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Eav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
13. & $\Aav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Aav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
\hhline{||-||--||}
14. & $\Nmax\minim \ha d_{i_j}\no$ & $\Nmax\maxim \acsa d_{i_n}=\min\limits_{1\le j\le n} d_j$ \\
15. & $\Lmax\minim \ha d_{i_j}\no$ & $\Lmax=0 \ha \Fmax\le\min\limits_{1\le j\le
n}d_j$ \\
& & $\Nmax\maxim \acsa d_{i_n}=\min\limits_{1\le j\le n} d_j$ \\
16. & $\Nmin\minim \acsa sp_{i_1}=\max\limits_{1\le j\le n} sp_j$ & $\Nmin\maxim \ha sp_{i_j}\no$ \\
17. & $\Lmin=0 \acsa \exists j: f_{i_j}\le d_{i_j}$, ha $\exists i: sp_i\ge0$& $\Lmin\maxim \ha sp_{i_j}\no$ \\
& $\Lmin\minim \acsa sp_{i_1}=\max\limits_{1\le j\le n} sp_j$, egy\'ebk\'ent & \\
\hhline{||-||--||}
18. & $\Lav\minim???$ &$\Lav\maxim???$ \\
\hhline{|b:=:b:==:b|}
\end{tabular}
\end{center}
\caption{\label{tablazat:egyprocesszoros eredmenyek} Egyprocesszoros eredm\'enyek \"osszefoglal\'asa}
\end{table}

\section{Egyprocesszoros eredm\'enyek \"osszefoglal\'asa}
\Aref{tablazat:egyprocesszoros eredmenyek}.\ t\'abl\'azatban \"osszefoglaltuk az
egyprocesszoros \"utemez\'esi eredm\'enyeket. A t\'abl\'azatb\'ol hi\'anyzik az \'atlagos
s\'ulyozott k\'es\'es sz\'els\H o\'ert\'ekeihez tartoz\'o felt\'etel, mivel nem ismeretes olyan
polinomi\'alis algoritmus, amely ezt az \"utemez\'esi probl\'em\'at megoldan\'a.
\begin{table}[!h]
\begin{center}
\begin{tabular}[c]{|| c || c | c ||}
\hhline{|t:===:t|}
Sorsz. & Minimum felt\'etele & Maximum felt\'etele \\
\hhline{|:===:|}
1. & $\Wmin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
2. & $\Emin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
3. & $\Amin=0$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
4. & $\Fmax=\sum\limits_{i=1}^n t_i$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
5. & $\Emax=n$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
6. & $\Amin=\sum\limits_{i=1}^n p_i$ & \"utemez\'est\H ol f\"uggetlen\"ul \\
\hhline{||-||--||}
7. & $\Fmin\minim \acsa t_{i_1}=\min\limits_{1\le j\le n} t_j$ & $\Fmin\maxim \acsa t_{i_1}=\max\limits_{1\le j\le n} t_j$ \\
8. & $\Wmax\minim \acsa t_{i_n}=\max\limits_{1\le j\le n} t_j$ & $\Wmax\maxim \acsa t_{i_n}=\min\limits_{1\le j\le n} t_j$ \\
\hhline{||-||--||}
9. & $\Fav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Fav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
10. & $\Wav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Wav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
11. & $\Nav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Nav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
12. & $\Eav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Eav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
13. & $\Aav\minim \acsa \frac{t_{i_j}}{p_{i_j}}\no$ & $\Aav\maxim \acsa \frac{t_{i_j}}{p_{i_j}}\csokk$ \\
\hhline{||-||--||}
14. & $\Nmax\minim \ha d_{i_j}\no$ & $\Nmax\maxim \acsa d_{i_n}=\min\limits_{1\le j\le n} d_j$ \\
15. & $\Lmax\minim \ha d_{i_j}\no$ & $\Lmax=0 \ha \Fmax\le\min\limits_{1\le j\le
n}d_j$ \\
& & $\Nmax\maxim \acsa d_{i_n}=\min\limits_{1\le j\le n} d_j$ \\
16. & $\Nmin\minim \acsa sp_{i_1}=\max\limits_{1\le j\le n} sp_j$ & $\Nmin\maxim \ha sp_{i_j}\no$ \\
17. & $\Lmin=0 \acsa \exists j: f_{i_j}\le d_{i_j}$, ha $\exists i: sp_i\ge0$& $\Lmin\maxim \ha sp_{i_j}\no$ \\
& $\Lmin\minim \acsa sp_{i_1}=\max\limits_{1\le j\le n} sp_j$, egy\'ebk\'ent & \\
\hhline{||-||--||}
18. & $\Lav\minim???$ &$\Lav\maxim???$ \\
\hhline{|b:=:b:==:b|}
\end{tabular}
\end{center}
\caption{\label{tablazat:egyprocesszoros eredmenyek} Egyprocesszoros eredm\'enyek \"osszefoglal\'asa}
\end{table}

\chapter{Maxim\'alis befejez\'esi id\H o minimaliz\'al\'asa}
\section{Bevezet\'es}
Ebben a fejezetben olyan \"utemez\'esi probl\'em\'akat t\'argyalunk, melyekben a maxim\'alis
befejez\'esi id\H o minimaliz\'al\'asa a c\'el. Ebb\H ol ad\'odik, hogy p\'eld\'aul a hat\'arid\H ok \'es a
s\'ulyok nem befoly\'asolj\'ak a taszkok \"utemez\'es\'et.

A vizsg\'alt probl\'em\'akban kieg\'esz\'\i t\H o er\H oforr\'asok nem szerepelnek, \'\i gy a form\'alis
modell a k\"ovetkez\H o: $\pi=(\rho, \tau, \mu),\ \rho=(\P),\
\P=\{P_1, \dots, P_m\},\ \tau=(\T, <, [t_{ij}]),\ \mu=\Fmax\minim$.

A processzorok az esetek t\"obbs\'eg\'eben azonosak lesznek.

A vizsg\'alt \"utemez\'esi probl\'em\'ak mindegyik\'enek megold\'as\'ara ismeretes polinomi\'alis
algoritmus. A fejezet v\'eg\'en azt is megmutatjuk, hogy a kor\'abban vizsg\'alt
anom\'ali\'ak m\'ert\'eke mekkora lehet.

\section{Fastrukt\'ur\'aj\'u taszkrendszerek}
Tegy\"uk fel, hogy adott $m$ azonos processzor, amelyek moh\'oak. A taszkok legyenek
megszak\'\i thatatlanok, egys\'egnyi v\'egrehajt\'asi idej\H uek, \'es a megel\H oz\'esi rel\'aci\'ot fa
adja meg.
\begin{figure}[!h]
\begin{center}
\resizebox{7cm}{!}{ \includegraphics{taszkfa1.eps} }
\end{center}
\caption{\label{abra:taszkfa1} Fastrukt\'ur\'aj\'u taszkrendszer}
\end{figure}

El\H osz\"or tekints\"uk \aref{abra:taszkfa1}.\ \'abr\'an bemutatott p\'eld\'at, ahol a
taszkokat az A, \dots, N bet\H ukkel jel\"olt\"uk, \'es az egys\'egnyi v\'egrehajt\'asi id\H oket
elhagytuk.
Becs\"ulj\"uk meg $\Fmax(S)$ \'ert\'ek\'et. Mivel 14 taszk van, ez\'ert $m\ge1$ moh\'o
processzor eset\'en $\Fmax(S)\le14$ b\'armely sz\'oba j\"ov\H o algoritmusra. Mivel van \"ot
taszkot tartalmaz\'o l\'anc (p\'eld\'aul N<L<G<C<A), ez\'ert $\Fmax\ge5$. Teh\'at ha
$m\ge1$, akkor $5\le\Fmax(S)\le14$ minden $A$ algoritmusra.

A pontosabb becsl\'eshez r\"ogz\'\i ts\"uk a processzorok sz\'am\'at: legyen $m=3$. 14
megszak\'\i thatatlan taszk v\'egrehajt\'as\'ahoz 3 processzoron m\'eg f\"uggetlen taszkok
eset\'en is legal\'abb 5 id\H oegys\'egre van sz\"uks\'eg, azaz ism\'et azt kaptuk, hogy
$\Fmax(S)\ge5$. Ha a megel\H oz\'esi korl\'atoz\'asokat is figyelembe vessz\"uk, akkor
l\'atjuk, hogy az A taszkot az \"osszes t\"obbi taszk megel\H ozi: mivel 13 taszk 3
processzort legal\'abb 5 id\H oegys\'egre lefoglal, ez\'ert $\Fmax(S)\ge6$. Az eddigieket
\"osszes\'\i tve azt kapjuk, hogy $6\le\Fmax(S)\le14$ minden sz\'oba j\"ov\H o $S$
\"utemez\'esre.

Az egyik lehets\'eges \"utemez\'esi strat\'egia az, hogy a taszkokat lexikografikus
sorrendben (nev\"uk \'ab\'ec\'e szerinti sorrendj\'eben) hajtjuk v\'egre. Ekkor
\aref{abra:lexikografikus utemezes}.\ \'abr\'an bemutatott $S_\m{lex}$
\"utemez\'est kapjuk, amelyre $\Fmax(S_\m{lex})=8$.

\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
B&D&F&N&L&G&C&A\\ \hline
E&I&K&\gr-&\gr-&\gr-&\gr-&\gr-\\ \hline 
H&J&M&\gr-&\gr-&\gr-&\gr-&\gr-\\ \hline
\end{tabular}
\caption{\label{abra:lexikografikus utemezes}Az $S_\m{lex}$ lexikografikus
\"utemez\'es}
\end{center}
\end{figure}

Egy m\'asik lehets\'eges megk\"ozezel\'\i t\'es, hogy az A befejez\H o feladatt\'ol legt\'avolabbi
feladatot igyeksz\"unk \"utemezni (t\"obb jel\"olt eset\'en p\'eld\'aul az el\H obbi,
lexikografikus m\'odon v\'alasztva. Ekkor \aref{abra:legtavolabbit eloszor
utemezes}.\ \'abr\'an bemutatott $S_\m{fur}$ \"utemez\'est kapjuk, amelyre
$\Fmax(S_\m{fur})=6$.
\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|}
\hline
M&I&L&G&C&A\\ \hline
N&J&E&B&\gr-&\gr-\\ \hline
H&K&F&D&\gr-&\gr-\\ \hline
\end{tabular}
\caption{\label{abra:legtavolabbit eloszor utemezes}Az $S_\m{fur}$ ,,legt\'avolabbit el\H osz\"or'' \"utemez\'es}
\end{center}
\end{figure}

Mivel kor\'abban l\'attuk, hogy a maxim\'alis befejez\'esi id\H o legal\'abb 6, ez\'ert
$S_\m{fur}$ optim\'alis \"utemez\'es. A tov\'abbiakban megmutatjuk, hogy a most
vizsg\'alt \"utemez\'esi probl\'em\'ak eset\'en a ,,legt\'avolabbit el\H osz\"or'' elv mindig
optim\'alis \"utemez\'esre vezet.

Ehhez el\H osz\"or vezess\"uk be a taszkok szintj\'enek fogalm\'at. Tegy\"uk fel, hogy a
taszkokat azonos processzorokon hajtjuk v\'egre, azaz a v\'egrehajt\'asi id\H o minden
processzoron azonos. A (defin\'\i ci\'ojuk szerint k\"ormentes) megel\H oz\'esi gr\'afokban
egy {\sl taszk szintj\'et} \'ugy defini\'aljuk, mint a taszkb\'ol a befejez\H o taszkokhoz
vezet\H o utak hosszainak maximuma. Megjegyezz\"uk, hogy egy \'ut hossz\'an az \'ut ment\'en
l\'ev\H o taszkok v\'egrehajt\'asi id\H oinek \"osszeg\'et \'ertj\"uk.

Amint arr\'ol m\'ar volt sz\'o, ebben a r\'eszben a v\'egrehajt\'asi id\H ok egys\'egnyiek, a
megel\H oz\'esi gr\'af pedig fa, ez\'ert egy taszk szintj\'et egyszer\H uen a taszkb\'ol az
egyetlen befejez\H o taszkhoz vezet\H o egyetlen \'ut ment\'en lev\H o taszkok sz\'ama adja.

\vspace{2ex}
{\sl Szintes \"utemez\'esr\H ol} akkor besz\'el\"unk, ha valah\'anyszor \"utemezend\H o taszkot
kell v\'alasztanunk, mindannyiszor a v\'egrehajthat\'o \'es m\'eg nem \"utemezett taszkok
k\"oz\"ul a legmagasabb szint\H uek egyik\'et v\'alasztjuk. Ez p\'eld\'aul a k\"ovetkez\H ok\'eppen
val\'os\'\i that\'o meg: El\H osz\"or az $n$ taszkhoz alkalmas m\'odon hozz\'arendelj\"uk az
$1,2,\dots,n$ c\'\i mk\'eket, majd a taszkokat c\'\i mk\'eik cs\"okken\H o sorrendj\'eben
felsorolva priorit\'asi list\'at k\'esz\'\i t\"unk, \'es ezzel a list\'aval {\sl list\'as
\"utemez\'est} v\'egz\"unk. Ez ut\'obbi azt jelenti, hogy ha \"utemezend\H o taszkot kell
v\'alasztani, azt a lista sorrendj\'eben keress\"uk.

\begin{alg}[LEV]
\label{alg:LEV}
Legyen
\begin{enumerate}
\item alma
\item korte
\end{enumerate}
\end{alg}[LEV]\label{alg:LEV}

\end{document}

\begin{alg}[LEV]\label{alg:LEV}
Legyen $\tau=(\T,<,\t)$ fastrukt\'ur\'aj\'u vagy erdõstrukt\'ur\'aj\'u taszkrendszer, amely
egys\'egnyi v\'egrehajt\'asi idejû, megszak\'\i thatatlan taszkokat tartalmaz. Ekkor a
fastrukt\'ur\'aj\'u $\tau$ $S_\m{LEV}(\tau)$ szintes \"utemez\'ese azonos


\begin{enumerate}
\item alma
\item korte
\end{enumerate}

\end{alg}

\end{document}
processzorokon a k\"ovetkez\H ok\'eppen \'all\'\i that\'o elõ.\\
Defini\'alunk egy $C:\T\rightarrow\{1,\dots,n\}$ ,,c\'\i mk\'ez\H o'' lek\'epez\'est (1--3.\
l\'ep\'es), majd a címkék segíts\'eg\'evel list\'asan \"utemez\"unk (4--5.\ l\'ep\'es).
\begin{enumerate}
\item Ha $\m T\in\T$ a taszkrendszer befejez\H o feladata, akkor $C(\m T):=1$.
\item Tegy\"uk fel, hogy az $1,\dots,j-1\ (j\le n)$ c\'\i mk\'eket m\'ar hozz\'arendelt\"uk
bizonyos taszkokhoz. Legyen $\gamma_j$ azon taszkok halmaza, amelyeknek
\begin{enumerate}[a{)}]
\item m\'eg nincs c\'\i mk\'ej\"uk, \'es
\item k\"ozvetlen r\'ak\"ovetkez\H oj\"uknek m\'ar van c\'\i mk\'eje.
\end{enumerate}
Ha ebben a halmazban T az egyetlen taszk, vagy T r\'ak\"ovetkez\H oj\'enek a c\'\i mk\'eje
a legkisebb, akkor $C(\m T):=j$. Ha viszont t\"obb taszk rendelkezik (azonos)
legkisebb c\'\i mk\'ej\H u k\"ozvetlen r\'ak\"ovetkez\H ovel, akkor ezek b\'armelyik\'et 
(pl.\ a lexikografikusan legkisebbet) v\'alaszthatjuk T-nek, \'es $C(\m T):=j$.
\item Ha van m\'eg c\'\i mk\'ezetlen taszk, akkor folytassuk a 2.\ l\'ep\'est\H ol, egy\'ebk\'ent
pedig a 4.\ l\'ep\'est\H ol.
\item  Indexelj\"uk meg a taszkokat oly m\'odon, hogy a $(\m T_n,\dots,\m T_1)$
list\'ara fenn\'alljon $C(\m T_j)=j$ minden $j=1,\dots,n$ c\'\i mk\'ere.
\item  A $(\m T_n,\dots,\m T_1)$ lista seg\'\i ts\'eg\'evel $m$ azonos processzoron ad\'od\'o
\"utemez\'est nevezz\"uk $S_\m{LEV}$-nek.
\end{enumerate}
Erd\H ostrukt\'ur\'aj\'u $\tau$ eset\'en $\tau$-t kieg\'esz\'\i tj\"uk egy 0 v\'egrehajt\'asi idej\H u
taszkkal, melynek $\tau$ befejez\H o taszkjai lesznek a k\"ozvetlen megel\H oz\H oi, \'es
erre az \'uj taszkrendszerre alkalmazzuk a fenti l\'ep\'eseket.
\end{alg}

\begin{pl}
\Aref{abra:taszkfa1}.\ \'abr\'an szerepl\H o fa eset\'en egy\'ertelm\H uen ad\'odik, hogy
$C(\m{A})=1$. Ekkor az a) tulajdons\'aggal A-n k\'\i v\"ul minden taszk
rendelkezik, k\"oz\"ul\"uk B, C \'es D rendelkezik a b) tulajdons\'aggal is. Mindh\'arom
taszk k\"ozvetlen r\'ak\"ovetkez\H oj\'enek c\'\i mk\'eje azonos (1), \'\i gy mindh\'arom v\'alaszthat\'o
T-nek. Legyen p\'eld\'aul $C(\m{B})=2$. Ezut\'an C \'es D alkotj\'ak $\gamma_3$-at.
Legyen $C(\m{C})=3$. Most $\gamma_4={D,F,G}$, \'es az 1, 3 c\'\i mk\'ek
\"osszehasonl\'\i t\'as\'aval $C(\m{D}):=4$. Ezut\'an $\gamma_5=\{E,F,G\}$, \'es F, G
k\"oz\"ul p\'eld\'aul F-et v\'alasztva $C(\m{F}):=5$. Hasonl\'ok\'eppen folytatva
$C(\m{G})=6$, $C(\m{E})=7$, $C(\m{H})=8$, $C(\m{I})=9$,
$C(\m{J})=10$, $C(\m{K})=11$, $C(\m{L})=12$, $C(\m{M})=13$
\'es $C(\m{N})=14$ ad\'odik.

Ez a c\'\i mk\'ez\'es az (N, M, L, K, J, I, H, E, G, F, D, C, B, A) list\'ara, az pedig
\aref{abra:szintes utemezes}.\ \'abr\'an l\'athat\'o \"utemez\'esre vezet.
\end{pl}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|c|c|}
\hline
    N&L&H&F&C   &A\\ \hline
    M&J&E&D&B   &\gr-\\ \hline
    \fgr K&I&G&\gr-&\gr-&\gr-\\ \hline
\end{tabular}
\caption{\label{abra:szintes utemezes}Az $S_\m{LEV}$ \"utemez\'es
Gantt-diagramja}
\end{center}
\end{figure}

A LEV \"utemez\'esi algoritmussal kapcsolatban megjegyezz\"uk, hogy a taszkok
c\'\i mk\'ez\'ese nem egy\'ertelm\H u: ha a $\gamma_j$-beli taszkok k\"oz\"ul t\"obbnek a k\"ozvetlen
r\'ak\"ovetkez\H oje azonos (\'es \'\i gy a vizsg\'alt c\'\i mk\'ek is azonosak), akkor ezen taszkok
k\"oz\"ul T tetsz\H olegesen v\'alaszthat\'o az algoritmus 2.\ l\'ep\'es\'eben.

\begin{tetel}
\label{tetel:fa eseten LEV minim Fmax-ot ad}
Ha egys\'egnyi v\'egrehajt\'asi idej\H u, megszak\'\i thatatlan taszkokat tartalmaz\'o
fastrukt\'ur\'aj\'u taszkrendszert azonos processzorokra a LEV algoritmussal
(\ref{alg:LEV}.\ algoritmus) \"utemez\"unk, akkor a maxim\'alis befejez\'esi id\H o
minim\'alis lesz.
\end{tetel}
\begin{biz}
\begin{enumerate}[a{)}]
\item Egyszintes (egyetlen taszkot tartalmaz\'o) \'es k\'etszintes taszkrendszerekre
az \'all\'\i t\'as k\"ozvetlen\"ul ad\'odik.
\item A tov\'abbiakban tegy\"uk fel, hogy a vizsg\'alt taszkrendszerek legal\'abb h\'arom
szintet tartalmaznak. Azt is tegy\"uk fel, hogy a t\'etel \'all\'\i t\'as\'aval ellent\'etben
$S_\m{LEV}$ nem minden esetben optim\'alis. Ekkor van olyan, a taszkok $n$
sz\'am\'at tekintve minim\'alis taszkrendszer, amelyre a szintes \"utemez\'es nem
optim\'alis. Egy ilyet $\tau_\m{min}$-nel jel\"olve teh\'at
$\Fmax(S_\m{LEV}(\tau_\m{min}))=F >
\Fmax(S_\m{OPT}(\tau_\m{min}))=F_0$. Term\'eszetesen $\tau_\m{min}$
megv\'alaszt\'as\'ab\'ol k\"ovetkezik, hogy az $n$-n\'el kevesebb taszkot tartalmaz\'o
taszkrendszerek eset\'en LEV optim\'alis \"utemez\'est ad.
\item Mivel a v\'egrehajtand\'o taszkok sz\'ama r\"ogz\'\i tett, ez\'ert az \"ures peri\'odusok
sz\'ama meghat\'arozza $F$-et. A befejez\H o taszk mindig az utols\'o id\H oegys\'egben
hajt\'odik v\'egre. Mivel $S_\m{LEV}$ nem optim\'alis, a $[0,F-2]$ intervallumban
van \"ures peri\'odus (egy\'ebk\'ent $S_\m{LEV}$ optim\'alis lenne). Tegy\"uk fel, hogy
a $p$-edik id\H oegys\'egben van \"ures peri\'odus, ahol $1\le p\le F-2$. Ha $p<F-2$,
akkor a $p$-edik id\H oegys\'eg ut\'an v\'egrehajtott taszkok a $p$-edik id\H oegys\'eg
elej\'en m\'eg nem kezdhet\H ok el, hiszen egy\'ebk\'ent a processzorok moh\'os\'aga miatt
valamelyiket elkezdt\"uk volna. Teh\'at ezen taszkok valamelyik megel\H oz\H oje a
$p$-edik id\H oegys\'egben hajt\'odott v\'egre. Mivel a fastrukt\'ura miatt minden
taszknak legfeljebb egy k\"ozvetlen r\'ak\"ovetkez\H oje van, \'\i gy a
$(p+1),\dots,(F-2)$-edik id\H oegys\'egekben v\'egrehajtott taszkok sz\'amai nem
haladhatj\'ak meg (k\"ul\"on-k\"ul\"on sem) a $p$-edik id\H oegys\'egben v\'egrehajtott
taszkok sz\'am\'at, \'es \'\i gy az $(F-2)$-edik id\H oegys\'egben is van legal\'abb egy
processzor, amelyik nem dolgozik.
\item Legyen $\tau_\m{min}$ befejez\H o taszkja T. $S_\m{LEV}$ szerint
T az $F$-edik id\H oegys\'egben hajt\'odik v\'egre, ez\'ert T-nek van olyan k\"ozvetlen
megel\H oz\H oje, amelyik az $(F-1)$-edik id\H oegys\'egben hajt\'odik v\'egre --- legyen R egy
ilyen taszk. Mivel az $(F-2)$-edik id\H oegys\'egben is van \"ures peri\'odus, \'\i gy R-nek
van olyan k\"ozvetlen megel\H oz\H oje, amelyik ebben az id\H oegys\'egben hajt\'odik v\'egre
(ha nem lenne, akkor R a processzorok moh\'os\'aga miatt m\'ar az $(F-2)$-edik
id\H oegys\'egben v\'egrehajt\'odna) --- legyen Q egy ilyen taszk.\\[1ex]
Tekints\"uk most azt a $\tau'$ taszkrendszert, amelyet $\tau_\m{min}$-b\H ol
kapunk T \'es annak k\"ozvetlen megel\H oz\H oi elt\'avol\'\i t\'as\'aval. Ha az
$S_\m{LEV}(\tau_\m{min})$-nek megfelel\H o Gantt-d\-i\-a\-gram\-ban
minden elt\'avol\'\i tott taszkot \"ures peri\'odussal helyettes\'\i t\"unk, akkor az $S'$
\"utemez\'eshez jutunk, amely $\tau'$ szintes \"utemez\'es\'enek felel meg. Ugyanis:
\begin{enumerate}[i{.)}]
\item T az utols\'o, $F$-edik id\H oegys\'egben hajt\'odik v\'egre, \'\i gy --- mivel minden
m\'as feladatnak r\'ak\"ovetkez\H oje --- T \"ures peri\'odussal val\'o helyettes\'\i t\'ese nem
v\'altoztatja meg a megmarad\'o \"utemez\'es szintes szerkezet\'et.
\item Legyen most P egy olyan k\"ozvetlen megel\H oz\H oje T-nek, amelyik a $k$-adik
id\H oegys\'egben $(1\le k\le F-1)$ hajt\'odik v\'egre. Ha P-t elt\'avol\'\i tjuk, akkor a
$k$-adik peri\'odusban $S'$ k\'esz\'\i t\'esekor csak olyan taszk \"utemezhet\H o, amelynek
szintje azonos P szintj\'evel, vagy ann\'al kisebb: ugyanis, ha $S'$ szerint egy
P-n\'el magasabb szint\H u taszk P ut\'an hajt\'odik v\'egre, akkor a taszkot $S_\m{LEV}$
\"ossze\'all\'\i t\'asakor P el\H ott kellett vizsg\'alnunk, \'es annak kellett fenn\'allnia, hogy
az a taszk nem hajthat\'o v\'egre. Mivel a P-vel azonos vagy n\'ala alacsonyabb
szinten l\'ev\H o taszkokat elt\'avol\'\i tottuk, \'\i gy a P elt\'avol\'\i t\'as\'aval felszabadul\'o \"ures
peri\'odusban egyetlen taszk sem hajt\'odhat v\'egre.
\end{enumerate}
Mivel a taszkok szintje $\tau'$-ben pontosan 2-vel kisebb, mint volt
$\tau_\m{min}$-ben, \'\i gy $S'$ val\'oban szintes \"utemez\'es.
\item Mivel $\tau_\m{min}$-b\H ol k\'et szintet elhagytunk, \'\i gy
$\Fmax(S'(\tau'))=F'\le F-2$. Az el\H obb eml\'\i tett Q taszk az $(F-2)$-edik
id\H oegys\'egben hajt\'odik v\'egre. Mivel Q a T taszk egyik k\"ozvetlen megel\H oz\H oj\'enek
k\"ozvetlen megel\H oz\H oje, amelyik az $(F-2)$-edik id\H oegys\'egben hajt\'odik v\'egre,
\'\i gy Q szintje 3. Ez\'ert az $(F-2)$-edik id\H oegys\'eg el\H ott nem lehet olyan
id\H oegys\'eg, amelyben csak kettes szint\H u taszkok hajt\'odtak v\'egre.
\'Igy $F'$ \'ert\'eke pontosan $F-2$.
\item $\tau'$-h\"oz vegy\"unk hozz\'a egy \'uj taszkot, amelynek k\"ozvetlen megel\H oz\H oi
pontosan $\tau'$ befejez\H o taszkjai. Az \'\i gy kapott $\tau''$ taszkrendszer
strukt\'ur\'aja ugyyancsak fa. Ha az $S'$ \"utemez\'est \'ugy eg\'esz\'\i tj\"uk ki $S''$
\"utemez\'ess\'e, hogy az $(F-1)$-edik id\H oegys\'egben a $\tau''$ befejez\H o feladat\'at
hajtjuk v\'egre, akkor azt kapjuk, hogy $\Fmax(S''(\tau''))=F''=(F-2)+1=F-1$.
\item Mivel $\tau'$-t $\tau_\m{min}$-b\H ol k\'et szintelt\'avol\'\i t\'as\'aval kaptuk,
\'\i gy $\tau'$-ben legfeljebb $n-2$, \'es \'\i gy $\tau''$-ben legfeljebb $n-1$ taszk
van, azaz $\tau''$ kisebb, mint $\tau_\m{min}$. Ha $\tau_\m{min}$-t
optim\'alisan \"utemezz\"uk, akkor befejez\H o\'u taszkja az $F_0$-adik id\H oegys\'egben
hajt\'odik v\'egre. Mivel az $(F_0-1)$-edik id\H oegys\'egben csak a befejez\H o taszk
k\"ozvetlen megel\H oz\H oi hajt\'odhatnak v\'egre $S_\m{OPT}$ szerint, \'\i gy
$\Fmax(S_\m{OPT}(\tau'))=F_0'\le F_0-2$. Amikor $\tau'$-t egy \'uj befejez\H o
taszkkal eg\'esz\'\i tj\"uk ki, akkor a maxim\'alis befejez\'esi id\H o legfeljebb egy
egys\'eggel n\H o, azaz $\Fmax(S_\m{OPT}(\tau''))=F_0''\le F_0-1$.\\
Mivel $F_0<F$, $F''_0\le F_0-1$ \'es $F''=F-1$, innen $F_0''<F''$, azaz $S''$ nem
optim\'alis. Mivel $\tau''$ kisebb, mint $\tau_\m{min}$, ellentmond\'asba
ker\"ult\"unk $\tau_\m{min}$ defin\'\i ci\'oj\'aval, ami a bizony\'\i tand\'o t\'etel
helyess\'eg\'et igazolja.
\end{enumerate}
\end{biz}

\begin{kov}
\label{kov:erdo eseten LEV minim Fmax-ot ad}
Ha egys\'egnyi v\'egrehajt\'asi idej\H u, megszak\'\i thatatlan taszkokat tartalmaz\'o, erd\H o
strukt\'ur\'aj\'u taszkrendszert azonos processzorokra a LEV algoritmussal \"utemez\"unk,
akkor a maxim\'alis befejez\'esi id\H o minim\'alis lesz.
\end{kov}
\begin{biz}
A v\'egrehajtand\'o taszkrendszert kieg\'esz\'\i tj\"uk egy \'uj, egys\'egnyi idej\H u taszkkal,
amelynek a k\"ozvetlen megel\H oz\H oi pontosan az eredeti taszkrendszer befejez\H o
taszkjai. Az \'\i gy kapott $\tau'$ taszkrendszer megfelel \aref{tetel:fa eseten
LEV minim Fmax-ot ad}.\ t\'etel felt\'eteleinek. Ha LEV nem minimaliz\'alja $\Fmax$-ot
$\tau$-ra, akkor nem minimaliz\'alhatja az \'uj taszkrendszerre sem --- ez\'ert
\aref{tetel:fa eseten LEV minim Fmax-ot ad}.\ t\'etelt alkalmazva $\tau'$-re,
megkapjuk a k\"ovetkezm\'eny \'all\'\i t\'as\'at.
\end{biz}
\begin{kov}
Ha egys\'egnyi v\'egrehajt\'asi idej\H u, megszak\'\i thatatlan taszkokat tartalmaz\'o,
antierd\H o strukt\'ur\'aj\'u taszkrendszert azonos processzorokra a LEV algoritmussal
\"utemez\"unk (az al\'abb ismertett m\'odon), akkor a maxim\'alis befejez\'esi id\H o
minim\'alis lesz.
\end{kov}
\begin{biz}
Ford\'\i tsuk meg az entierd\H oben az \'elek ir\'any\'\i t\'as\'at. Az \'\i gy kapott erd\H ostrukt\'ur\'aj\'u
feladatrendszerre alkalmazzuk a LEV algoritmust. K\"onnyen bel\'athat\'o, hogy az \'\i gy
kapott $S_\m{LEV}(\tau')$ \"utemez\'est visszafel\'e olvasva az eredeti
taszkrendszer szintes \"utemez\'es\'ehez jutunk. Ha az antierd\H o strukt\'ur\'aj\'u eredeti
taszkrendszernek lenne a visszafel\'e olvas\'assal kapottn\'al jobb \"utemez\'ese, akkor
annak megford\'\i t\'as\'aval az erd\H o strukt\'ur\'aj\'u $\tau'$-re $S_\m{LEV}(\tau')$-n\'el
jobb \"utemez\'est kapn\'ank, ami ellentmondana \aref{kov:erdo eseten LEV minim
Fmax-ot ad}.\ k\"ovetkezm\'enynek.
\end{biz}

Ha egy taszkrendszer gr\'afj\'aban fa \'es antifa is van (az ilyen ir\'any\'\i tott gr\'afot
nevezhetj\"uk dzsungelnek), akkor egy \"utemez\'es szintes volta m\'ar nem garant\'alja az
optim\'alis megold\'ast. Ezt illusztr\'alja \aref{abra:taszkdszungel}.\ \'abr\'an l\'ev\H o
dzsungel strukt\'ur\'aj\'u taszkrendszer. Ekkor egy szintes \"utemez\'es eredm\'enyezheti az
(A, B, C, E, D, F, G, H, I) list\'at, amelyre h\'arom processzor eset\'en $\Fmax=4$,
m\'\i g az (E, A, B, C, D, F, G, H, I) lista eset\'en az optim\'alis $\Fmax=3$ \'ert\'eket
kapjuk.

\begin{figure}[!h]
\begin{center}
\resizebox{9cm}{!}{ \includegraphics{taszkdzsungel.eps} }
\end{center}
\caption{\label{abra:taszkdszungel} Dzsungel strukt\'ur\'aj\'u taszkrendszer}
\end{figure}

\section{Taszkrendszerek v\'egrehajt\'asa k\'et processzoron}
Ebben a pontban a k\"ovetkez\H o \"utemez\'esi probl\'em\'at vizsg\'aljuk:
$\pi=(\rho,\tau,\mu)$, ahol $\rho=(\P)$, $\P=\{P_1,P_2\}$, $\tau=(\T,<,\t)$,
$\T=\{\m T_1,\dots,\m T_n\}$, $\t=(1,\dots,1)$, $\mu=\Fmax\minim$.

\Aref{abra:ketproctaszkrsz}.\ \'abr\'an bemutatott egyszer\H u taszkrendszer
$S'$ \'es $S''$ \"utemez\'ese is megfelel a szintes elvnek.
Ez a p\'elda bizony\'\i tja, hogy tetsz\H oleges strukt\'ura eset\'en a szintess\'eg m\'eg k\'et
processzorra sem garant\'alja az optim\'alis \"utemez\'est.

\begin{figure}[!h]
\begin{center}
\resizebox{4.5cm}{!}{ \includegraphics{ketproctaszkrsz.eps} }
\end{center}
\begin{center}
$S':$
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|}
\hline
D&  F &A&  C \\ \hline
E&\gr-&B&\gr-\\ \hline
\end{tabular}
\hspace{.7cm}
\normalsize
$S'':$
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|}
\hline
E&D&A \\ \hline
F&C&B \\ \hline
\end{tabular}
\caption{\label{abra:ketproctaszkrsz} Taszkrendszer, \'es k\'et lehets\'eges szintes \"utemez\'ese}
\end{center}
\end{figure}

Tekints\"uk most azt a taszkrendszert, melyben 
%$\T=\{\m{A, B, C, D, E, F, G, H, I, J}$,
%$\m{K, L, M, N, O, P, Q}\}$,
\T=\{A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q\},
\'es $<\, =\!\{
 \m{(D,B)}$, $\m{(D,C)}$, $\m{(E,C)}$, $\m{(F,A)}$, $\m{(F,C)}$,
$\m{(G,A)}$, $\m{(G,D)}$, $\m{(G,E)}$, $\m{(H,D)}$, $\m{(H,E)}$,
$\m{(H,F)}$, $\m{(I,D)}$, $\m{(I,F)}$, $\m{(J,F)}$, $\m{(K,G)}$,
$\m{(L,G)}$, $\m{(L,H)}$, $\m{(M,K)}$, $\m{(M,L)}$, $\m{(N,I)}$,
$\m{(N,M)}$, $\m{(O,N)}$, $\m{(P,N)}$, $\m{(Q,J)}$, $\m{(Q,N)}\}$
(\ref{abra:bonytaszkrsz}.\ \'abra).

Vizsg\'aljuk meg, hogyan lehetne a szintes algoritmust \'ugy \'altal\'anos\'\i tani, hogy
biztos\'\i tsa az optim\'alis \"utemez\'est tetsz\H oleges strukt\'ura eset\'en. Ehhez
megfogalmazunk bizonyos c\'elszer\H unek l\'atsz\'o tulajdons\'agokat. A T taszk c\'\i mk\'ej\'et
(index\'et) most \ind T, szintj\'et pedig \lev T jel\"oli.

\begin{figure}[!h]
\begin{center}
\resizebox{7.3cm}{!}{ \includegraphics{bonytaszkrsz.eps} }
\end{center}
\caption{\label{abra:bonytaszkrsz} Taszkrendszer a LEV algoritmus
\'altal\'anos\'\i t\'as\'ahoz}
\end{figure}

\begin{tul}
\label{tul:nagyobb szint, nagyobb index}
Ha a Q taszk szintje nagyobb, mint az R taszk\'e, akkor az indexe is legyen
nagyobb, azaz teljes\"ulj\"on $\forall \m{Q,R}\in\T:\ \lev Q > \lev R \rightarrow
\ind Q > \ind R$.
\end{tul}

Ha p\'eld\'aul minden szinten p\'aros sz\'am\'u taszk van, akkor ez az elv (tulajdons\'ag)
\"onmag\'aban is elegend\H o az optim\'alis \"utemez\'es megtal\'al\'as\'ahoz.

\begin{tul}
\label{tul:koveto halmazok}
Ha a Q taszk k\"ozvetlen r\'ak\"ovetkez\H oinek halmaza val\'odi r\'eszhalmazk\'ent tartalmazza
az R taszk k\"ozvetlen r\'ak\"ovetkez\H oinek halmaz\'at, akkor $\ind Q > \ind R$.
\end{tul}

Ezek a tulajdons\'agok elegend\H oek arra, hogy a 17-es indexet Q-hoz rendelj\"uk, a
15-\"ost \'es 16-ost pedig O-hoz \'es P-hez. A hatodik szinten csak az N taszk van,
ez\'ert az kapja a 14-es indexet. Ezut\'an az M taszk a 13-as indexet kapja, az L
a 12-est, a K pedig a 11-est.

Hogyan hasonl\'\i tsuk \"ossze a harmadik szinten l\'ev\H o taszkokat, mindenekel\H ott a G-t
\'es H-t? G-nek A, H-nak pedig F a harmadik r\'ak\"ovetkez\H oje a k\"oz\"os D \'es E mellett,
\'\i gy \aref{tul:koveto halmazok}.\ tulajdons\'ag nem el\'eg a v\'alaszt\'ashoz.  Az egyik
lehet\H os\'eg az, hogy H-hoz rendelj\"uk a nagyobb indexet, mivel t\"obb m\'asodik szinten
l\'ev\H o r\'ak\"ovetkez\H oje van, \'es \aref{tul:nagyobb szint, nagyobb index}.\
tulajdons\'agot teljes\'\i t\H o \"utemez\'esben az els\H o szint taszkjai csak akkor
ker\"ulhetnek \"utemez\'esre, ha a m\'asodik szint minden taszkj\'at \"utemezt\"uk m\'ar. \'Igy
teh\'at \ind H:=10, \ind G:=9, \ind I=8 \'es \ind J=7. D \'es F k\"oz\"ul megint nem
tudunk a k\"ovet\H o halmazok alapj\'an d\"onteni, legyen mondjuk \ind D=6 \'es \ind F=5,
v\'eg\"ul \ind E:=4, \ind A:=3, \ind B:=2 \'es \ind C:=1. Jel\"olje $S_\m{GLEV}(\tau)$
az ezen lista alapj\'an ad\'od\'o \"utemez\'est, \'es nevezz\"uk GLEV algoritmusnak az
elj\'ar\'ast, amivel a list\'at (\'es az \"utemez\'est) el\H o\'all\'\i tottuk --- vagyis a fenti k\'et
tulajdons\'ag figyelembev\'etel\'evel m\H uk\"od\H o \"utemez\'esi algoritmust.  Megmutatjuk, hogy
b\'armely $S(\tau)$ \"utemez\'es eset\'en $\Fmax(S(\tau))\ge \Fmax(S_\m{GLEV}(\tau))$,
vagyis hogy GLEV optim\'alis.

Ehhez el\H osz\"or defini\'aljuk a LEV algoritmus \'altalános\'\i tott változat\'at, a GLEV algoritmust.

\begin{alg}[GLEV]
\label{alg:GLEV}
Legyen $\tau=(\T,<,\t)$ tetsz\H oleges strukt\'ur\'aj\'u taszkrendszer, amely
egys\'egnyi v\'egrehajt\'asi idej\H u, megszak\'\i thatatlan taszkokat tartalmaz. Ekkor $\tau$ $S_\m{GLEV}(\tau)$ szintes 
\"utemez\'ese azonos processzorokon a k\"ovetkez\H ok\'eppen \'all\'\i that\'o el\H o.

Defini\'alunk egy $C:\T\rightarrow\{1,\dots,n\}$ ,,c\'\i mk\'ez\H o'' lek\'epez\'est (1--3. l\'ep\'es), 
majd a c\'\i mk\'ek seg\'\i ts\'eg\'evel list\'asan \"utemez\"unk (4--5. l\'ep\'es).
\begin{enumerate}[\bf 1{.\ l\'ep\'es.}]
\item Legyen $\m T\in\T$ a taszkrendszer tetsz\H oleges befejez\H o taszkja, és legyen $C(\m T):=1$.
\item Tegy\"uk fel, hogy az $1,\dots,j-1\ (j\le n)$ c\'\i mk\'eket m\'ar hozz\'arendelt\"uk bizonyos taszkokhoz. 
Legyen $\gamma _j$ azon taszkok halmaza, amelyeknek
\begin{enumerate}[a{)}]
\item m\'eg nincs c\'\i mk\'ej\"uk, \'es
\item nincs c\'\i mk\'ezetlen k\"ozvetlen r\'ak\"ovetkez\H oj\"uk.
\end{enumerate}

\item Most kiv\'alasztjuk  $\gamma _j$ azon elem\'et, amelyik a $j$ c\'\i mk\'et fogja kapni.

Ehhez minden $\m T\in \gamma _j$ taszkhoz hozzárendeljük a k\"ozvetlen r\'ak\"ovetkez\H oinek
indexeit cs\"okken\H o sorrendben tartalmaz\'o list\'at, melyet $\overline{\m T}$-vel jel\"ol\"unk. 

Legyen most $\m T\in \gamma _j$ olyan taszk, amelyre $\overline{\m T} \leq \overline{\m Q}$ teljes\"ul minden 
$\m Q\in \gamma _j$ taszkra, ahol a $\leq$ lexikografikus \"osszehasonl\'\i t\'ast jelent. Ekkor legyen 
$C(\m T):=j$.
\item Ha van m\'eg c\'\i mk\'ezetlen taszk, akkor folytassuk a 2.\ l\'ep\'est\H ol, egy\'ebk\'ent
pedig a 4.\ l\'ep\'est\H ol.
\item Indexelj\"uk meg a taszkokat oly m\'odon, hogy a $(\m T_n,\dots,\m T_1)$
list\'ara fenn\'alljon $C(\m T_j)=j$ minden $j=1,\dots,n$ c\'\i mk\'ere.
\item A $(\m T_n,\dots,\m T_1)$ lista seg\'\i ts\'eg\'evel $m$ azonos processzoron ad\'od\'o
\"utemez\'est nevezz\"uk $S_\m{GLEV}$-nek.
\end{enumerate}
\end{alg}

Mivel a taszkok egys\'egnyi v\'egrehajt\'asi idej\H uek, ez\'ert v\'egrehajt\'asuk olyan
intervallumokban t\"ort\'enik, amelyek v\'egpontjai eg\'esz sz\'amok. Jel\"olj\"uk $\lambda(\m
T)$-vel azt az id\H oegys\'eget, amelyben T v\'egrehajt\'odik.

Mint kor\'abban is, minden id\H oegys\'egben el\H osz\"or a $P_1$ processzorhoz rendel\"unk
taszkot. Ekkor igaz a k\"ovetkez\H o \'all\'\i t\'as.
\begin{lemma}
\label{lemma:lambda(R)>=lambda(T) akkor I(R)<I(T)}
Ha a GLEV algoritmussal kapott \"utemez\'es szerint T a $P_1$ processzoron
hajt\'odik v\'egre, akkor \T\ minden T-t\H ol k\"ul\"onb\"oz\H o, T-n\'el nem kor\'abban
v\'egrehajtott elem\'enek indexe kisebb, mint \ind T, azaz $\forall \m R\in\T:\ 
\m R\neq\m T \land \lambda(\m R)\ge\lambda(\m T) \rightarrow \ind R<\ind T$.
\end{lemma}
\begin{biz}
Amikor a T taszkot GLEV szerint a $P_1$ processzorhoz rendelt\"uk, akkor a m\'eg
\"utemezetlen taszkok vagy \"utemezhet\H oek voltak, vagy nem. Mivel T a $P_1$
processzoron a $\lambda(\m T)$-edik id\H oegys\'egben hajt\'odik v\'egre, a t\"obbi
\"utemezhet\H o taszk indexe kisebb volt, mint \ind T. A nem \"utemezhet\H o taszkok csak
valamelyik -- az adott id\H opontban \"utemezhet\H o -- megel\H oz\H oj\"uk befejez\'ese ut\'an
v\'alnak v\'egrehajthat\'ov\'a. Mivel GLEV szerint a taszkok csak akkor kaphatnak
c\'\i mk\'et, amikor m\'ar minden megel\H oz\H oj\"uk kapott c\'\i mk\'et (\'es a c\'\i mk\'ek cs\"okken\H o
sorrendben ker\"ulnek kioszt\'asra), \'\i gy minden taszk c\'\i mk\'eje kisebb, mint a
megel\H oz\H oinek c\'\i mk\'eje. Teh\'at a nem \"utemezhet\H o taszkok is rendelkeznek a fenti
tulajdons\'aggal.
\end{biz}

A tov\'abbiakban fontos szerepet j\'atszanak a \textsl{domin\'al\'o taszkok}, az
\textsl{ugr\'o taszkok}, \'es a seg\'\i ts\'eg\"ukkel defini\'alt \textsl{k\"ovet\H o halmazok},
amelyeket az al\'abbi (FOL) algoritmus seg\'\i ts\'eg\'evel adunk meg.
\begin{alg}[FOL]
Legyen $S_\m{GLEV}(\tau)$ a $\tau$ taszkrendszer GLEV \'altal el\H o\'all\'\i tott
\"utemez\'ese. Ekkor az adott \"utemez\'eshez tartoz\'o $k$ term\'eszetes sz\'amot, a $\m
D_k, \dots$, $\m D_1$, $\m D_0$ domin\'al\'o taszkokat, a $\m J_k, \dots$, $\m J_1$,
$\m J_0$ ugr\'o taszkokat, valamint az $F_0$, $F_1, \dots$, $F_k$ k\"ovet\H o
halmazokat meghat\'aroz\'o FOL algoritmus a k\"ovetkez\H o l\'ep\'esekb\H ol \'all.
\begin{enumerate} %[\bf 1{.\ l\'ep\'es.}]
\item \textbf{1. lépés} Legyenek Q, illetve R a $P_1$, illetve $P_2$ processzoron az utols\'o id\H oegys\'egben
v\'egrehajtott taszkok (R \"ures peri\'odus is lehet). Ekkor $\m D_0:=\m Q$ \'es $\m
J_0:=R$.
\item \item \textbf{2. lépés} Tegy\"uk fel, hogy $\m D_{j-1},\dots,\m D_0$ \'es $\m J_{j-1},\dots,\m J_0$
m\'ar ismert, $\m D_j$ \'es $\m J_j$ m\'eg nem. Ekkor $\m J_j$ (ha van ilyen) az a T
taszk vagy \"ures peri\'odus, amelyre
\begin{enumerate}[a{)}]
\item $\ind {\m T} < \ind {\m D_{j-1}}$, ahol feltessz\"uk, hogy az \"ures peri\'odus indexe
nulla;
\item $\lambda(\m T) < \lambda(\m D_{j-1})$;
\item az el\H oz\H o k\'et felt\'etelnek eleget tev\H o taszkok k\"oz\"ul $\lambda(\m T)$ a
lehet\H o legnagyobb.
\end{enumerate}
\item \textbf{3. lépés}  Ha $\m J_j$ l\'etezik, akkor $\m D_j$ legyen az a taszk, amely a $\lambda(\m
J_j)$-edik intervallumban a $P_1$ processzoron hajt\'odik v\'egre, \'es menj\"unk a 2.\
l\'ep\'esre.
\item \item \textbf{1. lépés} Legyen $k=j-1$. Ekkor $F_k:=\{\,T\mid\lambda(\m T)<\lambda(\m D_k)\} \cup
\{\m D_k\}$, $F_i:=\{\,T\mid\lambda(\m D_{i+1})<\lambda(\m T)<\lambda(\m D_i)\}
\cup \{\m D_i\}$, $(i=0, 1, \dots, k-1)$.
\end{enumerate}
\end{alg}

A k\"ovetkez\H o, \ref{abra:FOL fogalmai}.\ \'abra mutatja a defin\'\i ci\'oban szerepl\H o
taszkok k\"oz\"otti kapcsolatot. A $\m J_i$ taszk megel\H ozi a $\m D_{i-1}$-et,
,,el\'ebe ugrik'' abban az \'ertelemben, hogy kor\'abban hajt\'odik v\'egre annak
ellen\'ere, hogy az indexe kisebb. A k\"ovetkez\H o lemm\'aban megmutatjuk, hogy a
$\m D_i$ taszk domin\'al az $F_{i-1}$-beli taszkok felett abban az \'ertelemben,
hogy megel\H ozi \H oket.

\begin{figure}[!h]
\begin{center}
\footnotesize
\begin{tabular}{|c|c|c|c|c|}
\multicolumn{1}{c}{}&\multicolumn{2}{c}{$F_i$}&\multicolumn{2}{c}{$F_{i-1}$} \\
\hline
$\m D_{i+1}$ & \gr{\hbox{\quad\dots\quad}} & \gr{$\m D_i$} & \dgr{\hbox{\quad\dots\quad}} & \dgr{$\m D_{i-1}$}\\\hline
$\m J_{i+1}$ & \gr\dots & $\m J_i$ & \dgr\dots & $\m J_{i-1}$\\\hline
\end{tabular}
\caption{\label{abra:FOL fogalmai} Az ugr\'o \'es domin\'al\'o taszkok, \'es a k\"ovet\H o halmazok}
\end{center}
\end{figure}

\begin{lemma}
\label{lemma:Di dominal Fi-1 elemei felett}
A $\m D_i$ $(i=1,\dots,k)$ taszk megel\H ozi az $F_{i-1}$ k\"ovet\H o halmaz minden
elem\'et.
\end{lemma}
\begin{biz}
A $\m D_i$ \'es a $\m J_i$ taszkok egyidej\H uleg hajt\'odnak v\'egre. $\m J_i$-t \'ugy
v\'alasztottuk meg, hogy $\ind{\m J_i} < \ind{\m D_{i-1}}$ teljes\"ulj\"on, \'es $\m J_i$ a
lehet\H o legk\"ozelebbi legyen (balr\'ol, azaz a kor\'abban v\'egrehajtott taszkok k\"oz\"ul)
$\m D_{i-1}$-hez. Ez\'ert minden $F_{i-1}$-beli T taszkra teljes\"ul, hogy
$\ind {\m D_{i-1}} < \ind T$, \'es az egyenl\H otlens\'eg tranzitivit\'asa miatt fenn\'all 
$\ind {\m J_i} < {\ind T}$. Mivel az $F_{i-1}$-beli taszkok indexe nagyobb, mint 
$\ind {\m J_i}$, ez\'ert az \"utemez\'es sor\'an el\H obb vizsg\'altuk \H oket, mint $\m J_i$-t. Mivel
helyett\"uk $\m J_i$-t \"utemezt\"uk, \'\i gy akkor \H ok nem voltak \"utemezhet\H oek. Ebb\H ol
k\"ovetkezik, hogy $\m D_i$ minden ilyen T taszknak megel\H oz\H oje (nem felt\'etlen\"ul
k\"ozvetlen megel\H oz\H oje).
\end{biz}

Most megmutatjuk, hogy nemcsak $\m D_i$, hanem $F_i$ minden eleme domin\'al
$F_{i-1}$ elemei felett.

\begin{lemma}
\label{lemma:Fi minden eleme domin\'al Fi-1 elemei felett}
Az $F_i$ halmaz $(i=1,\dots,k)$ b\'armely eleme megel\H ozi az $F_{i-1}$ halmaz
b\'armely elem\'et.
\end{lemma}
\begin{biz}
Tegy\"uk fel, hogy az \'all\'\i t\'as nem igaz. Akkor van olyan $i$ index $(1\le i\le k)$,
hogy egy $F_i$-beli Q taszk nem el\H oz meg egy $F_{i-1}$-beli R taszkot. Ekkor
Q-nak vagy nincs r\'ak\"ovetkez\H oje $F_i$-ben (a eset), vagy van (b eset):
\begin{enumerate}[a{)}]
\item Ekkor \aref{lemma:Di dominal Fi-1 elemei felett}. lemma szerint Q
k\"ul\"onb\"ozik $\m D_i$-t\H ol, \'es $\m D_i<\m R$. $F_i$ defin\'\i ci\'oja szerint 
$\ind Q>\ind(\m D_i)$, mivel egy\'ebk\'ent Q sz\'oba j\"ott volna $\m J_{i+1}$-k\'ent, \'es nem
lehetne $F_i$ eleme.\\
Legyen $\overline{\m D_i}=(n_1,\dots,n_r)$ (a $\m D_i$ r\'ak\"ovetkez\H oinek
indexeit tartalmaz\'o lista), \'es $\delta_{i-1}$ legyen azon
$F_{i-1}$-beli taszkok halmaza, amelyeknek nincs k\"ozvetlen megel\H oz\H oj\"uk
$F_{i-1}$-ben. Ekkor $\delta_{i-1}$ elemeinek indexei jelen vannak $\overline{\m
D_i}$-ban, hiszen ezek az elemek $\m D_i$ k\"ozvetlen r\'ak\"ovetkez\H oi.
$F_{i-1}$ azon elemeinek indexei, amelyek nem tartoznak $\delta_{i-1}$-hez,
nincsenek jelen $\overline{\m D_i}$-ban, mivel a megel\H oz\'esi gr\'afban nincsenek
redund\'ans \'elek. $F_{i-1}$ elemeinek indexei nem kisebbek $\ind(\m D_{i-1})$-n\'el,
viszont $F_{i-2},\dots,F_0$ elemeinek indexei \'es a $\m J_{i-1},\dots,\m J_0$
taszkok indexei \aref{lemma:lambda(R)>=lambda(T) akkor I(R)<I(T)}.\ lemma
szerint kisebbek $\ind(\m D_{i-1})$-n\'el, ez\'ert $\delta_{i-1}$ elemeinek indexei az
els\H o $|\delta_{i-1}|$ helyet foglalj\'ak el $\overline{\m D_i}$-ban. Mivel $\ind Q>\ind(\m D_i)$, 
ez\'ert $\overline{\m D_i}\le\overline{\m Q}$, ez\'ert nem \"ures
$\overline{\m D_i}$ eset\'en $\overline{\m Q}$ sem lehet \"ures lista. Mindez csak
\'ugy lehets\'eges, hogy Q k\"ozvetlen megel\H oz\H oje $\delta_{i-1}$ valamennyi elem\'enek;
ekkor viszont Q megel\H oz\H oje $F_{i-1}$ valamennyi elem\'enek, ami ellentmond R
v\'alaszt\'as\'anak.
\item Ha Q-nak van r\'ak\"ovetkez\H oje $F_i$-ben, akkor van olyan Z r\'ak\"ovetkez\H oje is,
amelynek m\'ar nincs r\'ak\"ovetkez\H oje $F_i$-ben. Ekkor a m\'ar bizony\'\i tott a) r\'esz
szerint Z megel\H ozi $F_{i-1}$ b\'armely elem\'et, \'es \'\i gy a megel\H oz\'es tranzitivit\'asa
miatt Q is megel\H ozi $F_{i-1}$ minden elem\'et, azaz R-et is. Ez az ellentmond\'as
teljess\'e teszi a lemma bizony\'\i t\'as\'at.
\end{enumerate}
\end{biz}

\Aref{lemma:Fi minden eleme domin\'al Fi-1 elemei felett}.\ lemma seg\'\i ts\'eg\'evel
bizony\'\i that\'o GLEV optimalit\'asa.

\begin{tetel}
\label{tetel:GLEV optimalis}
Ha egys\'egnyi v\'egrehajt\'asi idej\H u, megszak\'\i thatatlan taszkokat tartalmaz\'o
taszkrendszert k\'et azonos processzorra a GLEV algoritmussal \"utemez\"unk, akkor a
maxim\'alis befejez\'esi id\H o minim\'alis lesz.
\end{tetel}
\begin{biz} 
Legyen $S_\m{GLEV}(\tau)$ a GLEV algoritmussal kapott \"utemez\'es, \'es
$F_0,\dots,F_k$ az \"utemez\'eshez tartoz\'o k\"ovet\H ohalmazok. Ekkor \aref{lemma:Fi
minden eleme domin\'al Fi-1 elemei felett}.\ lemma szerint $F_i$
b\'armely eleme megel\H ozi $F_{i-1}$ b\'armely elem\'et $(i=1,\dots,k)$, \'es \'\i gy az
$F_{i-1}$-beli taszkok v\'egrehajt\'asa csak az $F_i$-beli taszkok v\'egrehajt\'as\'anak
befejez\'ese ut\'an kezd\H odhet el. A k\"ovet\H o halmazok defin\'\i ci\'oja szerint ezen
halmazok elemsz\'ama p\'aratlan. Legyen $F_i$ elemsz\'ama $2m_i-1$. Ekkor $F_i$
elemeinek k\'et processzoron val\'o v\'egrehajt\'as\'ahoz legal\'abb $m_i$ id\H oegys\'egre van
sz\"uks\'ege b\'armely algorimusnak, azaz $\Fmax(S_\m A(\tau))\ge\sum_{i=1}^k m_i$
b\'armely A algoritmus eset\'en. Mivel $\Fmax(S_\m{GLEV}(\tau))=\sum_{i=1}^k m_i$,
\'\i gy GLEV val\'oban minimaliz\'alja \Fmax \'ert\'ek\'et.
\end{biz}

A t\'etellel kapcsolatban vizsg\'aljuk meg azt a taszkrendszert, amelyben $\T=\{$A,
B, C, D, E, F, G, H\}, \'es $<\, =\{\m{(E,D)}$, $\m{(F,A)}$, $\m{(F,B)}$,
$\m{(F,C)}$, $\m{(F,E)}$ $\m{(G,D)}$, $\m{(G,E)}$, $\m{(H,D)}$, $\m{(H,E)}\}$.
GLEV szerint az indexek p\'eld\'aul \'ab\'ec\'esorrendben rendelhet\H ok a taszkokhoz, \'es
akkor \aref{abra:GLEV redundans ellel}.\ \'abra bal oldal\'an szerepl\H o Gantt-diagram
szerint $\Fmax(S_\m{GLEV}(\tau))=5$, szemben a jobb oldalon bemutatott
$\Fmax(S_\m{OPT}(\tau))=4$ \'ert\'ekkel.

\begin{figure}[!h]
\begin{center}
$S_\m{GLEV}:$
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|c|}
\hline
H&  F &  E &D&B \\ \hline
G&\gr-&\gr-&C&A \\ \hline
\end{tabular}
\hspace{.7cm}
\normalsize
$S_\m{OPT}:$
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|}
\hline
F&G&E&D \\ \hline
H&C&A&B \\ \hline
\end{tabular}
\caption{\label{abra:GLEV redundans ellel} A GLEV algoritmussal kapott \"utemez\'es, \'es egy optim\'alis \"utemez\'es}
\end{center}
\end{figure}

A bal oldali \"utemez\'est \'ugy kaptuk, hogy a taszkrendszer gr\'afj\'at \aref{abra:graf
redundans ellel}.\ \'abr\'an l\'athat\'onak t\'etelezt\"uk fel.
\begin{figure}[!h]
\begin{center}
\resizebox{6cm}{!}{ \includegraphics{redundansel.eps} }
\end{center}
\caption{\label{abra:graf redundans ellel} A taszkrendszer redund\'ans \'eleket
tartalmaz\'o gr\'afja}
\end{figure}
A p\'elda nem mond ellent \aref{tetel:GLEV optimalis}.\ t\'etelnek, ugyanis
\aref{abra:graf redundans ellel}.\ \'abr\'an l\'ev\H o gr\'af a redund\'ans $\m{(H,D)}$ \'es
$\m{(G,D)}$ \'eleket is tartamazza, ami miatt az indexel\'es hib\'as lett. A k\'et \'elt
elhagyva GLEV optim\'alis megold\'ast ad.

\Aref{abra:haromproctaszkrsz}.\ \'abr\'an bemutatott taszkrendszer azt mutatja, hogy
p\'eld\'aul h\'arom processzor eset\'en GLEV nem garant\'alja \Fmax optim\'alis \'ert\'ek\'et: az
\'abra szerint az \'altal\'anos szintes algoritmus alkalmaz\'asa eset\'en 5, m\'\i g optim\'alis
esetben csak 4 id\H oegys\'eg kell a taszkrendszer v\'egrehajt\'as\'ahoz.
\begin{figure}[!h]
\begin{center}
\resizebox{9cm}{!}{ \includegraphics{haromproctaszkrsz.eps} }
\end{center}
\begin{center}
$S_\m{GLEV}:$
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|c|}
\hline
11&  8 &6&  3 &  2  \\ \hline
10&  7 &5&  1 &\gr- \\ \hline
 9&\gr-&4&\gr-&\gr- \\ \hline
\end{tabular}
\hspace{.7cm}
\normalsize
$S_\m{OPT}:$
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$
\end{tabular}
\footnotesize
\begin{tabular}{|c|c|c|c|}
\hline
 7&5&4&2  \\ \hline
11&9&3&1   \\ \hline
10&8&6&\gr- \\ \hline
\end{tabular}
\caption{\label{abra:haromproctaszkrsz} Taszkrendszer 3-processzoros
\"utemez\'eshez; a GLEV algoritmussal kapott \"utemez\'es, \'es egy optim\'alis \"utemez\'es}
\end{center}
\end{figure}

\section{F\"uggetlen feladatok}
Ebben a pontban a k\"ovetkez\H o \"utemez\'esi probl\'em\'at vizsg\'aljuk:
$\pi=(\rho,\tau,\mu)$, ahol $\rho=(\P)$, $\P=\{P_1,\dots,P_m\}$, $\tau=(\T,\t)$,
$\T=\{\m T_1,\dots,\m T_n\}$, $\t=(t_1,\dots,t_n)$,
a processzorok azonosak, a taszkok megszak\'\i that\'oak, $\mu=\Fmax\minim$.

Legyen a v\'egrehajt\'asi id\H ok \"osszege $X$. Mivel a legkedvez\H obb eset az \'all\'asid\H o
n\'elk\"uli \"utemez\'es lenne, \'\i gy tetsz\H oleges A \"utemez\'esi algoritmus eset\'en fenn\'all
$\Fmax(S_\m A%(\tau)
)\ge\frac Xm$.

Legyen $t_\m{max}=\max_{1\le i\le n} t_i$. Mivel egy feladat v\'egrehajt\'as\'an
egyidej\H uleg legfeljebb egy processzor dolgozhat, ez\'ert tetsz\H oleges A \"utemez\'esi
algoritmus eset\'en fenn\'all $\Fmax(S_\m A)\ge t_\m{max}$.

\begin{alg}[CONT]
A fenti jel\"ol\'eseket haszn\'alja a ,,folytonos'' %(CONT)
algoritmus:
\begin{enumerate} %[\bf 1{.\ l\'ep\'es.}]
\item \item \textbf{1. lépés} Legyen $F=\max(t_\m{max},\frac Xm)$, \'es \"utemezz\"uk a $\m T_1$ taszkot a
$P_1$ processzorra a $[0,t_1]$ intervallumban.
\item Ha minden taszkot \"utemezt\"unk, akkor STOP.
\item Tegy\"uk fel, hogy eddig a $\m T_1,\dots,\m T_{i-1}$ taszkokat \"utemezt\"uk, \'es
hogy a $P_1$, \dots, $P_{j-1}$ processzorok teljesen (a $[0,F]$ intervallumban)
foglaltak, a $P_j$ processzor pedig csak r\'eszben foglalt (a $[0,f]$
intervallumban, ahol $0\le f<F$).
\item Ha $t_i\le F-f$, akkor \"utemezz\"uk $\m T_i$-t $P_j$-re, az $[f,f+t_i]$
intervallumban, egy\'ebk\'ent pedig \"utemezz\"uk $\m T_i$ $F-f$ v\'egrehajt\'asi idej\H u
$\m T''$ r\'esz\'et $P_{j}$-re az $[f,F]$ intervallumban, \'es $t_i-(F-f)$
v\'egrehajt\'asi idej\H u $\m T'$ r\'esz\'et $P_{j+1}$-re a $[0,t_i-F+f]$ intervallumban.
\end{enumerate}
\end{alg}

\begin{tetel}
Ha f\"uggetlen, megszak\'\i that\'o taszkokat azonos processzorokra CONT seg\'\i ts\'eg\'evel
\"utemez\"unk, akkor \Fmax\ minim\'alis lesz, \'ert\'eke pedig
$\Fmax(S_\m{CONT})=\max(t_\m{max},\frac Xm)$.
\end{tetel}
\begin{biz}
\begin{enumerate}[a{)}]
\item Mivel tetsz\H oleges A \"utemez\'esi algoritmus eset\'en $\Fmax(S_\m A)\ge
t_\m{max}$ \'es $\Fmax(S_\m A)\ge\frac Xm$, \'\i gy $\Fmax(S_\m A)\ge
F=\max(t_\m{max},\frac Xm)$.
\item CONT ezt az okvetlen\"ul sz\"uks\'eges \'ert\'eket biztos\'\i tja, mivel egyr\'eszt $F$
el\'eg nagy ahhoz, hogy CONT szerint egy taszkon egyszerre legfeljebb egy
processzor dolgozzon ($\m T'$ \'es $\m T''$ s\'avjai ne fedj\'ek \'at egym\'ast), m\'asr\'eszt
$F$ el\'eg nagy ahhoz, hogy $\m T_n$ is id\H oben befejez\H odj\'ek ($\m T_n$ s\'avja ne
,,l\'ogjon ki'').
\end{enumerate}
\end{biz}

\section{\"Utemez\'esi anom\'ali\'ak I.}
Ebben a pontban azt mutatjuk be, hogy egy \"utemez\'esi probl\'ema ,,k\"onny\'\i t\'ese'' is
kiv\'althatja a hat\'ekonys\'agi jellemz\H ok roml\'as\'at.

\begin{pelda}
Tekints\"uk az al\'abbi $\tau_1$ taszkrendszert, \'es annak az $L=(\m T_1,\dots,\m
T_9)$ list\'aval kapott $S_1$ \"utemez\'es\'et h\'arom ($m=3$) azonos processzoron.
Ekkor (\ref{abra:anom1}.\ \'abra) $\Fmax(S_1)=12$, amir\H ol k\"onnyen bel\'athat\'o, hogy
optim\'alis \'ert\'ek.
\begin{figure}[!h]
\begin{center}
\resizebox{7.5cm}{!}{ \includegraphics{anom1.eps} }
\end{center}
\begin{center}
\parbox[5ex]{2em}{$S_1:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ 
\vspace{3ex}
\end{tabular}
\footnotesize
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{9}{c|}{$\m T_9$} \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_7$} \\ \hline
\mc{2}{|c|}{$\m T_3$}&\grn2-&\mc{4}{c|}{$\m T_6$}&\mc{4}{c|}{$\m T_8$} \\ \hline
&&&&&&&&&&&  
\end{tabular}
\normalsize
\caption{\label{abra:anom1} A $\tau_1$ taszkrendszer, \'es annak optim\'alis
\"utemez\'ese}
\end{center}
\end{figure}
\end{pelda}
\begin{pelda}
\"Utemezz\"uk az el\H obbi $\tau_1$ taszkrendszert $m=3$ azonos processzorra az
$L'=(\m T_1,\m T_2,\m T_4,\m T_5,\m T_6,\m T_3,\m T_9,\m T_7,\m T_8)$ list\'aval.
Ekkor a kapott $S_2$ \"utemez\'esre (\ref{abra:S2 utemezes}.\ \'abra) $\Fmax(S_2)=14$.
\begin{figure}[!h]
\begin{center}
\parbox[5ex]{2em}{$S_2:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ 
\vspace{3ex}
\end{tabular}
\footnotesize
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{13} l !{12} l !{14}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{2}{c|}{$\m T_3$}&\mc{9}{c|}{$\m T_9$} \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_7$}&\grn4- \\\hline
\mc{2}{|c|}{$\m T_4$}&\mc{4}{c|}{$\m T_6$}&\mc{4}{c|}{$\m T_8$}&\grn4- \\\hline
&&&&&&&&&&&&&  
\end{tabular}
\normalsize
\caption{\label{abra:S2 utemezes} A $\tau_1$ taszkrendszer \"utemez\'ese
az $L'$ lista eset\'en}
\end{center}
\end{figure}
\end{pelda}
\begin{pelda}
\"Utemezz\"uk a $\tau_1$ taszkrendszert az $L$ list\'aval $m'=4$ processzorra. Az
eredm\'eny $\Fmax(S_3)=15$ (ld.\ \ref{abra:S3 utemezes}.\ \'abra).
\begin{figure}[!h]
\begin{center}
\parbox[5ex]{2em}{$S_3:$\vspace{3ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ \\
$P_4$
\vspace{3ex}
\end{tabular}
\footnotesize
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{13} l !{12} l !{14} l !{15}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_5$}&\grn8- \\ \hline
\mc{2}{|c|}{$\m T_2$}&\mc{4}{c|}{$\m T_6$}&\mc{9}{c|}{$\m T_9$} \\\hline
\mc{2}{|c|}{$\m T_3$}&\mc{4}{c|}{$\m T_7$}&\grn9- \\\hline
\mc{2}{|c|}{$\m T_4$}&\mc{4}{c|}{$\m T_8$}&\grn9- \\\hline
&&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S3 utemezes} $\tau_1$ \"utemez\'ese
az $L$ list\'aval $m'=4$ processzorra}
\end{center}
\end{figure}
\end{pelda}
\begin{pelda}
Cs\"okkents\"uk $\tau_1$-ben a v\'egrehajt\'asi id\H oket eggyel. \"Utemezz\"uk az \'\i gy kapott
$\tau_2$ taszkrendszert az $L$ list\'aval $m=3$ processzorra. Az eredm\'eny:
$\Fmax(S_4)=13$ (ld.\ \ref{abra:S4 utemezes}.\ \'abra).
\begin{figure}[!h]
\begin{center}
\parbox[5ex]{2em}{$S_4:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ 
\vspace{3ex}
\end{tabular}
\footnotesize
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12} l !{13}}
\hline
\mc{2}{|c|}{$\m T_1$}&\mc{3}{c|}{$\m T_5$}&\mc{3}{c|}{$\m T_8$}&\grn5- \\\hline
\mc{1}{|c|}{$\m T_2$}&\mc{1}{c|}{$\m T_4$}&\mc{3}{c|}{$\m T_6$}&\mc{8}{c|}{$\m T_9$} \\ \hline
\mc{1}{|c|}{$\m T_3$}&\gr-&\mc{3}{c|}{$\m T_7$}&\grn8- \\ \hline
&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S4 utemezes} $\tau_2$ \"utemez\'ese az $L$ list\'aval
$m=3$ processzorra}
\end{center}
\end{figure}
\end{pelda}
\begin{pelda}
Enyh\'\i ts\"uk a $\tau_1$ taszkrendszerben a precedencia-korl\'atoz\'asokat: hagyjuk
el a $(\m T_4,\m T_5)$ \'es a $(\m T_4,\m T_6)$ \'eleket a gr\'afb\'ol.
Az \'\i gy kapott $\tau_3$ taszkrendszer $S_5$ \"utemez\'es\'enek eredm\'enye \aref{abra:S5 utemezes}.\ \'abr\'an l\'athat\'o:
$\Fmax(S_5)=16$.
\begin{figure}[!h]
\begin{center}
\parbox[5ex]{2em}{$S_5:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ \\
$P_3$ 
\vspace{3ex}
\end{tabular}
\footnotesize
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l !{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_6$}&\mc{9}{c|}{$\m T_9$} \\\hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_7$}&\grn8- \\\hline
\mc{2}{|c|}{$\m T_3$}&\mc{4}{c|}{$\m T_5$}&\mc{4}{c|}{$\m T_8$}&\grn6- \\\hline
&&&&&&&&&&&&&&&
\end{tabular}
\normalsize
\caption{\label{abra:S5 utemezes} A $\tau_3$ taszkrendszer \"utemez\'ese
$m=3$ processzorra}
\end{center}
\end{figure}
\end{pelda}

A k\"ovetkez\H o p\'elda azt mutatja, hogy \Fmax\ n\"oveked\'ese nem csak a lista rossz
megv\'alaszt\'asa miatt k\"ovetkezhet be.
\begin{pelda}
Legyen a $\tau$ taszkrendszer \'es annak $S_\m{OPT}$ optim\'alis \"utemez\'ese
\aref{abra:anom2}.\ \'abra szerinti. Ekkor $\Fmax(S_\m{OPT})=19$.
\begin{figure}[!h]
\begin{center}
\begin{tabular}{l}
\resizebox{4.5cm}{!}{ \includegraphics{anom2.eps} }
\end{tabular}
\parbox[5ex]{2em}{$S_\m{OPT}:$\vspace{2.5ex}}
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\vspace{3ex}
\end{tabular}
\hspace{-3ex}
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16} l !{17} l !{18}
l !{19}}
\hline
\mc{4}{|c|}{$\m T_1$}&\mc{5}{c|}{$\m T_4$}&\mc{10}{c|}{$\m T_6$} \\\hline
\mc{2}{|c|}{$\m T_2$}&\mc{2}{c|}{$\m T_3$}&\mc{5}{c|}{$\m T_5$}&\mc{10}{c|}{$\m T_7$} \\\hline
&&&&&&&&&&&&&&&&&&  
\end{tabular}
\normalsize
\caption{\label{abra:anom2} A $\tau$ taszkrendszer, \'es annak $S_\m{OPT}$
\"utemez\'ese k\'et processzoron}
\end{center}
\end{figure}

K\"onnyen bel\'athat\'o, hogy ha most a v\'egrehajt\'asi id\H oket 1-gyel cs\"okkentj\"uk, akkor
a kapott $\tau'$ taszkrendszeren $\Fmax(S_6)=20$ \'ert\'ekn\'el egyetlen list\'aval sem
\'erhet\"unk el jobbat
(\ref{abra:anom3}.\ \'abra).
\begin{figure}[!h]
\begin{center}
\parbox[5ex]{2em}{$S_6:$\vspace{2.5ex}}
\hspace{-2ex}
\begin{tabular}{l}
$P_1$ \\
$P_2$ 
\vspace{3ex}
\end{tabular}
\hspace{-3ex}
\footnotesize
\setlength{\tabcolsep}{3pt}
\begin{tabular}{!{0} l !{1} l !{2} l !{3} l !{4} l !{5} l !{6} l !{7} l !{8} l
!{9} l !{10} l !{11} l !{12} l !{13} l !{14} l !{15} l !{16} l !{17} l !{18}
l !{19} l !{20}}
\hline
\mc{3}{|c|}{$\m T_1$}&\mc{4}{c|}{$\m T_4$}&\mc{4}{c|}{$\m T_5$}&\mc{9}{c|}{$\m T_7$} \\\hline
\mc{1}{|c|}{$\m T_2$}&\mc{1}{c|}{$\m T_3$}&\mc{9}{c|}{$\m T_6$}&\grn9- \\\hline
&&&&&&&&&&&&&&&&&&&  
\end{tabular}
\normalsize
\caption{\label{abra:anom3} A $\tau'$ taszkrendszer optim\'alis list\'as
\"utemez\'ese}
\end{center}
\end{figure}
\end{pelda}

Ezen p\'eld\'ak ut\'an az \"utemez\'esi param\'eterek hat\'as\'at jellemz\H o relat\'\i v korl\'atot
adunk meg. Tegy\"uk fel, hogy adott $\tau$ \'es $\tau'$ taszkrendszerekre $\T'=\T$,
$<'\,\subseteq\,<$, $\t'\le\t$. A $\tau$ taszkrendszert egy $L$, a $\tau'$
taszkrendszert pedig egy $L'$ lista alkalmaz\'as\'aval \"utemezz\"uk --- m\'egpedig
el\H obbit $m$, ut\'obbit pedig $m'$ azonos processzorra. Az \'\i gy kapott
$S$, illetve\ $S'$ \"utemez\'esekre legyen $\Fmax(S)=F$ \'es $\Fmax(S')=F'$.
\begin{tetel}
A fenti felt\'etelek mellett $\displaystyle{\frac{F'}F \le 1+\frac{m-1}{m'}}$.
\end{tetel}
\begin{biz}
Tekints\"uk a vessz\H os param\'eterekhez ($S'$-h\"oz) tartoz\'o $D'$ \"utemez\'esi diagramot.
Legyen a $[0,F')$ intervallum pontjainak k\'et -- $A$ \'es $B$ -- r\'eszhalmaz\'anak
defin\'\i ci\'oja a k\"ovetkez\H o: $A=\{t\in[0,F)\mid$ a $t$ id\H opontban minden
processzor foglalt$\}$, $B=[0,F')\setminus A$. \'Erdemes megeml\'\i teni, hogy mindk\'et
halmaz diszjunkt, f\'elig ny\'\i lt (balr\'ol z\'art, jobbr\'ol ny\'\i lt) intervallumok uni\'oja.
\\[1ex]
Legyen $\m T_{j_1}$ egy olyan taszk, melynek a v\'egrehajt\'asa $D'$ szerint az
$F'$ id\H opontban fejez\H odik be (azaz $f_{j_1}=F'$). Ekkor k\'et lehet\H os\'eg van:
a $\m T_{j_1}$ taszk $s_{j_1}$ kezd\H opontja vagy $B$ bels\H o pontja, vagy nem az.
\begin{enumerate}
\item Ha $s_{j_1}$ $B$ bels\H o pontja, akkor $B$ defin\'\i ci\'oja szerint van olyan
processzor, amelyre $\varepsilon>0$ mellett igaz, hogy az
$[s_{j_1}-\varepsilon, s_{j_1})$ intervallumban nem dolgozik. Ez azonban csak
\'ugy fordulhat el\H o, ha van olyan $\m T_{j_2}$ taszk, amelyre
$\m T_{j_2}<\m T_{j_1}$ \'es $f_{j_2}=s_{j_1}$ (a eset).
\item Ha $s_{j_1}$ nem bels\H o pontja $B$-nek, akkor vagy $s_{j_1}=0$ (b eset),
vagy $s_{j_1}>0$. Ha van $B$-nek $s_{j_1}$-n\'el kisebb eleme (c eset), akkor
legyen $x_1=\sup\{x\mid x<s_{j_1}\ \m{\'es}\ x\in B\}$, egy\'ebk\'ent pedig legyen 
$x_1=0$ (d eset). Ha $x_1>0$, akkor $A$ \'es $B$ konstrukci\'oj\'ab\'ol k\"ovetkezik, hogy
van olyan processzor, amelyhez tala\'alhat\'o olyan $\m T_{j_2}$ taszk, amelynek
ebben az intervallumban m\'eg tart a v\'egrehajt\'asa, \'es amelyre $\m T_{j_2}<\m
T_{j_1}$.
\end{enumerate}
A k\'et esetet \"osszegezve teh\'at vagy van olyan $\m T_{j_2}<\m T_{j_1}$ taszk,
amelyre $y\in[f_{j_2}, s_{j_1})$ eset\'en $y\in A$ (a vagy c eset), vagy pedig
minden $x<s_{j_1}$ sz\'amra $x\in A$ \'es $x<0$ egyike fenn\'all (a vagy d eset).
\\[1ex]
Ezt az az elj\'ar\'ast ism\'etelve olyan $\m T_{j_r}, \m T_{j_{r-1}}, \dots, \m
T_{j_1}$ taszkl\'anchoz jutunk, amelyre igaz, hogy $x<s_{j_r}$ eset\'en vagy
$x\in A$ vagy $x<0$. Ezzel megmutattuk, hogy l\'eteznek olyan taszkok, amelyekre
\begin{equation}
\label{eq:Tj-k <' lanca}
\m T_{j_r} <' \m T_{j_{r-1}} <' \dots <' \m T_{j_1},
\end{equation}
tov\'abb\'a minden $t\in B$ id\H opontban van olyan processzor, amelyik dolgozik, \'es
\'eppen a l\'anc valamelyik elem\'et hajtja v\'egre. Ebb\H ol k\"ovetkezik, hogy
\begin{equation}
\label{eq:ures periodusok}
\sum_{\phi\in S'} t'(\phi) \le (m'-1)\sum_{k=1}^r t'_{j_k},
\end{equation}
ahol $\phi$-vel az \"ures peri\'odusokat jel\"olt\"uk, \'es \'\i gy a baloldali \"osszeg az
$S'$-ben l\'ev\H o \"osszes \"ures peri\'odusra vonatkozik.
\\[1ex]
(\ref{eq:Tj-k <' lanca}) \'es $<'\,\subseteq\,<$ alapj\'an $\m T_{j_r} < \m
T_{j_{r-1}} < \dots < \m T_{j_1}$, \'es \'\i gy
\begin{equation}
\label{eq:lancok osszideje}
F\ge\sum_{k=1}^r t_{j_k}\ge\sum_{k=1}^r t'_{j_k}.
\end{equation}
Mivel
\begin{equation}
\label{eq:taszkok osszideje}
mF \ge \sum_{i=1}^n t_i \ge \sum_{i=1}^n t'_i,
\end{equation}
\'es $\displaystyle{F'=\frac1{m'}\left(\sum_{k=1}^n t'_k + \sum_{\phi\in S'} t'(\phi)\right)}$,
\'\i gy (\ref{eq:ures periodusok}), (\ref{eq:lancok osszideje}) \'es (\ref{eq:taszkok
osszideje}) alapj\'an 

\noindent $\displaystyle{F'\le\frac1{m'}\Big(mF+(m'-1)F\Big)}$, ahonnan
$\displaystyle{\frac{F'}F\le1+\frac{m-1}{m'}}$.
\end{biz}

A k\"ovetkez\H o p\'eld\'ak nemcsak azt mutatj\'ak meg, hogy a t\'etelben szerepl\H o korl\'at a
lehet\H o legjobb, hanem azt is, hogy az adott korl\'at (legal\'abbis aszimptotikusan)
a param\'eterek b\'armelyik\'enek v\'altoztat\'as\'aval el\'erhet\H o.

\section{\"Utemez\'esi anom\'ali\'ak II.}
\begin{pelda}
Ebben a p\'eld\'aban a lista v\'altozik, < \"ures, $m$ tetsz\H oleges. A v\'egrehajt\'asi id\H ok
a k\"ovetkez\H ok: 
\[t_i=\left\{
\begin{array}{ll}
 1,  & \m{ha}\ i=1,\dots,m-1; \\
 m,  & \m{ha}\ i=m; \\
 m-1,& \m{ha}\ i=m+1,\dots,2m-1.
\end{array}\right.\]
Ha ezt  a $\tau_4$ taszkrendszert $m$ processzorra az $L=(\m T_1,\dots,\m T_n)$
list\'aval \"utemezz\"uk, akkor \aref{abra:tau4 L listaval}.\ \'abr\'an l\'ev\H o $S_7(\tau_4)$
optim\'alis \"utemez\'est kapjuk.
\begin{figure}[!h]
\begin{center}
$S_7:$
\footnotesize
\begin{tabular}{|*2{c|}}
\hline
$\m T_1$&\parbox{12em}{\hspace{4.75em}$\m T_{m+1}$} \\\hline
$\m T_2$&$\m T_{m+2}$    \\\hline
$\vdots$&$\vdots$         \\\hline
$\m T_{m-1}$&$\m T_{2m-1}$ \\\hline
\mc{2}{|c|}{$\m T_m$}       \\\hline
\end{tabular}
\normalsize
\caption{\label{abra:tau4 L listaval} Az $L=(\m T_1,\dots,\m T_n)$ list\'ahoz
tartoz\'o $S_7(\tau_4)$ \"utemez\'es}
\end{center}
\end{figure}

Ha az $L$ lista helyett az
$L'=(\m T_{m+1},\dots,\m T_{2m-1},\m T_1,\dots,\m T_{m-1},\m T_m)$
list\'at alkalmazzuk, akkor \aref{abra:tau4 L' listaval}.\ \'abr\'an l\'athat\'o
$S_8(\tau_4)$ \"utemez\'est kapjuk.
\begin{figure}[!h]
\begin{center}
$S_8:$
\footnotesize
\begin{tabular}{|*5{c|}}
\hline
\mc{4}{|c|}{$\m T_{m+1}$}&\parbox{12em}{\hspace{5.4em}$\m T_m$} \\\hline
\mc{4}{|c|}{$\m T_{m+2}$}&\gr-              \\\hline
\mc{4}{|c|}{$\vdots$}&\gr{$\vdots$}          \\\hline
\mc{4}{|c|}{$\m T_{2m-1}$}&\gr-               \\\hline
$\m T_1$ & $\m T_2$ &\dots& $\m T_{m-1}$ &\gr- \\\hline
\end{tabular}
\normalsize
\caption{\label{abra:tau4 L' listaval} Az $L'$ list\'ahoz tartoz\'o $S_8(\tau_4)$
\"utemez\'es}
\end{center}
\end{figure}
Ebben az esetben $F=\Fmax(S_7)=m$, $F'=\Fmax(S_8)=2m-1$, \'\i gy
$\frac{F'}F=2-\frac1m$; teh\'at a lista v\'altoztat\'as\'aval el\'ert\"uk, hogy a t\'etel
\'all\'\i t\'as\'aban az egyenl\H os\'eg teljes\"ulj\"on, vagyis a $\le$ jel jobb oldal\'an szerepl\H o
kifejez\'es nem cs\"okkenthet\H o.
\end{pelda}

\begin{pelda}
Ebben a p\'eld\'aban a v\'egrehajt\'asi id\H oket cs\"okkentj\"uk. A lista mindk\'et esetben az
$L=L'=(\m T_1,\dots,\m T_n)$. Itt \'es a fejezet tov\'abbi r\'esz\'eben $\varepsilon$
tetsz\H oleges kis pozit\'\i v sz\'amot jel\"ol. Az eredeti v\'egrehajt\'asi id\H oket a
$\t=(t_1,\dots,t_n)$ vektor tartalmazza, ahol
\[t_i=\left\{
\begin{array}{ll}
 2,\varepsilon & \m{ha}\ i=1,\dots,m; \\
 1,            & \m{ha}\ i=m+1,\dots,2m; \\
 m-1,& \m{ha}\ i=2m+1,\dots,3m.
\end{array}\right.\]
Az \'uj v\'egrehajt\'asi id\H ok pedig:
\[t'_i=\left\{
\begin{array}{ll}
 t_i-\varepsilon, & \m{ha}\ i=1,\dots,m-1; \\
 t_i,             & \m{ha}\ i=m,\dots,3m.
\end{array}\right.\]
A $\tau_5$, illetve\ a m\'odos\'\i tott $\tau_5'$ taszkrendszer megel\H oz\'esi gr\'afj\'at
\aref{abra:anom3}.\ \'abra mutatja,
az $S_9(\tau_5)$ (optim\'alis) \"utemez\'es \'es az $S_{10}(\tau_5')$ \"utemez\'es pedig
\aref{abra:S9, S10}.\ \'abr\'an l\'athat\'o.
\begin{figure}[!h]
\begin{center}
\resizebox{11.5cm}{!}{ \includegraphics{anom3.eps} }
\end{center}
\caption{\label{abra:anom3} $\tau_5$ \'es $\tau_5'$ azonos gr\'afja}
\end{figure}
\begin{figure}[!h]
\begin{center}
$S_9:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*3{c|}}
\hline
$\m T_1$&\parbox{4em}{\hspace{0.5em}$\m T_{m+1}$}&\parbox{14em}{\hspace{5.5em}$\m T_{2m+1}$} \\\hline
$\m T_2$&\parbox{4em}{\hspace{0.5em}$\m T_{m+2}$}&\parbox{14em}{\hspace{5.5em}$\m T_{2m+2}$} \\\hline
$\vdots$&$\vdots$&$\vdots$ \\\hline
$\m T_{m-1}$&\parbox{4em}{\hspace{0.5em}$\m T_{2m-1}$}&\parbox{14em}{\hspace{5.5em}$\m T_{3m-1}$} \\\hline
$\m T_m$&\parbox{4em}{\hspace{0.5em}$\m T_{2m}$}&\parbox{14em}{\hspace{5.5em}$\m T_{3m}$} \\\hline
\end{tabular}
\end{center}
\begin{center}
\normalsize
$S_{10}:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*8{c|}}
\hline
$\m T_1$&\mc{4}{c|}{\parbox{14.5em}{\hspace{5.5em}$\m T_{2m}$}}&\mc{2}{c|}{\parbox{5.5em}{\hspace{0.9em}$\m T_{2m-1}$}}&\parbox{14.5em}{\hspace{5.5em}$\m T_{2m+1}$} \\\hline
$\m T_2$&\mc{4}{c|}{\parbox{14.5em}{\hspace{5.5em}$\m T_{2m+3}$}}&\grn3- \\\hline
$\vdots$&\mc{4}{c|}{$\vdots$}&\grn3{$\vdots$} \\\hline
$\m T_{m-1}$&\mc{4}{c|}{\parbox{14.5em}{\hspace{6em}$\m T_{3m}$}}&\grn3- \\\hline
\mc{2}{|c|}{\parbox{3.5em}{\hspace{1em}$\m T_m$}}&\parbox{5.5em}{\hspace{1.5em}$\m T_{m+1}$}&\parbox{6em}{\hspace{2.5em}$\dots$}&\mc{2}{c|}{\parbox{5.5em}{\hspace{0.9em}$\m T_{2m-1}$}}&\grn2- \\\hline
\end{tabular}
\normalsize
\caption{\label{abra:S9, S10} Az $S_9(\tau_5)$ \'es $S_{10}(\tau_5')$ \"utemez\'esek}
\end{center}
\end{figure}
Itt $F=\Fmax(S_9(\tau_5))=m+2\varepsilon$ \'es
$F'=\Fmax(S_{10}(\tau_5')=2m-1+\varepsilon$, ez\'ert $\varepsilon$ cs\"okken\'es\'evel
$\frac{F'}F$ tart a $2-\frac1m$ \'ert\'ekhez
($\lim_{\varepsilon\rightarrow0}\frac{F'}F=2-\frac1m$). Teh\'at a v\'egrehajt\'asi
id\H oket v\'altoztatva tetsz\H olegesen megk\"ozel\'\i thetj\"uk a t\'etelben szerepl\H o korl\'atot.
\end{pelda}
\begin{pelda}
Ebben a p\'eld\'aban a megel\H oz\'esi korl\'atoz\'asokat gyeng\'\i tj\"uk. A $\tau_6$
taszkrendszer megel\H oz\'esi gr\'afj\'at \aref{abra:anom4}.\ \'abra mutatja.
\begin{figure}[!h]
\begin{center}
\resizebox{8cm}{!}{ \includegraphics{anom4.eps} }
\end{center}
\caption{\label{abra:anom4} A $\tau_6$ taszkrendszer gr\'afja}
\end{figure}
A taszkok
v\'egrehajt\'asi ideje pedig: $t_1=\varepsilon$, $t_i=1$, ha $i=1,\dots,m^2-m+1$, \'es
$t_{m^2-m+2}=m$. $\tau_6$-nak az $L=(\m T_1,\dots,\m T_{m^2-m+2})$ list\'ahoz
tartoz\'o, optim\'alis $S_{11}(\tau_6)$ \"utemez\'es\'et \aref{abra:S11}.\ \'abra
tartalmazza. Az \"osszes megel\H oz\'esi korl\'atoz\'as elhagy\'as\'aval kapjuk $\tau_6$-b\'ol a
$\tau_6'$ taszkrendszert. \Aref{abra:S12}.\ \'abra mutatja az $S_{12}(\tau_6')$
\"utemez\'est.
\begin{figure}[!h]
\begin{center}
$S_{11}:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*6{c|}}
\hline
$\m T_1$&\parbox{5em}{\hspace{1.5em}$\m T_2$}&\parbox{5em}{\hspace{1em}$\m T_{m+1}$}&\dots&\mc2{c|}{\parbox{5em}{\hspace{.2em}$\m T_{m^2-2m+2}$}} \\\hline
\mc5{|c|}{\parbox{17.7em}{\hspace{7em}$\m T_{m^2-m+2}$}} & \gr- \\\hline
\fgr-&\parbox{5em}{\hspace{1.5em}$\m T_3$}&\parbox{5em}{\hspace{1em}$\m T_{m+2}$}&\dots&\mc2{c|}{\parbox{5em}{\hspace{.2em}$\m T_{m^2-2m+3}$}} \\\hline
\fgr{$\vdots$}& $\vdots$ & $\vdots$ & $\ddots$ & \mc2{c|}{$\vdots$} \\\hline
\fgr-&\parbox{5em}{\hspace{1.5em}$\m T_m$}&\parbox{5em}{\hspace{1em}$\m T_{2m-1}$}&\dots&\mc2{c|}{\parbox{5em}{\hspace{.2em}$\m T_{m^2-m+1}$}} \\\hline
\end{tabular}
\end{center}
\caption{\label{abra:S11} Az $S_{11}(\tau_6)$ optim\'alis \"utemez\'es}
\end{figure}
\begin{figure}[!h]
\begin{center}
$S_{12}:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*8{c|}}
\hline
$\m T_1$&\mc2{c|}{\parbox{5em}{\hspace{1em}$\m T_{m+1}$}} &\mc2{c|}{\parbox{5em}{\hspace{2em}\dots}}& \mc2{c|}{\parbox{5em}{\hspace{.2em}$\m T_{m^2-m+1}$}} & \gr- \\\hline
\mc2{|c|}{\parbox{5em}{\hspace{1.8em}$\m T_2$}}&\mc2{c|}{\parbox{5em}{\hspace{1.2em}$\m T_{m+2}$}} &\mc2{c|}{\parbox{5em}{\hspace{2em}\dots}}& \mc2{c|}{\parbox{13em}{\hspace{4em}$\m T_{m^2-m+2}$}} \\\hline
\mc2{|c|}{\parbox{5em}{\hspace{1.8em}$\m T_3$}}&\mc2{c|}{\parbox{5em}{\hspace{1.2em}$\m T_{m+3}$}} &\mc2{c|}{\parbox{5em}{\hspace{2em}\dots}}& \grn2- \\\hline
\mc2{|c|}{$\vdots$} & \mc2{c|}{$\vdots$} & \mc2{c|}{$\ddots$} & \grn2{$\vdots$} \\\hline
\mc2{|c|}{\parbox{5em}{\hspace{1.2em}$\m T_{m-1}$}}&\mc2{c|}{\parbox{5em}{\hspace{1em}$\m T_{2m+1}$}}&\mc2{c|}{\parbox{5em}{\hspace{2em}\dots}}&\grn2- \\\hline
\mc2{|c|}{\parbox{5em}{\hspace{1.8em}$\m T_m$}}&\mc2{c|}{\parbox{5em}{\hspace{1.5em}$\m T_{2m}$}} &\mc2{c|}{\parbox{5em}{\hspace{2em}\dots}}& \grn2- \\\hline
\end{tabular}
\end{center}
\caption{\label{abra:S12} Az $S_{12}(\tau_6')$ \"utemez\'es}
\end{figure}
\end{pelda}

\begin{pelda}
Ez\'uttal a processzorok sz\'am\'at n\"ovelj\"uk: $m$-r\H ol $m'$-re.
A $\tau_7$ taszkrendszer gr\'afj\'at
\aref{abra:anom5}.\ \'abra mutatja, a v\'egrehajt\'asi id\H ok pedig:
\[t_i=\left\{
\begin{array}{ll}
 \varepsilon, & \m{ha}\ i=1,\dots,m+1; \\
 1,           & \m{ha}\ i=m+2,\dots,mm'-m'+m+1; \\
 m',          & \m{ha}\ i=mm'-m'+m+2.
\end{array}\right.\]
A taszkrendszer optim\'alis \"utemez\'es\'et $m$, illetve $m'$ processzoron
\aref{abra:S13}.\, illetve \aref{abra:S14}.\ \'abra mutatja. A maxim\'alis befejez\'esi
id\H oket \"osszehasonl\'\i tva itt is a k\'\i v\'ant aszimptotikus \'ert\'eket kapjuk:
$F=\Fmax(S_{13}(\tau_7))=m'+2\varepsilon$,
$F'=\Fmax(S_{14}(\tau_7))=m'+m-1+\varepsilon$, \'\i gy
$\frac{F'}F=1+\frac{m-1-\varepsilon}{m'+2\varepsilon}$, valamint
$\lim_{\varepsilon\rightarrow0}=\frac{F'}F=1+\frac{m-1}{m'}$.
%$<2-\frac1m<2$.
\begin{figure}[!ht]
\begin{center}
\resizebox{12cm}{!}{ \includegraphics{anom5.eps} }
\end{center}
\caption{\label{abra:anom5} $\tau_7$ r\'ak\"ovetkez\'esi gr\'afja}
\end{figure}
\begin{figure}[!ht]
\begin{center}
$S_{13}:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*6{c|}}
\hline
$\m T_1$&$\m T_{m+1}$&\parbox{5em}{\hspace{1em}$\m T_{m+2}$}&\parbox{10em}{\hspace{4.36em}\dots}&\mc2{c|}{\parbox{5em}{\hspace{1.8em}$\m T_a$}} \\\hline
$\m T_2$&\mc{4}{c|}{\parbox{22em}{\hspace{8em}$\m T_{mm'-m'+2}$}}&\gr- \\\hline
$\m T_3$&\gr-&\parbox{5em}{\hspace{1em}$\m T_{m+3}$}&\parbox{10em}{\hspace{4.36em}\dots}&\mc2{c|}{\parbox{5em}{\hspace{1.8em}$\m T_b$}} \\\hline
$\vdots$&\gr{$\vdots$}&$\vdots$&$\ddots$&\mc2{c|}{$\vdots$} \\\hline
$\m T_m$&\gr-&\parbox{5em}{\hspace{1.4em}$\m T_{2m}$}&\parbox{10em}{\hspace{4.36em}\dots}&\mc2{c|}{\parbox{5em}{\hspace{1.8em}$\m T_c$}} \\\hline
\end{tabular}
\end{center}
\caption{\label{abra:S13} Az $S_{13}(\tau_7)$ optim\'alis \"utemez\'es ($a=mm'-m'+3$,
$b=a+1$, $c=mm'-m'+m+1$)}
\end{figure}
\begin{figure}[!ht]
\begin{center}
$S_{14}:$
\footnotesize
\setlength{\tabcolsep}{2pt}
\begin{tabular}{|*5{c|}}
\hline
$\m T_1$&\parbox{5em}{\hspace{1em}$\m T_{m+2}$} &\parbox{5em}{\hspace{2em}\dots}& \parbox{5em}{\hspace{1.7em}$\m T_a$} & \parbox{13em}{\hspace{3.7em}$\m T_{mm'-m'+m+2}$} \\\hline
$\m T_2$&\parbox{5em}{\hspace{1em}$\m T_{m+3}$} &\parbox{5em}{\hspace{2em}\dots}& \parbox{5em}{\hspace{1.2em}$\m T_{a+1}$} & \gr- \\\hline
$\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & \gr{$\vdots$} \\\hline
$\m T_b$&\parbox{5em}{\hspace{1.7em}$\m T_c$} &\parbox{5em}{\hspace{2em}\dots}& \parbox{5em}{\hspace{1.7em}$\m T_d$} & \gr- \\\hline
\fgr-& $\vdots$ & $\ddots$ & $\vdots$ & \gr{$\vdots$} \\\hline
\fgr-&\parbox{5em}{\hspace{1.7em}$\m T_e$} &\parbox{5em}{\hspace{2em}\dots}& \parbox{5em}{\hspace{1.7em}$\m T_f$} & \gr- \\\hline
\end{tabular}
\end{center}
\caption{\label{abra:S14} Az $S_{14}(\tau_7)$ optim\'alis \"utemez\'es ($a=mm'-2m'+m+2$, $b=m+1$, $c=2m+2$, $d=mm'-2m'+2m+2$, $e=m+m'+1$, $f=mm'-m'+m+1$)}
\end{figure}
\end{pelda}


Ezekkel a p\'eld\'akkal bebizony\'\i tottuk a k\H ovetkez\H o t\'etelt.
\begin{tetel}
A 3.4. tételben szerepl\H o korl\'at a négy param\'eter $(\mathbf{t}, \ m, <, L)$ b\'armelyik\'enek a 
v\'altoztat\'as\'as\'aval tetsz\'es szerinti pontoss\'aggal megk\"ozel\'\i thet\H o.
\end{tetel}


\chapter{PROCESSZORSZÁM MINIMALIZÁLÁSA}


Ebben a fejezetben egy olyan ütemezési feladatot tárgyalunk, amelyben a 
taszkok határidõre való végrehajtásához szükséges processzorok számának minimalizálása a cél.

A feladat a következõ: $\pi = (\rho, \tau, \mu)$, $\rho = \{ \mathcal{P} \}$, $\mathcal{P} = \{ P_1, \ P_2, 
\ldots \}$, $\tau = (\mathcal{T}, \mathbf{t}, \mathbf{d})$, $\mu = N_{\textit{proc}}$, a processzorok azonosak, 
a taszkok megszakíthatatlanok, a határidõk szigorúak és $\mathbf{d} = (1, 1, \ldots)$, a 
végrehajtási idõkre pedig teljesül $0 < t_i \leq 1 \ (i = 1, \ 2, \ldots, n)$. 

Ebben az anyagban technikai okok miatt a feladatot olyan memóriakezelési feladatként tárgyaljuk,
 amelyben ismert méretû fájlokat kell elhelyezni adott méretû lemezeken és a cél 
 a felhasznált lemezek számának minimalizálása.
 
Adott a fájlok $n$ száma, valamint az elhelyezendõ fájlok méretét tartalmazó 
$\mathbf{t} = (t_1, t_2, \ldots, t_n)$ vektor, melynek elemeire teljesül 
$0 < t_i \leq 1 \ (i = 1, 2, \ldots, n).$ A fájlokat úgy kell elhelyezni a lemezeken, hogy 
nem szabad õket részekre bontani és figyelembe kell venni, hogy a lemezek kapacitása egységnyi.

\section{Közelítõ algoritmusok}
Az adott feladat NP-teljes. A gyakorlatban ezért különbözõ közelítõ algoritmusokat használnak. 

Ezeknek az algoritmusoknak a bemenõ adatai: a fájlok $n$ száma és a fájlméretek 
$\mathbf{t} = \langle t_1, t_2,\ldots,t_n \rangle$ vektora. 
A kimenõ adatok pedig a szükséges lemezek száma $(\var{lemezszám})$ és a lemezek 
$\mathbf{h} = \langle h_1, h_2, \ldots, h_n \rangle$ szintvektora.

A szereplõ pszeudokódokban a kimenõ adatokat nem adjuk meg paraméterként. Ezek a kódok nem csak 
a szükséges lemezek számát, hanem az egyes lemezek telítettségét is megadják.

\subsection{Lineáris algoritmus (LF)} 
A lineáris algoritmus (\textbf{L}inear \textbf{F}it) szerint az $F_i$ fájlt az $L_i$ lemezen helyezzük el. LF 
pszeudokódja a következõ. 

\begin{alg}{LF$(n,\mathbf{t})$}\inddef{\textsc{LF}} 
1 \'  \key{for} \= $i \leftarrow 1$ \key{to} $n$  \\ 
2 \'            \> \key{do} $h[i] \leftarrow  t[i]$ \\ 
3 \'  $\var{lemezszám} \leftarrow n$ \\
4 \'  \key{return} $\var{lemezszám}$
\end{alg}
 
Ennek az algoritmusnak mind a helyigénye, mind pedig a futási ideje $\Theta(n).$ Ha 
azonban a méretek beolvasását és a szintek nyomtatását az 1--2. sorokban lévõ ciklusban oldjuk meg, akkor 
a helyigény $\Theta(1)$-re csökkenthetõ. 

\subsection{Egyszerû algoritmus (NF)}\index{egyszerû algoritmus (NF)}
Az egyszerû algoritmus (\textbf{N}ext \textbf{F}it) addig rakja a fájlokat a soron következõ lemezre, amíg 
lehet. Pszeudokódja a következõ. 

\begin{alg}{NF$(n,\mathbf{t})$}\inddef{\textsc{NF}}\index{NF|see{egyszerû algoritmus}} 
1 \'  $h[1] \leftarrow t[1]$ \\ 
2 \'  $\textit{lemezszám} \leftarrow 1$ \\ 
3 \'  \key{for} \= $i \leftarrow 2$ \key{to} $n$  \\
4 \'            \> \key{do} \key{if} \= $h[\textit{lemezszám}] + t[i] \leq 1$ \= \\ 
5 \'            \>                   \> \key{then} \= $h[\textit{lemezszám}] \leftarrow h[\textit{lemezszám}] + t[i]$ \\
6 \'            \>                   \> \key{else} \> $\textit{lemezszám} \leftarrow \textit{lemezszám} + 1$ \\
7 \'            \>                   \>            \> $h[\textit{lemezszám}] \leftarrow t[i]$ \\
8 \' \key{return} $\var{lemezszám}$
\end{alg}
Ennek a algoritmusnak mind a helyfoglalása, mind pedig a futási ideje $\Theta(n).$ Ha a 
futási idõk beolvasását és a szintek kivitelét a 3--7. sorokban lévõ ciklusban oldjuk meg, 
akkor a helyfoglalás $\Theta(1)$-re csökkenthetõ, a futási idõ azonban $\Omega(n).$ 

\subsection{Mohó algoritmus (FF)}\index{mohó algoritmus (FF)}
A mohó algoritmus (\textbf{F}irst \textbf{F}it) a fájlokat rendre az elsõ olyan lemezen helyezi el, 
amelyikre ráférnek. 

\begin{algN}{FF$(n,\mathbf{t})$}\inddef{\textsc{FF}}\index{FF|see{mohó algoritmus}}
1 \' $\var{lemezszám} \ \leftarrow 1$ \\ 
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\ 
3 \'           \> \key{do} $h[i] \leftarrow  0$ 

\algnewpage
4 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$   \\ 
5 \'           \> \key{do} \= $k \leftarrow 1$ \\
6 \'           \>          \> \key{while} \= $t[i] + h[k] > 1$ \\ 
7 \'           \>          \>             \> \key{do} \= $k \leftarrow k + 1$ \\
8 \'           \>          \> $h[k] \leftarrow h[k] + t[i]$ \\ 
9 \'           \>          \> \key{if} \= $k > \var{lemezszám}$ \\ 
10 \'           \>          \>          \> \key{then} $\var{lemezszám} \leftarrow \var{lemezszám} + 1$ \\ 
11 \' \key{return} $\var{lemezszám}$
\end{algN} 
Ennek az algoritmusnak a helyigénye $\Theta(n),$ idõigénye pedig $O(n^2).$ Ha például minden fájlméret 1, akkor 
az algoritmus futási ideje $\Theta(n^2).$

\subsection{Gazdaságos algoritmus (BF)}\index{gazdaságos algoritmus (BF)} 
A gazdaságos algoritmus (\textbf{B}est \textbf{F}it) a fájlokat rendre a legelsõ olyan lemezre rakja, 
ahol a lehetõ legkisebb szabad kapacitás marad. 

\begin{algN}{BF$(n,\mathbf{t})$}\inddef{\textsc{BF}}\index{BF|see{gazdaságos algoritmus}} 
1 \' $\var{lemezszám} \leftarrow 1$ \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\ 
3 \'           \> \key{do} $h[i] \leftarrow 0$ \\ 
4 \' \key{for} \= $i \leftarrow 1$ \key{to} $n$  \\
5 \'           \> \key{do} \= $\var{szabad} \leftarrow 1.0$ \\
6 \'           \>          \> $\var{ind} \leftarrow 0$ \\ 
7 \'           \>          \> \key{for} \= $k \leftarrow 1$ \key{to} $\var{lemezszám}$  \\ 
8 \'           \>          \>           \> \key{do} \> \key{if} \= $h[k] + t[i] \leq 1$ 
                                és $1 - h[k] - t[i] < \var{szabad}$   \\ 
9 \'                       \>           \>          \>          \> \> \key{then} \= $\var{ind} \leftarrow k$ \\
10 \'                      \>           \>          \>          \>          \>  \> $\var{szabad} \leftarrow 1-h[k]-t[i]$ \\ 
11 \'          \>          \>           \>          \> \key{if} \= $\var{ind} > 0$ \= \\ 
12 \'          \>          \>          \>           \>          \> \key{then} \= $h[\var{ind}] \leftarrow h[\var{ind}] + t[i]$ \\ 
13 \'          \>          \>          \>           \>          \>            \> \key{else} \> $\var{lemezszám} \leftarrow  \var{lemezszám} + 1$ \\ 
14 \'          \>          \>          \>            \> $h[\var{lemezszám}] \leftarrow t[i]$ \\ 
15 \' \key{return} $\var{lemezszám}$
\end{algN}
Ennek az algoritmusnak a helyigénye $\Theta(n),$ futási ideje pedig $O(n^2).$ 

\subsection{Párosító algoritmus (PF)}\index{párosító algoritmus} 
A párosító algoritmus (\textbf{P}airwise \textbf{F}it) a méretvektor elsõ és utolsó elemébõl rendre párt 
képez, és a két fájlt -- a két méret összegének megfelelõen -- egy, illetve két lemezre rakja. 

A pszeudokódban két segédváltozó van: $\var{bind}$ az aktuális pár elsõ elemének indexe,  
$\var{eind}$ pedig az aktuális pár második elemének indexe. 

\begin{algN}{PF$(n,\mathbf{t})$}\inddef{\textsc{PF}}\index{PF|see{párosító algoritmus}}
1 \'  $\var{lemezszám} \leftarrow  0$ \\ 
2 \' $\var{bind} \leftarrow 1$ \\
3 \' $\var{eind} \leftarrow n$ \\
4 \' \key{while} \= $\var{eind} \geq \var{bind}$ \\ 
5 \'            \> \key{do} \= \key{if} \= $\var{eind} - \var{bind} \geq 1$ \\
6 \'            \>          \>          \> \key{then} \= \key{if} \= $t[\var{bind}] + t[\var{eind}] > 1$  \= \\  
7 \'            \>          \>          \>            \>          \> \key{then} \= $\var{lemezszám} \leftarrow \var{lemezszám} + 2$ \\
8 \'            \>          \>          \>            \>          \>            \> $h[\var{lemezszám} + 1] \leftarrow  t[\var{bind}]$ \\
10 \'           \>          \>          \>            \>          \>            \> $h[\var{lemezszám}] \leftarrow t[\var{eind}]$ \\
11 \'           \>          \>          \>            \> \key{else} \=  $\var{lemezszám} \leftarrow \var{lemezszám} + 1$ \\ 
12 \'           \>          \>          \>            \>            \> $h[\var{lemezszám}] \leftarrow t[\var{bind}] + t[\var{eind}]$ \\
13 \'           \>          \> \key{if} \= $\var{eind} = \var{bind}$ \= \\
14 \'           \>          \>          \> \key{then} \= $\var{lemezszám} \leftarrow  \var{lemezszám} + 1$ \\
15 \'           \>          \>          \>            \>$h[\var{lemezszám}] \leftarrow t[\var{eind}]$ \\
16 \'           \>          \>          \>            \>$\var{bind} \leftarrow \var{bind} + 1$ \\
17 \'           \>          \>          \>            \>$\var{eind} \leftarrow \var{eind} - 1$ \\
18 \' \key{return} $\var{lemezszám}$
\end{algN}

Ennek az algoritmusnak a helyigénye $\Theta(n),$ futási ideje $\Theta(n).$ Ha azonban a fájlméretek beolvasását és 
a lemezszintek kivitelét online módon megoldjuk, a helyigény csak $\Theta(1).$

\vspace{-0.5mm}
\subsection{Rendezõ egyszerû algoritmus (NFD)}\index{NFD|see{rendezõ 
egyszerû algoritmus}}\inddef{rendezõ egyszerû algoritmus (NFD)}
A következõ öt algoritmus két részbõl áll: elõször a végrehajtási idõk alapján csökkenõ 
sorrendbe rendezik a taszkokat (a rendezés eredménye az \textbf{s} vektor), 
majd a második részben a rendezett taszkokat ütemezik. 

A rendezõ egyszerû algoritmus (\textbf{N}ext \textbf{F}it \textbf{D}ecreasing) a rendezés után az egyszerû 
algoritmus (NF) szerint dolgozik. Így mind helyigénye, mind pedig idõigénye az alkalmazott 
rendezõ algoritmus és NF megfelelõ igényeibõl tevõdik össze. 

\vspace{-0.5mm}
\subsection{Rendezõ mohó algoritmus (FFD)}\index{FFD|see{rendezõ mohó algoritmus}} 
A rendezõ mohó algoritmus (\textbf{F}irst \textbf{F}it \textbf{D}ecreasing) a rendezés után a mohó algoritmus (FF) 
szerint dolgozik, így helyigénye $\Theta(n)$, idõigénye pedig $O(n^2)$. 

\vspace{-0.5mm}
\subsection{Rendezõ gazdaságos algoritmus (BFD)}\index{BFD|see{rendezõ gazdaságos algoritmus}} 
A rendezõ gazdaságos algoritmus\inddef{gazdaságos rendezõ algoritmus (BFD)} (\textbf{B}est \textbf{F}it 
\textbf{D}ecreasing)\index{BF} a rendezés után a gazdaságos algoritmus (BF) szerint dolgozik, így helyigénye 
$\Theta(n),$ idõigénye pedig $O(n^2).$ 

\vspace{-0.5mm}
\subsection{Rendezõ párosító algoritmus (PFD)}\index{PFD|see{rendezõ párosító algoritmus}} 
A rendezõ párosító algoritmus (\textbf{P}airwise \textbf{F}it \textbf{D}ecreasing) a rendezés után rendre párokat 
képez a legelsõ és legutolsó taszkokból, majd azokat lehetõleg egy processzorra (ha a végrehajtási 
idõk összege nem nagyobb egynél) ütemezi. Ha ez nem lehetséges, akkor az adott párt két processzorra ütemezi. 

\vspace{-0.5mm}
\subsection{Rendezõ gyors algoritmus (QFD)}\index{QFD|see{rendezõ gyors algoritmus}} 
A rendezõ gyors algoritmus (\textbf{Q}uick \textbf{F}it \textbf{D}ecreasing) a rendezés után rendre a legelsõ fájlt 
a soron következõ üres lemezre teszi, majd ehhez a fájlhoz mindaddig hozzáteszi a lehetõ legnagyobb fájlt 
(ezeket rendre a rendezett méretsorozat végétõl kezdi keresni), amíg ez lehetséges. 

A pszeudokódban használt munkaváltozók: $\var{bind}$ az elsõ vizsgálandó fájl indexe, $\var{eind}$  pedig 
az utolsó vizsgálandó fájl indexe. 

\begin{algN}{QFD$(n,\mathbf{t})$}\inddef{\textsc{QFD}}\index{rendezõ gyors algoritmus (QFD)} 
1 \' $\var{bind} \leftarrow 1$ \\ 
2 \' $\var{eind} \leftarrow n$ \\
3 \' $\var{lemezszám} \leftarrow 0$ \\ 
4 \' \key{while} \= $\var{eind} \geq  \var{bind}$ \\ 
5 \'             \> \key{do}    \= $\var{lemezszám} \leftarrow \var{lemezszám} + 1$ \\ 
6 \'             \>             \> $h[\var{lemezszám}] \leftarrow t[\var{bind}]$ \\
7 \'             \>             \> $\var{bind} \leftarrow \var{bind} + 1$ \\
8 \'             \> \key{while} \= $\var{eind} \geq \var{bind}$ és $h[\var{lemezszám}] + s[\var{eind}] \leq 1$  \\ 
9 \'             \>             \> \key{do} $\var{ind} \leftarrow \var{eind}$ \\
10 \'            \>             \> \key{while} \= $\var{ind} > \var{bind}$ és $h[\var{lemezszám}] + t[\var{ind} - 1] \leq 1$   \\ 
11 \'             \> \key{do} \= $\var{ind} \leftarrow \var{ind} - 1$ \\ 
12 \' $h[\var{lemezszám}] \leftarrow h[\var{lemezszám}] + t[\var{ind}]$  \\
13 \'            \> \key{if} \= $\var{eind} > \var{ind}$   \\
14 \'            \> \> \key{then} \= \key{for} \= $i \leftarrow  \var{ind}$ \key{to} $\var{eind} - 1$ \\ 
15 \'            \> \>            \>           \> \key{do} $t[i] \leftarrow  t[i + 1]$ \\
16 \'            \> $\var{eind} \leftarrow  \var{eind} - 1$ \\
17 \' \key{return} $\var{lemezszám}$
\end{algN}

Ennek a programnak a helyigénye $\Theta(n),$ futásideje kedvezõtlen esetben $\Theta(n^2),$ a 
gyakorlatban azonban -- egyenletes eloszlású végrehajtási idõk esetén --
körülbelül $\Theta(n \lg n).$ 




\section{Optimális algoritmusok} 
\subsection{Egyszerû hatvány típusú optimális algoritmus 
(SP)}\index{SP|see{egyszerû hatvány algoritmus}}\index{egyszerû hatvány algoritmus (SP)}
 
Ez az algoritmus a fájlokat rendre -- egymástól függetlenül -- $n$ lemez mindegyikére 
elhelyezi, így $n^n$ elhelyezést állít elõ, majd ezek közül kiválaszt egy optimálisat. Mivel ez az 
algoritmus minden elhelyezést elõállít (feltéve, hogy két elhelyezést azonosnak tekintünk, ha 
minden lemezhez ugyanazokat a fájlokat rendelik), így biztosan megtalálja az egyik 
optimális elhelyezést. 
\subsection{Faktoriális típusú optimális algoritmus (FACT)} 
Ez az algoritmus rendre elõállítja a fájlok permutációit (ezek száma $n!),$ majd az így 
kapott listákat helyezi el a NF segítségével. 

Az algoritmus optimalitása így látható be. Tekintsünk egy tetszõleges fájlrendszert 
és annak egy $S_{\textsc{OPT}}(\tau)$ optimális elhelyezését. 
$S_{\textsc{OPT}}(\tau)$ alapján állítsuk elõ a fájlok egy $P$ 
permutációját úgy, hogy rendre felsoroljuk a $P_1, P_2, \ldots, P_{\textsc{OPT}}(\tau)$ lemezekre elhelyezett  
fájlokat. Ha a $P$ permutációt az NF algoritmussal helyezzük el, akkor vagy $S_{\textsc{OPT}}$-hoz 
jutunk, vagy egy másik optimális elhelyezéshez (bizonyos taszkok esetleg eggyel kisebb indexû 
processzorra kerülnek). 
\subsection{Gyors hatványtípusú optimális algoritmus (QP)} 
Ez az algoritmus (\textbf{Q}uick \textbf{P}ower) azzal próbálja SP idõigényét csökkenteni, hogy a 
\idez{nagy} fájlokat (melyek mérete nagyobb, mint 0.5) eleve külön lemezre helyezi, és csak a többi 
fájl (a \idez{kicsi} fájlokat) próbálja mind az $n$ lemezre elhelyezni. Így $n^n$ helyett csak 
$n^K$ elhelyezést állít elõ, ahol $K$ a kicsi fájlok száma. 
\subsection{Gazdaságos hatványtípusú optimális algoritmus 
(EP)}\index{EP|see{gazdaságos hatványtípusú algoritmus}}\index{gazdaságos hatványtípusú algoritmus (EP)}
Ez az algoritmus (\textbf{E}conomic \textbf{P}ower) azt is figyelembe veszi (amellett, hogy két nagy fájl  
nem fér el egymás mellett), hogy két kis fájl mindig elfér egy lemezen. 
Ezért a nagy fájlok számát $N$-nel, a kicsikét $K$-val jelölve legfeljebb $N +  \lfloor(K + 1)/2 \rfloor$ 
lemezre van szüksége. Így elõször a nagy lemezeket 
ütemezzük külön lemezekre, majd a kicsiket a fenti számú lemez mindegyikére. Ha 
például $N = K = n/2,$ akkor ezek szerint csak $(0.75n)^{0.5n}$ elhelyezést kell elõállítanunk. 

\section{Listarövidítés (SL)}\inddef{listarövidítés}\index{SL|see{listarövidítés}} 
Bizonyos feltételek mellett igaz, hogy a $\mathbf{t}$ lista felbontható úgy $\mathbf{t}_1$ és 
$\mathbf{t}_2$ listákra, hogy 
$\textsc{OPT}(\mathbf{t}_1) + \textsc{OPT}(\mathbf{t}_2) \leq \textsc{OPT}(\mathbf{t})$ 
(ilyen esetekben szükségképpen az egyenlõség teljesül). 
Ennek elõnye, hogy a rövidebb listákat rendszerint rövidebb összidõ alatt tudjuk 
optimálisan elhelyezni, mint az eredeti listát. 

Tegyük fel például, hogy $t_i + t_j = 1.$ 
Ekkor legyen $\mathbf{t}_1 = (t_i,t_j)$ és $\mathbf{t}_2 = \mathbf{t} \setminus \mathbf{t}_1.$ Ekkor 
$\textsc{OPT}(\mathbf{t}_1) = 1$ és $\textsc{OPT}(\mathbf{t}_2) = \textsc{OPT}(\mathbf{t}) - 1.$ 
Tekintsük ugyanis egy optimális elhelyezés esetén azt 
a két lemezt, amelyekre a $\mathbf{t}_1$ lista elemei kerültek. Mivel mellettük legfeljebb 
$1 - t_1,$ illetve $1 - t_2$ összegû fájlok lehetnek, így azok helyfoglalásainak összege legfeljebb 
$2 - (t_1 + t_2),$ azaz 1. A listát egyszerre mindkét végén vizsgálva $O(n)$ idõ alatt kiválaszthatjuk azokat a 
fájlpárokat, melyekre a végrehajtási idõk összege 1. 
Ezután rendezzük a $\mathbf{t}$ listát. Legyen a rendezett lista $\mathbf{s}.$ 
Ha például $s_1 + s_n > 1,$ akkor az elsõ fájl minden elhelyezésben külön lemezre kerül, 
és így $\mathbf{t}_1 = (t_1)$ és $\mathbf{t}_2 = (t_2,t_3,\ldots,t_n)$ jó választás. 

Ha a rendezett listára $s_1 + s_n < 1,$ de $s_1 + s_{n - 1} + s_n > 1,$ akkor legyen $s_j$ a legnagyobb 
olyan listaelem, amelyet $s_1$-hez adva nem lépjük túl az egyet. 

Ekkor $\mathbf{t}_1 = (t_1,t_j)$ és $\mathbf{t}_2 = \mathbf{t} \setminus \mathbf{t}_1$ választás mellett a 
$\mathbf{t}_2$ lista két elemmel rövidebb, mint a $\mathbf{t}$ lista volt. 

Az utóbbi két mûvelettel gyakran lényegesen lerövidíthetõek a listák (szerencsés esetben 
úgy, hogy mindkét listára könnyen megkaphatjuk az optimális processzorszámot). 

A rövidítés után megmaradó listát -- például a korábbi algoritmusok valamelyikével -- 
természetesen még fel kell dolgozni. 

\section{Becslések (ULE)}\index{felsõ és alsó becslések}\index{ULE|see{felsõ és alsó becslések}} 
A felsõ és alsó becslésekre (\textbf{U}pper and \textbf{L}ower \textbf{E}stimations) 
támaszkodó algoritmusok a következõképpen mûködnek. Valamelyik közelítõ algoritmussal 
elõállítják az $\textsc{OPT}(\mathbf{t})$ egy $\textsc{A}(\mathbf{t})$ 
felsõ becslését, majd alulról is megbecsülik $\textsc{OPT}(\mathbf{t})$ értékét. Erre alkalmasak például az 
elhelyezések azon tulajdonságai, hogy két nagy fájl nem helyezhetõ azonos lemezre, 
és hogy a méretek összege egyik lemezen sem lehet 1-nél több. Ezért mind a nagy fájlok 
száma, mind pedig a fájlméretek összege, így ezek $\textsc{MAX}(\mathbf{t})$ maximuma is alsó becslést 
ad. Ha $\textsc{A}(\mathbf{t}) = \textsc{MAX}(\mathbf{t}),$ akkor az \textsc{A} algoritmus 
optimális ütemezést állított elõ. Ellenkezõ 
esetben például valamelyik idõigényes optimumkeresõ algoritmussal folytathatjuk. 


\section{Algoritmusok páronkénti összehasonlítása}\index{páronkénti összehasonlítás}
Ha egy ütemezési (vagy más) probléma megoldására több algoritmust ismerünk, ak- 
kor az algoritmusok összehasonlításának egyik egyszerû módja annak vizsgálata, hogy 
megadhatók-e a szereplõ paraméterek értékei úgy, hogy a kiválasztott 
teljesítménymérték értéke az egyik algoritmus esetén kedvezõbb legyen, mint a másik algoritmus esetén. 

A most vizsgált elhelyezési probléma esetén a $\mathbf{t}$ méretvektorhoz az \textsc{A}, 
illetve \textsc{B} algoritmus által rendelt lemezszámot $\textsc{A}(\mathbf{t})$-vel, 
illetve $\textsc{B}(\mathbf{t})$-vel 
jelölve azt vizsgáljuk, vannak-e olyan 
$\mathbf{t}_1,$ illetve $\mathbf{t}_2$ vektorok, melyekre $\textsc{A}(\mathbf{t}_1) < \textsc{B}(\mathbf{t}_1),$ 
illetve $\textsc{A}(\mathbf{t}_2) > \textsc{B}(\mathbf{t}_2).$ 
Ezt a kérdést most az elõbb definiált tíz közelítõ és az optimális algoritmusra vizsgáljuk meg. 

Az optimális algoritmusok definíciójából adódik, hogy minden $\mathbf{t}$-re és minden $\textsc{A}$ 
algoritmusra $\textsc{OPT}(\mathbf{t}) \leq \textsc{A}(\mathbf{t}).$ 

A továbbiakban a példavektorok elemei huszadok lesznek. 

Tekintsük a következõ nyolc listát: \\
 
$\mathbf{t_1} = (12/20, 6/20, 8/20, 14/20),$ 

$\mathbf{t_2} = (8/20, 6/20, 6/20, 8/20, 6/20, 6/20),$ 

$\mathbf{t_3} = (15/20, 8/20, 8/20, 3/20, 2/20, 2/20, 2/20)$, 

$\mathbf{t_4} = (14/20, 8/20, 7/20, 3/20, 2/20, 2/20, 2/20, 2/20),$ 

$\mathbf{t_5} = (10/20, 8/20, 10/20, 6/20, 6/20),$

$\mathbf{t_6} = (12/20, 12/20, 8/20, 8/20),$

$\mathbf{t_7} = (8/20, 8/20, 12/20, 12/20).$

$\mathbf{t_8} = (14, 12, 8, 10).$ \\

Ezeknek a listáknak az elhelyezési eredményeit a \ref{fig:lemezszam}. ábrán foglaltuk össze. 


\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}  \hline
 & LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT   \\ \hline
$\mathbf{t}_1$ & 4 &  3 & 3 & 3 & 3 & 3 & 2 & 2 & 2 & 2 & 2  \\ \hline
$\mathbf{t}_2$ & 6 &  2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 2 \\ \hline
$\mathbf{t}_3$ & 7 &  3 & 2 & 3 & 4 & 3 & 2 & 3 & 4 & 2 & 2 \\ \hline
$\mathbf{t}_4$ & 8 &  3 & 3 & 2 & 4 & 3 & 3 & 2 & 4 & 3 & 2 \\ \hline
$\mathbf{t}_5$ & 5 &  3 & 3 & 3 & 3 & 2 & 2 & 2 & 3 & 2 & 2   \\ \hline
$\mathbf{t}_6$ & 4 &  3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 2 & 2  \\ \hline
$\mathbf{t}_7$ & 4 &  3 & 3 & 3 & 2 & 3 & 2 & 2 & 2 & 2 & 2 \\ \hline
\end{tabular}
\caption{Lemezszámok összefoglalása.\label{fig:lemezszam}}
\end{center}
\end{figure}

A \ref{fig:lemezszam}. ábra mutatja, hogy az elsõ listához LF 4, míg a többi algoritmus 
ennél kevesebb lemezt igényel. Továbbá azt 
is mutatja $\mathbf{t}_1$ lista sora, hogy FFD, BFD, PFD, QFD és OPT kevesebb lemezt igényel, mint NF, 
FF, BF, PF és NFD. 

Természetes, hogy nincs olyan lista, amelyre bármelyik algoritmus kevesebb lemezt használna fel, mint OPT. 
 
Az is közvetlenül adódik, hogy nincs olyan lista, melyhez az LF kevesebb lemezt használna fel, mint a többi 
tíz algoritmus közül bármelyik.

Ezeket a megállapításokat mutatja a \ref{fig:parok}. ábra. Az ábrán a fõátlóban lévõ X szimbólumok azt jelzik, 
hogy az egyes algoritmusokat önmagukkal nem hasonlítjuk össze. Az elsõ oszlopban lévõ nagykötõjelek azt 
jelzik, hogy a sornak megfelelõ algoritmushoz nincs olyan lista, melyet az algoritmus 
több lemez felhasználásával dolgozna fel, mint az oszlopnak megfelelõ algoritmus, azaz LF.

Az utolsó sorban lévõ nagykötõjelek pedig azt mutatják, hogy nincs olyan lista, melyhez az optimális algoritmus több lemezt 
igényelne, mint bármelyik másik vizsgált algoritmus.

Végül az egyesek azt jelzik, hogy a $\mathbf{t}_1$ listához az ábra adott mezõje sorának megfelelõ algoritmus 
több lemezt használ fel, mint a mezõ oszlopának megfelelõ algoritmus.    

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|}  \hline
    & LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT   \\ \hline
LF  & X  &  1 & 1  & 1  & 1  & 1   & 1   & 1   & 1   & 1   & 1  \\ \hline
NF  & -- &  X &    &    &    &     & 1   & 1   & 1   & 1   & 1 \\ \hline
FF  & -- &    &  X &    &    &     & 1   & 1   & 1   & 1   & 1 \\ \hline
BF  & -- &    &    &  X &    &     & 1   & 1   & 1   & 1   & 1 \\ \hline
PF  & -- &    &    &    &  X &     & 1   & 1   & 1   & 1   & 1   \\ \hline
NFD & -- &    &    &    &    &  X  & 1   & 1   & 1   & 1   & 1 \\ \hline
FFD & -- &    &    &    &    &     &  X  &     &     &     &  \\ \hline
BFD & -- &    &    &    &    &     &     & X   &     &     &  \\ \hline
PFD & -- &    &    &    &    &     &     &     &  X  &     &   \\ \hline
QFD & -- &    &    &    &    &     &     &     &     & X   &  \\ \hline
OPT & -- & -- & -- & -- & -- & --  & --  &--   & --  & --  & X \\ \hline
\end{tabular}
\caption{Algoritmusok páronkénti összehasonlítása.\label{fig:parok}}
\end{center}
\end{figure}


Ha tovább folytatjuk a \ref{fig:parok}. ábra lemezszámainak elemzését, a \ref{fig:parok}. ábrát a 
\ref{fig:tobbpar}. ábrává egészíthetjük ki.

Mivel az elsõ sort és az elsõ oszlopot már kitöltöttük, az LF algoritmussal nem foglalkozunk többet. 

A $\mathbf{t}_2$ listához NF, FF, BF és OPT 2 lemezt használ, míg a többi 6 algoritmus hármat. Ezért 
a \idez{gyõztesek} oszlopainak és a \idez{vesztesek} sorainak metszéspontjaiba ketteseket írunk (a 
PF és OPT, valamint az NFD és OPT metszéspontjában azonban a 
már ott lévõ egyest nem írjuk felül, így $4 \times 6 - 2 = 22$ 
mezõbe kerül kettes). Mivel OPT sorát és oszlopát kitöltöttük, ezért a pont további részében nem 
foglalkozunk vele.

A harmadik lista hátrányos PF és PFD számára, ezért a soraikban lévõ üres mezõkbe hármasokat írunk.
Ez a lista arra is példa, hogy NF rosszabb lehet, mint FF, 
BF rosszabb lehet FF-nél, BFD az FFD-nél és a QFD-nél.


A negyedik listát csak BF és BFD tudja optimálisan  -- azaz két lemez felhasználásával -- feldolgozni. 
Ezért a két algoritmus oszlopában a még üres mezõkbe négyest írhatunk. 

Az ötödik listához NFD, FFD, BFD és QFD csak két, míg NF, FF, BF, PF és PFD három lemezt használ. Ezért 
a megfelelõ mezõkbe ötös kerülhet.

A $\mathbf{t}_6$ lista \idez{vesztesei} NF és NFD -- ezért a soraikban még üresen álló mezõkbe hatost írunk.

A $\mathbf{t}_7$ lista feldolgozását PF jobban végzi, mint FF.

A $\mathbf{t}_8$  lista bizonyítja, hogy a PF lehet jobb, mint a PFD.

További mezõk kitöltését segíti a következõ 
\begin{tetel} Ha $\mathbf{t} \in D,$ akkor
$$\textsc{FF}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \koz . $$
\end{tetel}
\begin{biz} A lista hossza szerinti indukciót alkalmazunk. 

Legyen $\mathbf{t} = \langle t_1, t_2, \ldots, t_n \rangle$ és $\mathbf{t_i} = \langle t_1, t_2, \ldots, t_i \rangle$ 
$(i = 1, 2, \ldots, n).$ Legyen NF$(\mathbf{t}_i) =$ N$_i$ és FF$(\mathbf{t}_i) =$ F$_i,$ továbbá legyen 
$n_i$ az \textit{utolsó lemez szintje} NF szerint, azaz a legnagyobb indexû, nem üres lemezre tett állományok 
hosszainak összege akkor, amikor NF éppen feldolgozta $\mathbf{t}_i$-t. Hasonlóképpen legyen $f_i$ az 
utolsó lemez szintje FF szerint.

A következõ invariáns tulajdonság teljesülését bizonyítjuk minden $i$-re: vagy $F_i < N_i,$ vagy $F_i = N_i$ 
és $f_i \leq n_i.$   

Ha $i = 1,$ akkor $F_1 = N_1$ és $f_1 = n_1 = t_1,$ azaz az invariáns tulajdonság második része teljesül. 
Tegyük fel, hogy a tulajdonság teljesül az $1 \leq i < n$ értékre. Ha most a $t_{i + 1}$ elhelyezése elõtt 
az invariáns tulajdonság elsõ része teljesült, akkor vagy érvényes marad az $F_i < N_i$ egyenlõtlenség, 
vagy pedig a lemezszámok egyenlõk lesznek és $f_i < n_i$ fog fennállni. Ha most a $t_{i + 1}$ elhelyezése elõtt 
a lemezszámok egyenlõk voltak, akkor az elhelyezés 
után vagy FF lemezszáma kisebb lesz, vagy pedig egyenlõ lemezszám 
mellett FF utolsó lemezének szintje legfeljebb akkora lesz, mint NF utolsó lemezének szintje.
\end{biz}

Hasonló állítás bizonyítható az NF--BF, NFD--FFD és NFD--BFD algoritmuspárokra.

Indukcióval belátható, hogy FFD és QFD minden listára ugyanannyi lemezt igényelnek.

Az eddigi megállapításokat a \ref{fig:tobbpar}. ábrán összesítjük.

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|}  \hline
    & LF & NF & FF & BF & PF & NFD & FFD & BFD & PFD & QFD & OPT   \\ \hline
LF  & X  &  1 & 1  & 1  & 1  & 1   & 1   & 1   & 1   & 1   & 1  \\ \hline
NF  & -- &  X & 3  & 4  & 7  & 5   & 1   & 1   & 1   & 1   & 1 \\ \hline
FF  & -- & -- &  X & 4  & 7  & 5   & 1   & 1   & 1   & 1   & 1 \\ \hline
BF  & -- & -- & 3  &  X & 7  & 5   & 1   & 1   & 1   & 1   & 1 \\ \hline
PF  & -- &  2 & 2  &  2 &  X &  3  & 1   & 1   & 1   & 1   & 1   \\ \hline
NFD & -- &  2 & 2  &  2 &  6 &  X  & 1   & 1   & 1   & 1   & 1 \\ \hline
FFD & -- &  2 & 2  &  2 &    &  -- &  X  & 4   &     & --  & 2\\ \hline
BFD & -- &  2 & 2  &  2 &    &  -- &  3  & X   &     & 3   & 2\\ \hline
PFD & -- &  2 & 2  &  2 &  8 &  3  &  3  & 3   &  X  & 3   & 2 \\ \hline
QFD & -- &  2 & 2  &  2 &    & --  & --  & 4   &     & X   & 2\\ \hline
OPT & -- & -- & -- & -- &--  & --  & --  & --  & --  & --  & X \\ \hline
\end{tabular}
\caption{Algoritmusok páronkénti összehasonlításának eredményei.\label{fig:tobbpar}}
\end{center}
\end{figure}



\section{Közelítõ algoritmusok hibája}
Két algoritmus ($\textsc{A}$ és $\textsc{B}$) relatív hatékonyságát gyakran jellemzik a kiválasztott 
hatékonysági mérték értékeinek hányadosával, jelen esetben az $\textsc{A}(\mathbf{t})/\textsc{B}(\mathbf{t})$ 
relatív lemezszámmal. Ennek a hányadosnak a felhasználásával különbözõ jellemzõk definiálhatók. Ezeket két 
csoportba szokás sorolni: egyik csoportba a legrosszabb, míg a másikba az átlagos esetet 
jellemzõ mennyiségek kerülnek. 

Itt csak a legrosszabb esettel foglalkozunk (az átlagos eset vizsgálata rendszerint lényegesen nehezebb). 

Legyen $D_n \ (n = 1, 2, \ldots)$ azon valós listák halmaza, amelyek $n$ elemet tartalmaznak, és legyen $\mathcal{D}$ 
az összes valós lista halmaza, azaz
$$ D = \displaystyle{\cup}_{n=1}^{\infty} D_n \koz . $$

Legyen $\mathcal{A}_{\var{lsz}}$ az \ki{állományelhelyezõ,}\inddef{állományelhelyezõ algoritmus} 
(azaz a minden $\mathbf{t} \in \mathcal{D}$ 
listához egy nemnegatív valós számot hozzárendelõ, és így a $\mathcal{D} \rightarrow \R^+_0$ 
leképezést megvalósító) algoritmusok halmaza. 

Legyen $\mathcal{A}_{\var{opt}}$ a minden listához az optimális lemezszámot rendelõ algoritmusok 
halmaza, és \textsc{OPT} ennek a halmaznak egy eleme (azaz egy olyan algoritmus, amely minden 
$\mathbf{t} \in D$ listához megadja a listához tartozó fájlok elhelyezéséhez szükséges 
és elégséges lemezek számát). 

Legyen $\mathcal{A}_{\var{köz}}$ azon $\textsc{A} \in \mathcal{A}_{\var{lsz}}$ algoritmusok halmaza, 
amelyekre $\textsc{A}(\mathbf{t}) \geq \textsc{OPT}(\mathbf{t})$ minden 
$\mathbf{t} \in D$ listára, és van olyan $\mathbf{t} \in D$ lista, amelyre $\textsc{A}(\mathbf{t}) 
> \textsc{OPT}(\mathbf{t}).$ Legyen $A_{becs}$ azon $\textsc{E} \in \mathcal{A}_{\var{lsz}}$ 
algoritmusok halmaza, amelyekre $\textsc{E}(\mathbf{t}) \leq \textsc{OPT}(\mathbf{t})$ minden 
$\mathbf{t} \in D$ listára, és van olyan $\mathbf{t} \in D$ lista, amelyre 
$\textsc{E}(\mathbf{t}) < \textsc{OPT}(\mathbf{t}).$ 

Legyen $F_n$ azon valós listák halmaza, amelyekre $\textsc{OPT}(\mathbf{t}) = n,$ azaz 
$F_n = \{\mathbf{t} | \mathbf{t} \in D$ és $\textsc{OPT}(\mathbf{t}) = n \}  \ (n = 1, 2, \ldots ).$ 
A továbbiakban csak $\mathcal{A}_{lsz}$-beli algoritmusokat fogunk vizsgálni. 
Az A és B algoritmusok $(\textrm{A, \ B} \in \mathcal{A}) \ R_{\textsc{A,B,}n}$ hibafüggvényét, 
$R_{\textsc{A,B}}$ hibáját (abszolút 
hibáját) és $R_{A,\infty}$ aszimptotikus hibáját a következõképpen definiáljuk:

$$R_{A,B,n} = \sup _{t \in F_n} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,$$ 
$$R_{A,B} = \sup _{t \in D} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,$$ 
$$R_{A,B,\infty} = \limsup _{n \rightarrow \infty} R_{A,B,n} \koz .$$

Ezek a mennyiségek fõleg akkor érdekesek, ha $\textsc{B} \in \mathcal{A}_\var{opt}.$ 
Ilyenkor az egyszerûség kedvéért a jelölésekbõl elhagyjuk a $\textsc{B}$-t, és az $\textsc{A} \in \mathcal{A},$ 
illetve az $\textsc{E} \in \mathcal{A}$ algoritmusok hibafüggvényérõl, 
hibájáról és aszimptotikus hibájáról beszélünk. 

Az NF fájlelhelyezõ algoritmus jellemzõ adatai ismertek.
\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:NF}
\begin{equation}
n = \textsc{OPT}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \leq 2\textsc{OPT}(\mathbf{t})-1=2n-1 \koz .\label{eq:NFkorlatok}
\end{equation}
Továbbá, ha $k \in \Z,$ akkor léteznek olyan $\mathbf{u}_k$ és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{NF}(\mathbf{u}_k)
\end{equation}
és 
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{NF}(\mathbf{v}_k) = 2k - 1 \koz .
\end{equation}
\end{tetel}
\begin{biz}
a) Az alsó korlát természetes: közelítõ algoritmus nem lehet jobb, mint az optimális.

b) A felsõ korlát belátásához elõször tegyük fel, hogy NEXT(\textbf{t}) páros, azaz $2k$ alakú. 
A NF által elheyezett fájlok esetén a lemezeken páronként nagyobb a fájlok hosszának összege, mint 1. 
Ezért a NF $2k$ lemezre mindig úgy helyez fájlokat, hogy hosszaik összege nagyobb, mint $k$,  
ezért $\textsc{NF}(\textbf{t}) > 2\textsc{OPT}(\mathbf{t})$ ellentmondásra vezetne

Legyen most $\textsc{NF}(\mathbf{t}) = 2k + 1$. Ekkor az elõzõek szerint a hosszak összege nagyobb, mint $k$, 
ezért $\textsc{OPT}(\mathbf{t}) \geq k + 1$, ami elég a kívánt egyenlõtlenséghez.

c) Ha az $\mathbf{u}_k$ lista $k$ darab egyest tartalmaz, akkor ezt a listát mind NF, mind pedig OPT $k$ 
lemezre helyezi el.

d) A $\mathbf{v}_k$ lista legyen $2k - 1$ olyan lista összeláncoltja, melyekben két elem van: elõbb 1/2, azután 
pedig $(1/2)/(2k - 1)$. Ezt a listát NF $2k - 1$ lemezre helyezi el, míg OPT csak $k$ lemezt használ fel.  
\end{biz}  

Ebbõl az állításból adódik a NF fájlelhelyezõ algoritmus hibafüggvénye, abszolút hibája és aszimptotikus hibája.
\begin{kov} Ha $n \in \Z,$ akkor
\begin{equation}
R_{\textsc{NF},n} = 2 - \frac{1}{n} \koz ,
\end{equation}
továbbá
\begin{equation}
R_{\textsc{NF}} = R_{\textsc{NF},\infty} = 2 \koz .
\end{equation}
\end{kov}

Megmutatjuk, hogy a FF fájlelhelyezõ algoritmus legrosszabb esetben is kevesebb fájlt igényel, 
mint az optimális érték 1.75-szöröse. A bizonyítás alapja a következõ, ú.n. telítettségi lemma.

\begin{lemma} Legyen k pozitív egész. Ha FF $k + 1$ lemez mindegyikén legalább k fájlt helyez el, akkor 
az ezeken a lemezeken elhelyezett fájlok hosszának összege nagyobb, mint k.
\end{lemma}

Ennél valamivel erõsebb  állítást bizonyítunk be.

\begin{lemma} Legyenek $k, \ i_1, \ i_2, \ \ldots \ i_{k+1} = b$ pozitív egészek, melyekre $i_1 < i_2 < \ldots < i_k < b$. 
Ha a FF algoritmus az L$_b$ lemezen legalább $k$ fájlt helyez el, akkor az L$_{i_1}$, \ L$_{i_2}$, \ \ldots, \  L$_{i_k}$, \ L$_b$ 
lemezeken elhelyezett fájlok méretének összege nagyobb, mint $k$.  
\end{lemma}

Érdemes megjegyezni, hogy a telítettségi lemma úgy is megfogalmazható, hogy a lemmában szereplõ lemezeken az átlagos 
telítettség nagyobb, mint $k/(k + 1)$.

\begin{biz} Legyen a legnagyobb indexû, azaz az L$_b$ lemezen elhelyezett legkisebb fájl mérete $a$. Ekkor az $a$ 
méretû fájl nem fért rá a kisebb indexû lemezekre, ezért azok szintje nagyobb, mint $1 - a$. A legnagyobb indexû 
fájl szintje viszont legalább $ka$, így a szintek összege valóban nagyobb, mint $k(1 - a) + ka = k$.
\end{biz}

\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:FF74}
\begin{equation}
\textsc{FF}(\mathbf{t}) < 1.75 \textsc{OPT}(\mathbf{t}) \koz .\label{eq:FF74}
\end{equation}
\end{tetel}
\begin{biz} A bizonyítás alapja, hogy a telítettségi lemma szerint az egy fájlt tartalmazó lemezek 
átlagos szintje egykettednél, a két fájlt tartalmazó lemezek pedig átlagosan kétharmadnál 
nagyobb mértékben telítettek. A fájlok hosszának összege legyen $H$, 
$\textsc{OPT}(\textbf{t}) = p$, $\textsc{FF}(\textbf{t}) = f$ és $\textsc{NF}(\textbf{t}) = e$.

a) Ha $p \leq 3$, akkor az elõzõ két tétel szerint teljesül az állítás:
\begin{equation}
f \leq e \leq 2p - 1 \koz,
\end{equation}
ahonnan már adódik a kívánt egyenlõtlenség.

b) Ha $p > 3$, akkor feltesszük, hogy FF $q$ lemezre egy, a többi $f - q$ 
lemezre pedig legalább két fájlt tett.  
A fájlok hosszainak (és egyúttal a lemezek szintjeinek) összege legyen $H$, ekkor $p \geq H$.

b1) Ha $q = 0$, akkor $p \geq H > 2/3 f$, ahonnan $f < 3/2p$.

b2) Ha $q =1$, akkor $p > 2(f - 1)/3$, ahonnan
\begin{equation}
f < \frac{3}{2}p + 1 = \frac{7}{4}p - \frac{1}{4}p + 1 = \frac{7}{4}p + \frac{4 - p}{4} \koz.
\end{equation}
Mivel $p \geq 4,$ ebbõl a kívántnál is erõsebb egyenlõtlenség adódik.

b3) Ha $q \geq 2$ és $f - q \leq 2$, akkor $q \leq p$ miatt 
\begin{equation}
f \leq q + 2 \leq p + 2 = \frac{7}{4}p - \frac{3}{4}p + \frac{8}{4} = \frac{7}{4}p + \frac{8 - 3p}{4} \koz,
\end{equation}
ahonnan a kívántnál kedvezõbb egyenlõtlenség adódik.

b4) Végül ha $q \geq 2$ és $f - q \geq 3$, akkor 
\begin{equation}
p > \frac{q}{2} + \frac{2(f -q)}{3} = \frac{2}{3}f - \frac{q}{6} \koz,
\end{equation}
ahonnan $p \geq q$ miatt
\begin{equation}
p > \frac{2f}{3} - \frac{p}{6} \koz,
\end{equation}
és így
\begin{equation}
f < \frac{7}{6}p\frac{3}{2} = \frac{7}{4} p \koz.
\end{equation}
\end{biz}


Az FF és BF fájlelhelyezõ algoritmus legrosszabb esetére vonatkozik a következõ állítás.

\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:FFBF}
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}), \ \textsc{BF}(\mathbf{t}) \leq 1.7\textsc{OPT}(\mathbf{t}) + 2 \koz .\label{eq:FFBFkorlatok}
\end{equation}
Továbbá, ha $k \in \Z,$ akkor léteznek olyan $\mathbf{u}_k$ és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{FF}(\mathbf{u}_k) = \textsc{BF}(\mathbf{u}_k) \label{FFBFkorlatok}
\end{equation}
valamint
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{FF}(\mathbf{v}_k) = 
\textsc{BF}(\mathbf{v}_k) = \lfloor 1.7k \rfloor \koz .\label{FFBFalso}
\end{equation}
\end{tetel}

Ebbõl az állításból adódik FF és BF aszimptotikus hibája, valamint hibafüggvényük jó becslése.

\begin{kov} Ha $n \in \Z,$ akkor
\begin{equation}
\frac{\lfloor 1.7n \rfloor}{n} \leq  R_{\textsc{FF},n}, R_{\textsc{BF},n} \leq \frac{\lceil 1.7n + 1 \rceil}{n}, 
\label{eq:egyhet}
\end{equation}
továbbá
\begin{equation}
R_{\textsc{FF},\infty} = R_{\textsc{BF},\infty} = 1.7 \koz .
\end{equation}
\end{kov} 

Az FF algoritmusra (\ref{eq:FFBFkorlatok})-nál kisebb felsõ korlát is ismert.

\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{bound:FF}
\begin{equation}
\textsc{FF} < 1.7 \textsc{OPT}(\mathbf{t}) + 1 \koz .\label{eq:FFkorlat}
\end{equation}
\end{tetel}

Ha $n$ osztható tízzel, akkor az (\ref{FFBFalso}) egyenlõtlenségben FF-re vonatkozó tényleges érték  
és a (\ref{eq:FFkorlat})-ban FF-re vonatkozó felsõ korlátok megegyeznek, azaz tízzel osztható $n$ 
esetén az FF$(\mathbf{t})$/$(\mathbf{t})$ és BF$(\mathbf{t})$/OPT$(\mathbf{t})$ hányadosok szuprémuma 1,7.

Mit mondhatunk FF abszolut hibájáról?

\vspace{6mm}
\textbf{IRODALOMJEGYZÉK}

[1] E. G. Coffman, Jr.: \textit{Computer and Job Shop Scheduling Theory}. John Wiley \& Sons, New York, 1972. 
1976. \hrefun{http://ams.math.uni-bielefeld.de/mathscinet/search/publications.html?pg4=AUCN\&s4=Coffman\%2C\&co4=
AND\&pg5=TI\&s5=&co5=AND\&pg6=JOUR\&s6=\&co6=AND\&pg7=ALLF\&s7=\&co7=AND\&Submit=Search\&dr=all\&yrop=
eq\&arg3=\&yearRangeFirst=\&yearRangeSecond=\&pg8=ET\&s8=Books\&review\_format=html}
{MR0629691 (83m:68066a)}

[2] A. Iványi: Performance bounds for simple bin packing algorithms. 
\textit{Annales Universitatis Budapestinensis de Rolando Eötvös Nominatae, 
Sectio Computatorica} \textbf{5} (1984), 77--82. \hrefun{http://ams.math.uni-bielefeld.de/mathscinet/
search/publdoc.html?arg3=\&co4=AND\&co5=AND\&co6=AND\&co7=AND\&dr=all\&pg4=AUCN\&pg5=TI\&pg6=JOUR\&pg7=
ALLF\&pg8=ET\&r=1\&review\_format=html\&s4=Iv$\%$C3$\%$A1nyi\&s5=Performance$\%$20bounds\&s6=\&s7=\&s8=All\&vfpref=
html\&yearRangeFirst=\&yearRangeSecond=\&yrop=eq}{MR0822601 (87h:68067)}  

[3] Iványi A. (szerk.): \textit{Informatikai algoritmusok. 1. kötet.} ELTE Eötvös Kiadó, Budapest, 2004. 
Elektronikusan: \newline 
\noindent \hrefun{http://www.inf.elte.hu/karunkrol/digitkonyv/Jegyzetek2004/InfAlg1.pdf}
{http://www.inf.elte.hu/karunkrol/digitkonyv/Jegyzetek2004/InfAlg1.pdf}. 11.4. alfejezet, 491--502. oldal. 
Angolul: \textit{Algorithms of Computer Science. Volume 2.} Mondat Kiadó, Budapest, 2007. 
17.4. alfejezet, 836--848. oldal. 

\end{document}
