Results And Conclusions:Future Scope

Initially we have tried with the number of population is twice of the number of the machines which result the earlier convergence of the problem. Due to this there may be possible of stuck at local optima. So we fixed up the number of population to 30. It gives better result than the former.
For the further improvement, we gave attention to the selection parameter.

How our team approached to Job Shop Scheduling using Genetic Algorithm

As said in previous post below is our approach for the Job Shop Scheduling using Genetic Algorithm

Project Team: Kumaravel.S, Mohammed Ishaq.I, Sankaralingam.B, Venkatesh.G

As first to generate the chromosomes, we generate the Random number from

As of now…

In the previous posts, i just narrated the theory part (of genetic algorithm and job shop scheduling) what out team had extracted from various source (nearly 1000 of sources including web, books, library, resources from professors… and spend nearly full 100 days over 6 months) and our thoughts for the “thesis submission”. In forth coming posts, OUR APPROACH TO GA IN JSSP will be described. Also programming code will be explained in suitable way with the program extracts…

Previous Post List: Table of contents

IMPLEMENTATION OF GA TO JSSP

From the earlier said operational parameters, we took the real-value encoding in which the job numbers are encoded to form the string which will give the sequence of machining order. i.e., each chromosome represents a legal solution to the problem and is composed of a string of genes. In our application, each solution is encoded as a string of job sequence. For example, the string “235641” represents for a job sequence of job 2 is processed before job “3”, job “3” is processed before job “5” and so on. The requirement is that repeating a job in a sequence is not allowed and all jobs should appear in the sequence.

For the crossover we preferred the one point method since it is simple and easy to implement and it is robust. In case of mutation the swap mutation is used, which play the major role to avoid the convergence. Termination condition used is Fixed Generation Termination. In general the roulette wheel selection is used for the maximize problem so here we used the rank selection with the fitness function as said above.

Configuration of Operational Parameters with which application runs 

Population Size	Number of chromosomes in the population is 30
Crossover	Probability of crossover’s tossing head is 0.6
Mutation	Probability of Mutation’s tossing head 0.2
Fitness	Subjective Fitness of Makes-span
Selection	Linear Ranking selection
Termination Condition	After 100 Generations

References:

Book Reference: David Edward Goldberg (1989), “Genetic Algorithms in Search, Optimization and Machine Learning” Addison-Wesley.

Citation Needed: Scheduling Problem For A Single Flexible Manufacturing machine, Nguyen Van Hop, Industrial Engineering Program, Sirindhorn International Institute of Technology, Thammasat University

Related Posts:

• ABSTRACT
• INTRODUCTION
• Genetic Algorithm
• Mechanism
• History
• Biological Background
• Parameters

Table of Contents

© 2006 Kumaravel & Project Team

---

If references link found broken see the below e-printed version of webpage

Note: e-printed version of the webpage, are just for the reference and it was not owned by blog author. It had be created using the Open Source PDFCreator, which is environment friendly to save paper.

---

Termination

This generational process is repeated until a termination condition has been reached. Common terminating conditions are

• A solution is found that satisfies minimum criteria
  
• Fixed number of generations reached
  

Genetic Operators

Genetic variation is a necessity for the process of evolution. Genetic operators used in genetic algorithms are analogous to those which occur in the natural world: survival of the fittest, or selection; asexual or sexual reproduction (crossover, or recombination); and mutation.
Crossover
In genetic algorithms, crossover is a genetic operator used to

Fitness

Fitness is used to determine which chromosomes will be used for the next generation. Mathematically, for chromosome S_k: fitness = f(S_k) where: k = 1,..., n; n is a population size, which function that you use to calculate the fitness is obviously dependant on how you decide to encode the string to represent your problem.

Selection

During each successive epoch, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected.

Chromosomes

In genetic algorithms, a chromosome is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve. The chromosome is often represented as a simple string; although a wide variety of other data structures are also in use as chromosomes.

A genetic algorithm creates many chromosomes, either randomly

Operational Parameters of Genetic Algorithm

As said earlier the following are genetic parameters which are similar to Biological background of the nature.

• Chromosomes
  
• Fitness
  

History of Genetic Algorithm

Idea of evolutionary computing was introduced in 1960s by I.Rechenberg in his work "Evolution strategies" ("Evolutionsstrategie", in original). His idea was then developed by other researchers. Genetic Algorithms (GA) were invented by John Holland and developed by him and his students and colleagues. This lead to Holland's book "Adaptation in Natural and Artificial Systems"

How GA differs from other optimization techniques?

1. They work with a coding of the parameter set, not the parameters themselves.
   
2. They search from a population of points in the problem domain, not a singular point.
   
3. They use payoff information as the objective function rather than derivatives of the problem or auxiliary knowledge.
   

Evolutionary Steps of Genetic Programming -2

The evolutionary steps of genetic programming are as follows:
1. Randomly create an initial population (generation 0) of individual computer programs composed of the available functions and terminals.
2. Iteratively perform the following sub-steps (called a generation) on the population until the termination criterion is satisfied:

Evolutionary Steps of Genetic Programming -1

Genetic programming typically starts with a population of randomly generated computer programs composed of the available programmatic ingredients. Genetic programming iteratively transforms a population of computer programs into a new generation of the population by applying analogs of naturally occurring genetic operations. These operations are applied to individuals selected from the population. The individuals are probabilistically selected to participate in the genetic operations based on their fitness. The iterative transformation of the population is executed inside the main generational loop of the run of genetic programming.

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Genetic Algorithm
• Mechanism of GA

Table of Contents

© 2006 Kumaravel & Project Team

Mechanism of GA

A GA is an algorithm that operates on a principle, a combination of natural selection and procreation permits the development of living species that are highly adapted to their environments.

When applied to a problem the standard genetic algorithm proceeds as follows: an initial population of individuals i.e., a set of solutions for the given problem represented by chromosomes, is generated at random or heuristically.

At every evolutionary step, known as a generation, the individuals in the current population are decoded and evaluated according to some predefined quality criterion, referred to as the fitness function.

To form the next generation, individuals are selected according to their fitness. Then some or the entire existing individual of the current population is replaced with the newly created individuals.

Creation of new individuals is done by crossover and mutation operations which motivated by a hope that the new population will be better than the old one. Many selection procedures are currently in use, one of the simplest being Holland's original fitness proportionate selection, where individuals are selected with a probability proportional to their relative fitness.

This ensures that the expected number of times an individual is chosen is approximately proportional to its relative performance in the population. Thus, high-fitness individuals stand a better chance of “reproducing”, while low-fitness ones are more likely to disappear.

This is repeated until some condition such as number of populations or improvement of the best solution is satisfied. If the GA has been designed well, the population will converge to an optimal solution to the problem.

Convergence is the progression towards increasing uniformity. However, it is important not to forget that GA are stochastic iterative processes and they are not guaranteed to converge; hence, the termination condition may be specified as some fixed, maximal number of generations or as the attainment of an acceptable fitness level.^†

References

†“Genetic Algorithms”, Burhaneddin SANDIKCI, http://www.ie.bilkent.edu.tr/~lors/ie572/burhaneddin_html/IE572_GA.html

http://www.ie.bilkent.edu.tr/~lors/ie572/burhaneddin.pdf

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Some other Optimisation methods
• Genetic Algorithm
• Darwin's Theory of Natural Selection

Table of Contents

© 2006 Kumaravel & Project Team

---

If references link found broken see the below e-printed version of webpage

Note: e-printed version of the webpage, are just for the reference and it was not owned by blog author. It had be created using the Open Source PDFCreator, which is environment friendly to save paper.

---

Genetic Algorithm – Short note on Implementation

Genetic algorithms are typically implemented as a computer simulation in which a population of abstract representations (called chromosomes) of candidate solutions (called individuals) to an optimization problem evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but different encodings are also possible. The evolution starts from a population of completely random individuals and happens in generations. In each generation, the fitness of the whole population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), modified (mutated or recombined) to form a new population, which becomes current in the next iteration of the algorithm.^†

References

†Genetic algorithm - Wikipedia, the free encyclopedia, last modified 00:36, 15 February 2006, http://en.wikipedia.org/wiki/ Genetic_algorithm

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Some other Optimisation methods

Genetic Algorithm

Table of Contents

© 2006 Kumaravel & Project Team

Genetic Algorithm

A Genetic Algorithm (GA) is a programming technique that impersonates Darwin's theory of evolution or natural selection as a problem-solving approach and it is a part of evolutionary computing, which is a rapidly growing area of artificial intelligence. Since it is heuristic, it won’t give the solution which is exact. Most real-world problems are like that which don't calculate it exactly.

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Some other Optimisation methods

Implementation of GA – a short note

Table of Contents

© 2006 Kumaravel & Project Team

INTRODUCTION - OPTIMISATION OF JSS USING GA

In continuation to the previous posts related to JSS Using GA

Many prevailing industrial production environments still rely on pure professional knowledge for production planning and scheduling purposes. Optimization in an algorithmic sense is mostly not performed at all. This may seem amazing at first glance since computation have invaded almost all fields of modern industries. In particular, systems such as Production, Planning and Control Systems serve as a support tool for production related management activities. Such systems are designed in a highly generic and versatile way in order to be applied in many different companies no matter what products they actually manufacture.

In general, the objectives of optimization may be different from company to company such as minimization of make-span, maximizing machine occupation or both. Therefore, the concept of Production, Planning and Control Systems is not applicable for the optimization of production planning and scheduling in most of the cases. Due to its increasing significance, the optimization of production planning and scheduling attracted the attention of academic research.

The Job Shop Scheduling Problem (JSSP) and similar scheduling problems are combinatorial optimization problems and commonly classified as NP-hard ordering problems which makes almost impossible to solve these problems exactly, even for relatively small problem instances. Exact methods exist, like the branch and bound method which are only of theoretical relevance due to their exponential runtime complexity.

In reality compute results close to the optimum but in a reasonable amount of time is highly enough rather optimality. In such a case heuristic methods such as Local Search, Tabu Search, Simulated annealing and Evolutionary Algorithms, especially Genetic Algorithms (GA), are dominating in the field of JSSP.

Among the three kinds of JSSP such as static, dynamic and non-deterministic^† ,In this project, the static JSSP is used to evaluate the sequence using GA. JSSP description in terms of GA is initial phase challenge and machine side scheduling also challenged at final phase using the result of job side sequence. This report briefly describes the GA and its parameter along with the JSS parameters.

References:

† C. Bierwirth and D. Mattfeld, “Production Scheduling and Rescheduling with Genetic Algorithms”, Evolutionary Computation Volume 7, Number 1: 1-17, Massachusetts Institute of Technology (1999), Germany.

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING

Table of Contents

© 2006 Kumaravel & Project Team