\documentclass[11pt,a4paper]{article}
\usepackage[ansinew]{inputenc}
\usepackage[margin=2.5cm,nohead]{geometry}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{ngerman,latexsym,alltt,graphicx,textcomp}
\usepackage[bookmarks, colorlinks=false, pdftitle={MRT II Praktikumsprotokoll},
pdfauthor={Fabian Kurz, http://fkurz.net/}, pdfsubject={DSP}, pdfkeywords={TU Dresden, Praktikum, Mikrorechentechnik}, linkbordercolor={1 1 1}]{hyperref}
\date{30. Mai 2005}
\author{Gruppe 50:\\Marcel~Junige, Fabian~Kurz\\Martin~Laabs, Lars Lindenmüller}
\title{Praktikumsprotokoll Mikrorechentechnik II --\\
"`Simulation und Optimierung von Fertigungsprozessen"'}
\begin{document}
\setcounter{secnumdepth}{4}
\maketitle
\tableofcontents
\newpage
\section{Aufgabenstellung}

Aufgabe des Praktikums war die Implementierung von Methoden zur Manipulation
doppelt verketteter Listen im Rahmen des Simulationssystems ROSI.

ROSI wurde entwickelt um ereignisdiskrete Prozesse (insbesondere
Fertigungsprozesse) zu simulieren und optimieren. Ein solches Simulationsmodell
wird aus verschiedenen Bausteienen (Maschine, Warteschlange, Jobs,
Steuerelementen) zusammengesetzt.  

Bei der Optimierung durch stochastische Suchverfahren ist es n\"otig, die
Reihenfolge der Jobs in einer Warteschlange ver\"andern zu k\"onnen. Abbildung 
\ref{liste1} zeigt ein Modell einer solchen Warteschlange. Es handelt sich um
eine doppelt verkettete Liste von Jobs: jeder Job hat einen Zeiger auf seinen
Vorg\"anger und Nachfolger. Ein First- und Last-Zeiger verweisen auf das erste
bzw. letzte Element. 

\begin{figure}
\center
\begin{picture}(335,75)
\multiput(0,0)(50,0){6}{
\multiput(30,0)(30,0){2}{\line(0,1){30}}
\multiput(30,0)(0,30){2}{\line(1,0){30}}
\put(38,2){\makebox(0,0)[lb]{\sf\small Bef.}}
\put(52,28){\makebox(0,0)[rt]{\sf\small Next}}
\put(34,5){\circle*{3}}
\put(56,25){\circle*{3}}
\put(34,5){\vector(-1,0){24}}
\put(56,25){\vector(1,0){24}}
}
\multiput(145,45)(0,30){2}{\line(1,0){50}}
\multiput(145,45)(50,0){2}{\line(0,1){30}}
\put(155,48){\makebox(0,0)[bl]{\sf First}}
\put(185,72){\makebox(0,0)[tr]{\sf Last}}
\put(150,51.5){\circle*{3}}
\put(150,51.5){\line(-1,0){105}}
\put(45,51.5){\vector(0,-1){21.5}}
\put(190,68.5){\circle*{3}}
\put(190,68.5){\line(1,0){105}}
\put(295,68.5){\vector(0,-1){38.5}}
\end{picture}
\caption{Doppelt verkettete Liste}
\label{liste1}
\end{figure}

Es waren die folgenden Methoden zu implementieren:
\begin{description}
\item[JOB CQueue::GetList (long n)] Gibt einen Zeiger auf den $n$-ten Job der Warteschlangenliste
zur\"uck. Bei einem Wert von $n <1$ wird \texttt{NULL} zur\"uckgegeben.
\item[int CQueue::ExchJobs (JOB A, JOB B)] Vertauscht die Jobs \texttt A und \texttt B, die jeweils mit
einem Zeiger referenziert werden.
\item[int CQueue::ExchJobs (long Ax, long Bx)] Dito, jedoch wird anstelle der
Zeiger auf die zu vertauschenden Jobs die Jobnummer in der Liste angegeben.
\end{description}

\section{Entwurf und Implementierung}
\subsection{CQueue::GetList}

\texttt{CQueue::GetList} Gibt einen Zeiger auf den $n$-ten Job der
Warteschlangenliste zur\"uck. Bei einem Wert von $n <1$ wird \texttt{NULL}
zur\"uckgegeben.

Die Implementierung von \texttt{GetList} erfolgt intuitiv: 
Es wird \"uberpr\"uft, ob der Wert \texttt{No} positiv ist, wenn dies nicht der
Fall ist, wird \texttt{NULL} zur\"uckgegeben. Ein Hilfszeiger
\texttt{jp} wird vereinbart. Dieser wird mittels der Methode \texttt{GetJob} 
auf den ersten Job gesetzt. 

In einer \texttt{for}-Schleife wird der Zeiger nun \texttt{No} mal auf den
n\"achsten Job gesetzt. Falls kein nachfolgender Job exisitert, wird ebenfalls
\texttt{NULL} zur\"uckgegeben.

Wenn die \texttt{for}-Schleife ordnungsgem\"aß beendet wurde, zeigt der
Hilfzeiger \texttt{jp} auf das \texttt{No}-te Element und kann zur\"uckgegeben
werden.

\bigskip

\noindent \textbf{Quelltext}
\bigskip
\hrule
\begin{verbatim}
/***********************************************************************
   Es wird der No-te Job in der Warteschlange ausgegeben, 
   ohne ihn aus der Warteschlange zu entfernen. Die Zaehlung 
   beginnt mit 1. No = 0 -> NULL, No > Length -> NULL    
***********************************************************************/
JOB  CQueue::GetList (long No) {
    JOB jp;                          // Hilfszeiger auf aktuellen Job
    long i;                          // Zaehlervariable

    if (No < 1) {                    // Ueberpruefe auf guelltigen Wert
        return NULL;                 // Es gibt keine neg. Elemente
    } 

    jp=FirstJob();

    for(i=0;i<=No-1;i++) {           // Erster Job No = 0
        jp=jp->GetNext();            // durch Liste durchhangeln
        if (jp==NULL) {              // Job existiert nicht
            return NULL;             // NULL zurueckgeben
        }
    }

    // Wenn das Programm bis hier gekommen ist, zeigt jp auf den No-ten 
    // Job. Dieser wird zurueckgegeben.

    return jp;
}
\end{verbatim}
\hrule

\subsection{CQueue::ExchJobs (1)}

\texttt{CQueue::ExchJobs} Vertauscht die Jobs \texttt A und \texttt
B, die jeweils mit einem Zeiger referenziert werden.

Abbildung \ref{tausch} verdeutlicht die dabei zu t\"atigen Zeigeroperationen:
Die Vorg\"anger und Nachfolger von \texttt A und \texttt B werden in
den Hilfzeigern \texttt{An}, \texttt{Ap}, \texttt{Bn} und \texttt{Bp}
gespeichert. Mittels der Methoden \texttt{PutBefore} und \texttt{PutNext}
werden sodann die Elemente \texttt A und  \texttt B neu eingereiht. Dies
geschieht in beide Richtungen: Sowohl \texttt A und \texttt B als auch ihre
Vorg\"anger und Nachfolger m\"ussen neu verkn\"upft werden. 

\begin{figure}[h]
\center
\begin{picture}(285,75)
\put(0,30){
\multiput(0,0)(50,0){5}{
\multiput(30,0)(30,0){2}{\line(0,1){30}}
\multiput(30,0)(0,30){2}{\line(1,0){30}}
\put(34,5){\circle*{3}}
\put(56,25){\circle*{3}}
}
\put(34,5){\vector(-1,0){24}}
\put(256,25){\vector(1,0){24}}
\put(45,15){\makebox(0,0)[c]{\sf A}}
\put(95,15){\makebox(0,0)[c]{\sf B}}
\put(145,15){\makebox(0,0)[c]{\sf C}}
\put(195,15){\makebox(0,0)[c]{\sf D}}
\put(245,15){\makebox(0,0)[c]{\sf E}}
\qbezier(156,25)(165,25)(165,30)
\qbezier(165,30)(165,35)(155,35)
\put(155,35){\line(-1,0){80}}
\qbezier(75,35)(70,35)(70,30)
\qbezier(70,30)(70,25)(76,25)
\put(80,25){\vector(1,0){0}}
\qbezier(206,25)(215,25)(215,32.5)
\qbezier(215,32.5)(215,40)(205,40)
\put(205,40){\line(-1,0){80}}
\qbezier(125,40)(120,40)(120,32.5)
\qbezier(120,32.5)(120,25)(126,25)
\put(130,25){\vector(1,0){0}}
\qbezier(56,25)(65,25)(65,35)
\qbezier(65,35)(65,45)(75,45)
\put(75,45){\line(1,0){85}}
\qbezier(160,45)(170,45)(170,35)
\qbezier(170,35)(170,25)(175,25)
\put(175,25){\vector(1,0){5}}
\qbezier(106,25)(115,25)(115,37.5)
\qbezier(115,37.5)(115,50)(125,50)
\put(125,50){\line(1,0){85}}
\qbezier(210,50)(220,50)(220,37.5)
\qbezier(220,37.5)(220,25)(225,25)
\put(225,25){\vector(1,0){5}}
} % 30 up

\qbezier(84,35)(74,35)(74,30)
\qbezier(74,30)(74,25)(85,25)
\put(84,25){\line(1,0){80}}
\qbezier(164,25)(170,25)(170,30)
\qbezier(170,30)(170,35)(163,35)
\put(160,35){\vector(-1,0){0}}

\qbezier(134,35)(124,35)(124,27.5)
\qbezier(124,27.5)(124,20)(135,20)
\put(134,20){\line(1,0){80}}
\qbezier(214,20)(220,20)(220,27.5)
\qbezier(220,27.5)(220,35)(213,35)
\put(210,35){\vector(-1,0){0}}

\qbezier(184,35)(175,35)(175,25)
\qbezier(175,25)(175,15)(165,15)
\put(165,15){\line(-1,0){85}}
\qbezier(63,35)(70,35)(70,25)
\qbezier(70,25)(70,15)(80,15)
\put(60,35){\vector(-1,0){0}}

\qbezier(234,35)(225,35)(225,22.5)
\qbezier(225,22.5)(225,10)(215,10)
\put(215,10){\line(-1,0){85}}
\qbezier(113,35)(120,35)(120,22.5)
\qbezier(120,22.5)(120,10)(130,10)
\put(110,35){\vector(-1,0){0}}
\end{picture}
\caption{Vertauschung der Elemente \texttt B  und \texttt D in einer doppelt verketteten Liste}
\label{tausch}
\end{figure}

Abbildung \ref{tausch} stellt den einfachsten Fall dar, in dem zwei
nicht benachbarte Listenelemente miteinander vertauscht werden. Es gibt jedoch
folgende Sonderf\"alle zu beachten:
\begin{description}
\item[Element mit sich selbst vertauschen:] In diesem Falle ist nichts zu
machen.
\item[Benachbarte Elemente vertauschen:] Hier (Beispiel \texttt A vor \texttt
B) ist zu beachten, dass der Vor\-g\"angerzeiger des Elements \texttt B auf
\texttt A zeigt, bzw. der Nachfolgezeiger des Elements \texttt A auf das
Element \texttt B zeigt. W\"urde man nun den gew\"ohnlichen Weg einschlagen,
den ehemaligen Vorg\"anger von \texttt B (welcher \texttt A ist) als neuen
Vorg\"anger von \texttt A zu vereinbaren, ist \texttt A sein eigener
Vorg\"anger und die Listenstruktur ist zerst\"ort. Dieses wird verhindert indem mal den Nachfolger von \texttt A auf
\texttt A, den Vorg\"anger von \texttt B auf \texttt B setzt. Analog bei
\texttt B vor \texttt A.
\item[Eines/beide Elemente am Anfang oder Ende der Liste:] In diesem Fall
gibt es 
Pointer ins Leere, die nicht als Vorg\"anger oder Nachfolger eines
Elements eingesetzt werden d\"urfen. Anstelle dessen muss der First- bzw. 
Last-Pointer
neu gesetzt werden.
\end{description}

\bigskip

\noindent \textbf{Quelltext}
\bigskip
\hrule
\begin{verbatim}
/***********************************************************************
   Es wird der Job A der Warteschlange mit Job B vertauscht.
***********************************************************************/
int CQueue::ExchJobs (JOB A, JOB B) {
    JOB An,Ap,Bn,Bp;                   // Nachfolger bzw. Vorgaenger von A,B 

    if(A==B) {                         // Job A identisch Job B
        return ROSI_NOP;               // Nichts zu tun
    }
    if((A==NULL) || (B==NULL)) {       // Einer der Jobs ist NULL
        return ROSI_ERROR;             // Error!
    }

    An=A->GetNext();                   // Nachfolger von A
    Ap=A->GetBefore();                 // Vorgaenger von A
    Bn=B->GetNext();                   // Nachfolger von B
    Bp=B->GetBefore();                 // Vorgaenger von B

    // Bei benachbarten Jobs aufpassen, dass Nachfolger/Vorgaenger kein 
    // Zeiger auf sich selbst wird!

    if (B->GetNext() == A) {
        Ap = A;
        Bn = B;
    }
    else if (A->GetNext() == B) {
        An = A;
        Bp = B;
    }


    // Pointer-Vertauschung
    
    A->PutBefore(Bp);
    A->PutNext(Bn);
    B->PutBefore(Ap);
    B->PutNext(An);

    // Bei Verknuepfungen von An, Ap, Bn, Bp ggf. First- und Last-Zeiger
    // Anpassen!

    if (Bn == NULL) {                 // B letztes Element
        Last = A;                     // A wird letztes Element
    }
    else {                            // B nicht letztes Element
        Bn->PutBefore(A);             // A vor Bn einreihen
    }
    if (Bp == NULL) {                 // B erstes Element
        First = A;                    // A wird erstes Element
    }
    else {                            // B nicht erstes Element
        Bp->PutNext(A);               // A nach Bp einreihen
    }

    if (An == NULL) {                 // Analog zur B
        Last = B;
    }
    else {
        An->PutBefore(B);
    }
    if (Ap == NULL) {
        First = B;
    }
    else {
        Ap->PutBefore(B);
    }

    return ROSI_OK;
}
\end{verbatim}
\hrule

\subsection{CQueue::ExchJobs (2)}

Die Methode \texttt{ExchJobs} wird zus\"atzlich noch in einer zweiten Variante
implementiert, in der sich die Eingabeparameter im Typ unterschieden. W\"ahrend
die obige Variante Eingabeparameter vom Typ \texttt{JOB} erwartet, soll bei 
dieser Variante die \emph{Jobnummer} angegeben werden k\"onnen. 

Dies ist einfach zu implementieren, da die dazu ben\"otigten Methoden mit
\texttt{GetList} und \texttt{ExchJobs} schon zur Verf\"ugung stehen.

Die Behandlung ung\"ultiger Eingabeparameter wird ebenfalls durch die
vorhandenen Methoden uebernommen, so dass sich die Methode als Dreizeiler
implementieren l\"asst:

\bigskip

\noindent \textbf{Quelltext}
\bigskip
\hrule
\begin{verbatim}
/***********************************************************************
   Es wird der Ax-te Job der Warteschlange mit dem Bx-ten Job getauscht.
***********************************************************************/
int CQueue::ExchJobs (long Ax, long Bx) {
    return ExchJobs(GetList(Ax),GetList(Bx));
}

\end{verbatim}
\hrule


\section{Diskussion}
Die zu implementierenden Methoden funktionierten auf Anhieb wie gefordert. Dies
konnte schnell durch Vertauschungsoperationen in einer Liste im Konsolenmodus
von ROSI nachgewiesen werden. Dabei wurden auch die oben beschriebenen 
Sonderf\"alle ber\"ucksichtigt.

Es wurden im Folgenden zwei verschiedene Modelle von Produktionsstrategien mit
ROSI simuliert und durch stochastische Methoden optimiert:


\subsection{Flowshop}

Im \emph{Flowshop}-Modell durchl\"auft das zu fertigende Produkt eine bestimmte
Anzahl von Bearbeitungsstationen, wobei die Reihenfolge dieser Stationen f\"ur
alle Auftr\"age gleich ist. Die Stationen werden in ROSI als \texttt{Maschinen}
bezeichnet. Zu finden ist die optimale Anordnung der Bearbeitungsschritte, bei
der die Fertigungszeit minimal wird.

Die Auslastung der einzelnen Maschinen und Warteschlangen wird von ROSI in
einem Gant-Diagramm dargestellt. Abbildung \ref{flow} zeigt das Gant-Diagramm
eines Produktionsablaufes vor der Optimierung. In diesem Zustand, die neun Jobs
sind der Reihe nach ($1 \ldots 9$) angeordnet, ben\"otigt die Produktion 2:23h. 

Durch zuf\"alliges Ver\"andern der Jobreihenfolge per Hand (Reihenfolge
6, 9, 5, 4, 3, 1, 7, 2, 8) ergab sich eine leicht verbesserte Zeit von 2:15h.

Abbildung \ref{flowopt} stellt den Zustand nach einer Optimierung durch 500
zuf\"allige Vertauschungen dar. Die g\"unstigste sich ergebene Zeit von 1:59h
trat bei der Jobreihenfolge 9, 8, 1, 5, 6, 7, 2, 3, 4 auf.

\begin{figure}[h]
\center
\includegraphics[width=0.8\textwidth]{gant-flow}
\caption{Flowshop-Modell, nicht optimiert}
\label{flow}
\end{figure}

\begin{figure}[h]
\center
\includegraphics[width=0.8\textwidth]{gant-flow-optimiert}
\caption{Flowshop-Modell, Optimierung mit 500 Schritten}
\label{flowopt}
\end{figure}

Offensichtlich wurde durch diese Umverteilung der Auftr\"age die Auslastung der
Maschinen verbessert. Im Gant-Diagramm ist zu sehen, dass die
Leerlaufzeit der Maschinen (blau) nach der Optimierung deutlich geringer
geworden ist. 

\subsection{Jobshop}

Eine anderes Modell zur Beschreibung von Produktionsabl\"aufen ist der
\emph{Jobshop}. Im Gegensatz zum Flowshop gibt es hier keine feste Reihenfolge,
in der die Jobs die Maschinen durchlaufen. 

Auch f\"ur ein solches Modell wurde eine Optimierung durch zuf\"allige
Vertauschungen der Jobreihenfolge vorgenommen.

Im Originalzustand betrug die Bearbeitungszeit 1d 9:45h, das entsprechende
Gant-Diagramm wird in Abbildung \ref{job} dargestellt.
Durch zuf\"alliges Vertauschen per Hand (Reihenfolge 3, 6, 10, 4, 5, 2, 7, 8,
9, 1) ergab sich eine schlechtere Zeit von 1d, 11h. 

Erst die Optimierung mit 1000 Schritten brachte eine wesentliche Verbesserung
auf 1d, 5:21h, wie in Abbildung \ref{jobopt} dargestellt. Deutlich ist auch
hier wieder zu erkennen, dass die Leerlaufzeiten deutlich verringert werden
konnten.

\begin{figure}[h]
\center
\includegraphics[width=0.8\textwidth]{gant-job}
\caption{Jobshop-Modell, nicht optimiert}
\label{job}
\end{figure}

\begin{figure}[h]
\center
\includegraphics[width=0.8\textwidth]{gant-job-optimiert}
\caption{Jobshop-Modell, Optimierung mit 1000 Schritten}
\label{jobopt}
\end{figure}



\end{document}