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

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"

Applications of Genetic Algorithms

• Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics.
  
• Automated design of mechatronic systems using bond graphs and genetic programming (NSF).
  
• Calculation of Bound States and Local Density Approximations.
  

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.

---

an example - Darwin's Theory

As an example Darwin noted that the ptarmigan turns white in winter. This colour change, he inferred, helped protect it from predators, which would have a hard time spotting the bird in snow. Ptarmigans that didn't change colour in winter would be spotted easily and eaten. In this way, Darwin implied, ptarmigans that turned white in winter would be more likely to survive, reproduce, and pass this adaptation to future generations.^†

References

†“Natural Selection”, http://bioweb.cs.earlham.edu/9-12/evolution/HTML/natural.html

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.

---

Darwin’s Theory of Natural Selection

• Individuals within a species vary and these variations are inherited (at least in part) by their offspring.
• Organisms produce more offspring than can possibly survive.
• On average, offspring that vary most strongly in directions favoured by the environment will survive and reproduce. Favourable variation will therefore accumulate in populations by natural selection. Unfavourable variations will be “weeded out” by natural selection.

Darwin's theory of natural selection built on the work of many scientists before him but was revolutionary because he was the first to put it together into a coherent theory that included a mechanism for how evolution occurred (natural selection) and because his conclusions directly challenged the orthodox religious thinking of the time.^†This was because:

• Darwin argued that evolution has no purpose. Individuals "struggle" to increase the representation of their genes in future generations, and that is all.
• Darwin maintained that evolution has no direction. It does not lead inevitably to higher things or to man. Organisms become better adapted to their environments, and that is all.

References

†“Darwin's Theory of Natural Selection”, Gould, http://www.chss.iup.edu/anthropology/courses/TC110/Darwin.htm.

Related Posts:

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

an example - Darwin's Theory

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

Search Methods and Optimization Techniques

Search Methods and Optimization Techniques

Section 1

Section 2

Section 3

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING

Table of Contents

© 2006 Kumaravel & Project Team

Search Methods and Optimization Techniques – Section 1

A search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer scientists that solve problems are kinds of search algorithms. The set of all possible solutions to a problem is called the search space. Brute-force search or "naïve"/uninformed search algorithms use the simplest, most intuitive method of searching through the search space, whereas informed search algorithms use heuristics to apply knowledge about the structure of the search space to try to reduce the amount of time spent searching.^†

References:

^†Search algorithm - Wikipedia, the free encyclopedia, last modified 04:37, 24 February 2006, http://en.wikipedia.org/wiki/ Search_algorithm

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING

Table of Contents

© 2006 Kumaravel & Project Team

Optimisation of Job Shop Scheduling Using Genetic Algorithm

In the current trend of Job Shop Scheduling in modern industries is still relying on the expert’s skill sets, although the computation enrolls almost all the fields. Application of the biological principal of natural selection to the artificial systems such as evolutionary algorithm was introduced more than three decades ago which has an inspiring evolution in the past few years. In this project, inspiring evolution of one such evolutionary algorithm called Genetic Algorithm (GA) is applied to Static Job Shop Scheduling Problem (JSSP) based on the raw data such as number of jobs to be machined on certain numbers of machines with operation time for each job on each machine to search out the optimal make-span of the problem. This project explains various operational parameters of genetic algorithm, which is one of the optimisation technique based on the mechanics of natural selection and genetics in combination with survival of fitness among the chromosomes structures in heuristic manner. In which each chromosome is encoded as a string of job sequence in integer or real value encoding fashion and the set of chromosomes called population is evaluated using various genetic operations such as one point crossover, swap mutation and linear ranking selection to search in multi direction to find the optimal solutions in the vast search space.

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.

A PROJECT BY - KUMARAVEL.S, MOHAMMED ISHAQ.I, SANKARALINGAM.B,VENKATESH.G

Table of Contents