\documentclass[presentation]{beamer}

\mode<presentation>
{
  %\usetheme{Warsaw}
  \usetheme{Malmoe}
  % oder ...

  %\usecolortheme{seagull}
  
  \setbeamercovered{transparent}
  % oder auch nicht
}

\mode<handout>
{
	\usecolortheme{seagull}
}

%\usepackage[german]{babel}
\usepackage{ngerman}
% oder was auch immer

\usepackage[latin1]{inputenc}
% oder was auch immer

\usepackage{times}
\usepackage[T1]{fontenc}
% Oder was auch immer. Zu beachten ist, das Font und Encoding passen
% müssen. Falls T1 nicht funktioniert, kann man versuchen, die Zeile
% mit fontenc zu löschen.

\usepackage{graphicx}

\title{Computational Intelligence}

\subtitle{"`Job Shop Scheduling"'}

\author{Daniel Brinkers, Florian Forster, Mark Fichtner}
% - Der \inst{?} Befehl sollte nur verwendet werden, wenn die Autoren
%   unterschiedlichen Instituten angehören.

\institute{Friedrich Alexander Universit"at Erlangen-N"urnberg}
% - Der \inst{?} Befehl sollte nur verwendet werden, wenn die Autoren
%   unterschiedlichen Instituten angehören.
% - Keep it simple, niemand interessiert sich für die genau Adresse.

\date[CI2K6]{Computational Intelligence, 2006-07-27}

\subject{"`Job Shop Scheduling"'}
% Dies wird lediglich in den PDF Informationskatalog einfügt. Kann gut
% weggelassen werden.


% Falls eine Logodatei namens "university-logo-filename.xxx" vorhanden
% ist, wobei xxx ein von latex bzw. pdflatex lesbares Graphikformat
% ist, so kann man wie folgt ein Logo einfügen:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}



% Folgendes sollte gelöscht werden, wenn man nicht am Anfang jedes
% Unterabschnitts die Gliederung nochmal sehen möchte.
\AtBeginSection[]
{
	\begin{frame}<beamer>
		\frametitle{Gliederung}
		\tableofcontents[currentsection]
	\end{frame}
}


% Falls Aufzählungen immer schrittweise gezeigt werden sollen, kann
% folgendes Kommando benutzt werden:

%\beamerdefaultoverlayspecification{<+->}



\begin{document}

\begin{frame}
	\titlepage
\end{frame}

\mode<handout>
{
	\begin{frame}
		\frametitle{"Ubersicht}
		\tableofcontents
	% Die Option [pausesections] könnte nützlich sein.
	\end{frame}
}


% Da dies ein Vorlage für beliebige Vorträge ist, lassen sich kaum
% allgemeine Regeln zur Strukturierung angeben. Da die Vorlage für
% einen Vortrag zwischen 15 und 45 Minuten gedacht ist, fährt man aber
% mit folgenden Regeln oft gut.  

% - Es sollte genau zwei oder drei Abschnitte geben (neben der
%   Zusammenfassung). 
% - *Höchstens* drei Unterabschnitte pro Abschnitt.
% - Pro Rahmen sollte man zwischen 30s und 2min reden. Es sollte also
%   15 bis 30 Rahmen geben.



\section{Das Problem}
%\subsection{Description}

\begin{frame}
	\frametitle{Was ist "`Job Shop Scheduling"'}
	%\framesubtitle{}

	\begin{itemize}
	\item $N$ Maschinen
	\item $M$ Bauteile
	\item Jedes Bauteil $m$ muss von $n$ Maschinen (in einer vorgegebenen
	Reihenfolge) bearbeitet werden, um fertiggestellt zu werden. Dabei
	m"ochte man aber f"ur den Prozess insgesamt m"oglichst wenig Zeit
	aufwenden, also m"oglichst viele Maschinen gleichzeitig arbeiten
	lassen.
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Beispiel: Autos}
	%\framesubtitle{}
	\begin{itemize}
	\item Firma X produziert Kombis, Kleinwagen und Limousinen.
	\item Als Maschinen gibt es Grundaufbau-Kombi, Grundaufbau-Kleinwagen,
	Grundaufbau-Limosine, Reifenmontage, Motormontage, Lackiererei.
	\item Da es beim Kleinwagen nicht genug Platz in der n"ahe des
	Motorraumes gibt, muss der Motor vor der Lackierung eingebaut werden.
	\item Da der Kombi besonders schwer ist, braucht er seine Reifen direkt
	nach dem Grundaufbau und wegen seiner Gr"o"se am l"angsten bei der
	Lackierung.
	\item Preisfrage: Wie baut man am schnellsten am meisten Autos?
	\end{itemize}
\end{frame}

\section{GA}
\begin{frame}
	\frametitle{Representation}

	\begin{itemize}
	\item Liste von Zahlen
	\item Jede Zahl representiert Verarbeitungsschritt, also eine Maschine/Bauteil-Kombination
	\item Ist ein Bauteil bereits fertig, so wird das n"achste verwendet,
	um immer g"ultige L"osungen zu erhalten
	\item Nicht eindeutig: Mehrere Representationen f"ur eine L"osung
	m"oglich
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Operationen}

	\begin{itemize}
	\item Fitness\\
	Die Zeit, bis das letzte Bauteil fertig ist
	\item Rekombination (Cross-Over)\\
	Hier kommt die Representation mit den immer g"ultigen L"osungen zum tragen
	\item Mutation\\
	Beliebige Teile des Gens werden zuf"allig erh"oht bzw. erniedrigt
	\end{itemize}
\end{frame}

\section{ACO}
\begin{frame}
	\frametitle{ACO}
	\framesubtitle{Realisierung}

	\begin{itemize}
	\item Liste von Ereignissen: $A_1$ heisst Maschine $A$ bearbeitet
	Bauteil $1$.
	\item Aufbauen eines Baumes/Graphs
	\item Graph ist bei ACOs leider n"otig und stellt ein zentrales Problem
	dar, da g"ultige Kind-Knoten von dem gesamten bisherigen Weg abh"angt
	\end{itemize}
\end{frame}

\section{Fazit}
\begin{frame}
	\frametitle{Fazit}

	\begin{itemize}
	\item GAs finden eine annehmbare L"osung in einer vern"unftigen Zeit
	\item ACOs f"ur Job-Scheduling-Probleme nicht bzw. nicht gut geeignet
	\end{itemize}
\end{frame}

\end{document}
