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

\addtocounter{chapter}{3}
\setcounter{section}{3}
\setcounter{page}{38}
\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}}}%%

\begin{document}

\chapter{A determinisztikus ütemez\'es alapfogalmai}
\section{Bevezet\'es}
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.eps} }
\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\'enyek}
\section{Bevezet\'es}
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}



\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. 




\tableofcontents

\end{document}
