\documentstyle[12pt,psfig,lslide]{article}
%\documentstyle[12pt,amssymbols,lslide]{article}
        % <- if amssymbols.sty is available
%\documentstyle[12pt,amstex,amssymb,lslide]{article}
        % <- if you use AmSLaTeX

\pagestyle{myheadings}

\makeatletter
\def\@oddhead{\vbox{\hbox to\hsize{\sl \rightmark \hfill \sl \today }}}
\def\@oddfoot{\vbox{\vspace{-20pt} \footmsg \hfill \rm \thepage}}
\makeatother

\def\rightmark{Job-Shop Scheduling with GA }
\def\footmsg{Hasan Timucin OZDEMIR}

\def\slidetitle{Analysis}
\def\author{Analysis}

\landscape
        % <- if your driver can rotate 90 degrees.
        % e.x. in emTeX derivers:
        %  hp filename /tr2
        % \portrait is default. 1 


% Adjust page dimensions here if necessary. For example:
%\addtolength{\textwidth}{-.3in}
%\addtolength{\textheight}{.5in}
%\addtolength{\topmargin}{.02in}
%\addtolength{\oddsidemargin}{-.03in}
%\addtolength{\evensidemargin}{-.03in}

%\verttop
        % compare it with \vertcenter that is the default

%\ovalframe
\doubleboxframe

%\doubleboxframe % or \ovalframe
        % compare them with \shadowframe that is the default

%\boxsecframe
%\boxsecframe
        % compare it with \shadowsecframe that is the default

\input{psfig}
\title{ {\bf Application of Fuzzy rules} \\ 
{\bf to control the parameters of the Genetic Algorithm } \\
{\bf for the Job-Shop Scheduling Problem} \\ 
\vspace{1cm} Hasan Timucin OZDEMIR \\ 
\vspace{1cm} \today}

\begin{document}

\begin{slide}

\titlepage

%{\bf Application of Fuzzy rules }

%\\ to control the parameters of
%the Genetic Algorithm \\ for the Job-Shop Scheduling Problem }

\pagebreak

\section{Genetic Algorithms} 

\begin{itemize}
\item
The Genetic Algorithms are controlled by

\begin{itemize}
\item crossover probability ($P_c$)
\item mutation probability ($P_m$)
\item population size ($PS$)
\end{itemize}

\item
Decision about these parameters is unfortunately depends on your problem.
The implementer tries to find the good combination to solve one problem
with the GA.

\item
The GA explores different areas in each generation when the population is diverse.
The bad case occurs when the hole population converges to one individual
({\bf premature convergence}) since crossover operation gives nothing and 
all the search process depends on the mutation operator.
\end{itemize}

\pagebreak

\begin{itemize}
\item
In this study we try to define a bunch of rules so that these parameters
are going to change during the each generation. 

\item
The key feature we want in the generation is the DIVERSITY and all
the rules that we are trying to implement are force the population as
much diversified as possible. 
\end{itemize}

\pagebreak

\section{Job-Shop Scheduling}

\begin{itemize}
\item
Let J denote the set of jobs, say $J=\{ j_{1}, j_{2}, \cdots , j_{m}\}$
and each job consists of some number of operations, say $n_{j}$ and
$O_{j} = \{o_{j,1},o_{j,2}, \cdots ,o_{j,n_{j}}\}$. Let M denote the set
of machines that are available to carry out the certain operations, say
$M=\{m_{1},m_{2}, \cdots ,m_{k}\}$. 
\item We have a cost matrix between operations and machines such as
 $C_{o,m}$ denotes the necessary time to carry out the operation {\bf o} on
 machine {\bf m}.
\item
The goal is to match the machines with the operations of each job(a
processing order of operations on each machine), such
that the maximum completion time({\em makespan}) is minimized with the
following assumptions:
\begin{itemize}
\item Individual operations are not splittable and no operation can be
performed on more than one machine at a time,
 
 \item No machine can handle more than one operation at a time.

\end{itemize}
\end{itemize}

\section{Job-Shop Scheduling}

\begin{itemize}

\item If the operations of any job are not related by precedence
constraints, the problem is referenced as an {\bf Open Shop} problem.

\item If we want to use the same machine ordering for each job, 
then this problem is called {\bf a flow shop problem}.

\item If we want to put a special machine orderings for each
job then this is called {\bf a job shop problem}.

\end{itemize}

\pagebreak

{\bf How can we define the diversity of population?}

\begin{itemize}

\item We want to collect the following information from the population
to use them in the definition of rules

\begin{itemize}

\item Number of the matching solutions in the population.

\item Sum Of Dissimilarities = \( \sum_{i=1}^{PS} \sum_{j=i+1}^{PS}
D_{i,j} \)

where $D_{i,j}$ denotes the dissimilarity between two chromosomes(i and j) 
can be evaluated by using a {\bf hamming distance},
 
 \[ D_{i,j} = \sum_{k=1}^{n} | P_{i,k} - P_{j,k} | \]

\end{itemize}

\item Number of the matching solutions can be at most the size of the
population(PS).

\item Sum Of Dissimilarities(SofD)

\[SofD < n \cdot PS \cdot \frac{PS+1}{2} \]

\item These observations allow us to apply the normalization on these
values and define the necessary fuzzy sets in [0,1] interval.
\end{itemize}

\pagebreak

\section{Fuzzy Rules}

%\begin{figure}[htbp]
%\centerline{\psfig{file=DissimClasses.ps,height=3in,width=3in}}
%\caption{Fuzzy Classes for the Sum of Dissimilarities Measure}
%\label{fig:layers}

%\end{figure}
%\begin{figure}[htbp]
%\centerline{\psfig{file=NumOfMatch.ps,height=3in,width=3in}}
%\caption{Fuzzy Classes for the Number of matches measure}
%%\label{fig:layers}
%\end{figure} 

\pagebreak
 
\section{Fuzzy Rules}

\begin{itemize}
\item
Crossover and Mutation probabilities are going to be updated according
to the following rules:

\begin{center}
Crossover Probability ($P_c$)
\hspace{2cm}
Mutation Probability ($P_m$)
 
\begin{tabular}{|l|cccc|} \hline
   & N & S & L & VL \\ \hline
N  & 0 & 0 & - & - \\
S  & - & 0 & 0 & 0 \\
L  & + & + & 0 & 0 \\
VL & + & + & + & 0 \\ \hline
\end{tabular}
\hspace{1.5in}
\begin{tabular}{|l|cccc|} \hline
    & N & S & L & VL \\ \hline
 N  & - & - & - & 0 \\
 S  & + & 0 & 0 & 0 \\
 L  & + & + & + & 0 \\
 VL & + & + & + & + \\ \hline
\end{tabular}
\end{center}
\item Each symbol refers to the following operation on the corresponding
parameter

\begin{center}
\begin{tabular}{ccl}
0 & : & do not change \\
- & : & decrease \\
+ & : & increase \\
\end{tabular}
\end{center}

\end{itemize}

\pagebreak

\section{Components of GA}

\begin{itemize}
\item {\bf Chromosome Structure :} Assume that we have {\bf m} number of machines and without optimization
it can
be done in {\bf t} time intervals. Then we define a string for each machine
such that each string has {\bf t} elements, that hold the status of the
machine for the corresponding time slot. The status of the machine
contains
whether the machine is idle
or not and if it is not idle, which job is carried out by the machine
at that time. ({\bf Gantt Chart})

\item {\bf Mutation Structure :} Two tasks are selected at random and
{\bf swap}ped.

\item {\bf Parent Selection For the Crossover Operation :} Crossover
operation is applied on the chromosomes that are {\bf similar} or {\bf less similar}
according to the Dissimililarity measure.

\item {\bf Crossover Operation :} Standard 1 point crossover operation.
\end{itemize}
%\titlepage

\pagebreak

{\bf Algorithm}

\begin{enumerate}
 
\item For each chromosome of the current population
  
\begin{enumerate}
   
\item If crossover is necessary, then pick the most similar chromosome
   and apply the crossover between these two chromosomes. Add the new
   offsprings to the new generation set.
    
\item If mutation is necessary, then apply mutation and put the new
    solution into a new generation set.
     
\end{enumerate}
      
\item Merge the previous population with the new generation set and sort
      them by their fitness value.
       
\item Select the chromosomes who has better fitness value and are not
   {\bf very similar} to the ones that are already added. Here average
   fitness value of the total set might give us some direction. If two
   chromosomes are very similar, we might add the one who has the better
   fitness value.
	
\item Adjust the crossover probability by using the fuzzy rules.

\item Adjust the mutation probability by using the fuzzy rules.
	 
\end{enumerate}

\pagebreak

\section{Further Studies}

\begin{itemize}

\item We can try to use the different measures from the population
structure such as variance, entropy, etc. to define the corresponding rules.

\item We can try to assign a mutation rate and crossover rate for each
individual and adjust their values according to given rules so that each
individual can end up with its own mutation and crossover rate.

\item A little different version could be to think the mutation rate for
each gene and try to adjust them by using rules while keeping a crossover
rate for each individual in the population.

\item In the proposed algorithm we only use one kind of crossover and
mutation operator. We can try to use several crossover and mutation
operators with the algorithm and promote the one who produces a better
individuals so that an algorithm can find the better match between
operators.
\end{itemize}

\pagebreak

\section{Conclusion}

%\slidecontents

%\sectioncontent



\end{slide}
\end{document}
