As first to generate the chromosomes, we generate the Random number fromAs said in previous post below is our approach for the Job Shop Scheduling using Genetic AlgorithmProject Team: Kumaravel.S, Mohammed Ishaq.I, Sankaralingam.B, Venkatesh.G
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
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:© 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.
As said earlier, JSSP is a class of combinational optimization problems known as NP-Hard one.
In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H, such that for every decision problem L in NP there exists a polynomial-time many-one reduction to H, written L ≤p H. Informally, this class can be described as containing the decision problems that are at least as hard as any problem in NP. This intuition is supported by the fact that if we can find an algorithm A that solves one of these problems H in polynomial time, we can construct a polynomial time algorithm for any problem L in NP by first performing the reduction from L to H and then running the algorithm A. So, formally, a language L is NP-hard if for every L' in NP, L' ≤p L. If it is also the case that L is in NP, then L is called NP-complete. The notion of NP-hardness plays an important role in the discussion about the relationship between the complexity classes P and NP. The class NP-hard can be understood as the class of problems that are NP-complete or harder. A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for these problems, this has never been proved.†
References:
†NP-hard - Wikipedia, the free encyclopedia, last modified 01:43, 18 February 2006, http://en.wikipedia.org/wiki/NP hard
Related Posts:
© 2006 Kumaravel & Project Team
· If more than two machines involves then this rule can be applied only if it satisfies any one of the conditions as said above.
· This rule is applicable only when sequence of machines is in same order.
Related Posts:
© 2006 Kumaravel & Project Team
For the n jobs and m machines JSSP as shown below.
| Job | Processing time | |||||
| Machine 1 | Machine 2 | … | Machine k | … | Machine m | |
| J1 | T11 | T12 | … | T1k | … | T1m |
| J2 | T21 | T22 | … | T2k | … | T2m |
| . | . | . | … | . | … | . |
| Ji | Ti1 | Ti2 | … | Tik | … | Tim |
| . | . | . | … | . | … | . |
| Jn | Tn1 | Tn2 | … | Tnk | … | Tnm |
Table:JSSP (n x m) Modified Johnson's Rule
If any one of the conditions below:
· Min (Ti1) ≥ Max (Tik)
· Min (Tim) ≥ Max (Tik)
Where i = 1, …, n and k = 2, …,(m-1)
is satisfied, then Johnson’s algorithm can be extended in following way.
Create a hypothetical problem with two machines and n jobs as shown below and objective is to obtain optimal sequence for this. Later, the make-span is to be determined for the optimal sequence by using the data of original problem as above.
| Job | Processing time | |
| Machine A | Machine B | |
| J1 | T11 + ∑T1k | ∑T1k + T1m |
| J2 | T21 + ∑T2k | ∑T2k + T2m |
| . | . | . |
| Ji | Ti1 + ∑Tik | ∑Tik + Tim |
| . | . | . |
| Jn | Tn1 + ∑Tnk | ∑Tnk + Tnm |
Table: Hypothetical Problem of Modified Johnson's Rule
Where i = 1, …, n and k = 2, …,(m-1)
Related Posts:
© 2006 Kumaravel & Project Team
Consider the nx2 JSSP as shown below, using the Johnson’s rule obtain the optimal sequence which will minimize the make-span. Also determine the make-span.
| Job | Processing time | |
| Machine 1 | Machine 2 | |
| J1 | 4 | 6 |
| J2 | 12 | 10 |
| J3 | 14 | 10 |
| J4 | 8 | 12 |
| J5 | 18 | 6 |
| J6 | 16 | 8 |
Table:Illustration JSSP (6x2) for Johnson’s Rule
The working of the Johnson’s algorithm is as summarized as below.
| Stage | Minimum Tik | Unscheduled Jobs | Partial sequence |
| 1 | T11 = 4 | 1,2,3,4,5,6 | 1 X X X X X |
| 2 | T52 = 6 | 2,3,4,5,6 | 1 X X X X 5 |
| 3 | T41 = T62 = 8 | 2,3,4,6 | 1 4 X X X 5 |
| 4 | T62 = 8 | 2,3,6 | 1 4 X X 6 5 |
| 5 | T22 = T32 = 12 | 2,3 | 1 4 2 X 6 5 |
| 6 | T32 = 12 | 3 | 1 4 2 3 6 5 |
Table:Working of Johnson's Algorithm
Explanation for the specific stage 3 and 5 where the tie exists
· In stage 3, tie occurs between the J4 and J6 in different machines and J4 is on Machine 1 and hence it is first assigned
· In stage 5, tie occurs between the J2 and J3 in same machines and giving the priority to J2, it is first assigned.
Thus the optimal solution is 1-4-2-3-6-5. Then make-span is dogged as below:
| Job | Processing Time | Ideal Time | ||||
| Machine 1 | Machine 2 | Machine 1 | Machine 2 | |||
| In | Out | In | Out | |||
| J1 | 0 | 4 | 4 | 10 | 0 | 4 |
| J4 | 4 | 12 | 12 | 24 | 0 | 2 |
| J2 | 12 | 24 | 24 | 34 | 0 | 0 |
| J3 | 24 | 38 | 38 | 50 | 0 | 4 |
| J6 | 38 | 54 | 54 | 62 | 0 | 4 |
| J5 | 54 | 72 | 72 | 78 | 6 | 10 |
Table:Elapse Time Table for Each Machine of Given Job Sequence
Related Posts:
© 2006 Kumaravel & Project Team
