Printer Friendly

An effective genetic algorithm for flow shop scheduling problems to minimize makespan.

1. Introduction

In past 5 decades flow shop scheduling may be a challenging area for researchers. Its main aim is to work out the job sequence of processing jobs on a given set of machines. In manufacturing environment flow shop scheduling is taken into account as most category of problem. A general flow shop scheduling during which n jobs are to be processed through m machines is to be considered. Fixed and non-negative processing times are thought of here. the foremost important assumptions created are that every job will be processed on only one machine at a time, the operations don't seem to be preventive, the jobs are out there for processing at time zero and set-up times are sequence independent. Here we have a tendency to think about the permutation flow shop problem, identical job sequence is taken into account on each machine for manufacturing. In flow shop scheduling minimizing makespan and total flow time may be a difficult task for several of the researchers. Therefore we thought of minimizing makespan as objective for my present work using meta-heuristic approach by improvising the Genetic algorithmic program. During this effective genetic algorithm (EGA), worst solutions are aloof from that algorithm by adding robust factor concept.

The first research involved to the flow shop scheduling problem was planned by Johnson [1]. Johnson represented a certain algorithm to reduce makespan for the n-jobs and 2-machines flow shop scheduling problem. Once the flow shop scheduling problem enlarges as well as additional jobs and machines, it becomes a combinatorial optimization problem. It's clear that combinatorial optimization problems are in NP-hard problem class, and close to optimum solution techniques are most popular for such problems. In recent years, metaheuristic approaches like Tabu Search, Genetic algorithms, simulated annealing, differential evolution, and artificial immune systems are very fascinating to solve combinatorial optimization problems relating to their computational performance. The recent studies for the flow shop scheduling problem with makespan criteria, it's obvious that the solution methods supported metaheuristic approaches are often planned. Mainstream of studies for the flow shop scheduling problem focuses to reduce makespan. For instance, the flow time, the machine idle times are main measures in minimizing total scheduling cost. Whereas makespan decrease results in total production run utilization, flow time decrease results in stable consumption of resources, fast turn-around of jobs and work-in-process inventory minimization. So as to reduce the production cost, it's desired to attain each these two objectives at the same time. Rajendran [2, 3] given one branch-and-bound algorithm and two heuristic algorithms aimed at two machine flow shop scheduling problem through makespan because the primary criterion and total flow time. Neppalli, Chen, and Gupta [4] planned two genetic algorithms for this problem. T'kindt, Gupta, and Billaut [5] presented mathematical programming designs, a branch-and-bound process, and a heuristic algorithm. Later, Jeen Robert et al. [6] have given a hybrid algorithm for Minimizing Makespan in the flow shop Environment. Yeh [7] created a memetic algorithm to solve this problem.

Recently, ant colony optimization (ACO) approach has become additional preferred to solve combinatorial optimization problems. This heuristic algorithm combines simulated annealing search and a local search algorithm. This study is that the initial application of ACO metaheuristic to multiobjective m-machine flow shop scheduling problem with esteem to the both objectives of makespan and total flow time. The performance of planned algorithm was related with two heuristic algorithms developed by Rajendran [8] and Ravindran [9] for these category problems and Genetic algorithm. Computational studies were showed on the yardstick problems from Taillard [10] because the test problem so as to verify the algorithm's performance. During this literature survey we tend to found several algorithm are accustomed solve flow shop scheduling problem in manufacturing field by many of the researchers, however we might found that genetic algorithm is very old algorithm however very powerful algorithm to solve flowshop scheduling problem. At the same time Muthiah [18] was described an opposite genetic algorithm and it was applied in Job shop scheduling problem. Thus we used genetic algorithm to solve flowshop scheduling however it's in effective approach by modifying its method routes strategies. Here we tend to addressed effective genetic algorithm (EGA) to solve flowshop benchmark problem, and also the results obtained by EGA are compared with earlier reportable results by using ant colony algorithm ACO by Betul Yagmahan [11] and Andrea Rossi [12].

2. Problem description and notations

Consider an m-machine flow shop problem where there are n jobs to be processed on the m machines among an equivalent order. We've got a tendency to completely take under attention of the permutation schedules, i.e., the same job order on each machine. The objective of this paper is to improve a developed Real Coded Genetic Algorithm and Efficient Genetic Algorithm to hunt out the most effective or near best sequence in flowshop environment by minimizing makespan. Meanwhile, the sequence among which each machine processes all jobs is identical on all machines.

Makespan is one among the foremost necessary criteria in every production systems; it's up to the whole completion time of all the activities. Minimizing this criterion caused higher usage of the resources specially machinery and manpower. In each simple and hybrid flow shop, the method is to transform the flow shop into a network form, then a linear programming model with the objective of minimizing the entire completion time of all the actions are constructed. Minimizing total completion time of all the activities is similar to minimizing makespan among the production system. The result is that the sequencing and scheduling of all the activities are determined. Besides, the following assumptions are thought of throughout this study:

* Each machine can process at the foremost one job at a time and each job is processed on just one machine at any given time.

* The schedule is non-preemptive; which suggests once a job starts to be processed on a machine, the process cannot be interrupted before completion.

* The number of jobs and their process times on each machine are known ahead and are non-negative integers.

* The individual operation setup times are little compared with their processing times, and are enclosed within the processing times.

* The prepared time of all jobs is zero, which suggests that everyone jobs are available for processing at the start.

The handling time t(i,j) is specified for any job i on any machine j. Given a permutation of the jobs, the accomplishment times of jobs on the machines, makespan are calculated as follows:

C([J.sub.1],1) = t([J.sub.1],1), (1)

C([J.sub.i],1) = C([J.sub.i-1],1) + t([J.sub.i],1),i = 2,... ... ... ,n, (2)

C([J.sub.1],1) = C([J.sub.1],J-1) + t([J.sub.1],j),j = 2,... ... ... ,m, (3)

C([J.sub.1],1) = max{C([J.sub.i-j],j),C[J.sub.i], j-1)}+t[J.sub.i]j), i = 2,... ... ... , n; j = 2,... ... ... ,m. (4)

(i) Makespan [C.sub.max] is the length of time required to finish processing all jobs, i.e.:

[C.sub.max]=max{[C.sub.1],[C.sub.2],... ... ... ,[C.sub.n]}, (5)

where [C.sub.n] is the completion time of job n.

The problem is to seek out a permutation of jobs thus on minimize the makespan of jobs. Since flow-shop scheduling problem has been shown to be NP--complete problem, for practical purposes, it has always a lot of acceptable to use an approximation technique that generates a close to best solution effectively. Throughout this paper an effort is made to boost the prevailing genetic algorithm procedures to use to permutation flowshop scheduling problems to provide higher results. The subsequent notations are utilized during this paper:
n           number of jobs
m           number of machines
[p.sub.ij]  processing time of job i on machine j
[p.sub.m]   probability of mutation
[P.sub.to]  probability for Roulette wheel selection
[p.sub.sc]  probability for sub chromosomal crossover
[P.sub.sm]  probability for sub chromosomal mutation
P(k)        population at kth generation
X* , X**    best and second best chromosomes
R           real random number is 0 and 1
Ng          maximum generation


3. Simple genetic algorithms (SGA)

Genetic Algorithms may be a world class optimization algorithm that look for improved performance by sampling areas of the solution space that have high probability of resulting in a good solution. They reproduce the natural evolutionary process in this, in every generation, the fittest individuals have a superior chance to produce offsprings by collaborating features of the parents or by altering one or a lot of the parent's characteristics whereas, the worst individuals are possibly to die. Decisions that need to be created for applying GA include individual or chromosome illustration, technique of crossover, probability of crossover, technique of mutation, probability of mutation, and population size. GA is of course parallel and exhibits implicit parallelism, that doesn't evaluate and improve a single answer, however analyses and modifies a set of solutions at the same time (Goldberg, [15]). The potential of a GA to control on many solutions instantaneously and collect information from all current solutions to direct search reduces the possibility of being trapped in a very local optimum.

In general, simple Genetic algorithm (SGA) consists of the subsequent steps:

Step 1: Initialize a population of chromosomes.

Step 2: Evaluate the fitness operate of each body.

Step 3: create new chromosomes by applying genetic operators like crossover and mutation to current chromosomes.

Step 4: evaluate the fitness worth of the new population of chromosomes.

Step 5: If the termination condition is satisfied, stop and come the simplest chromosome; otherwise, go to Step 3.

4. Real coded genetic algorithms (RCGA)

To compensate for the excessive computation time needed by the SGA, the important genetic algorithm (IGA) emphasizing on the coding of the chromosomes with floating purpose illustration was introduced and established to possess important improvements on the computation speed and exactness (Wei-Der Chang [14]; Goldberg [15]). Real Coded Genetic algorithm (RGGA) is same as that of straightforward genetic algorithm provided instead of taking binary values it'll take real values as [0, 1].

In real coded genetic algorithm the subsequent steps are to be followed:

Step 1: randomly generate N chromosomes on initial population within the search.

Step 2: Calculate the fitness for every chromosome.

Step 3: Perform reproduction, i.e. choose the higher chromosomes with probabilities supported their fitness values.

Step 4: Perform crossover on chromosomes selected in higher than step by crossover probability.

Step 5: Perform mutation on chromosomes generated in higher than step by mutation probability.

Step 6: If reach the stop condition or get the best solution, one could stop the process, else repeat Steps 2-6 until the stop condition is achieved.

Step 7: Get the best solution.4.

5. Effective genetic algorithm (EGA)

To enhance the performance of straightforward genetic algorithm, an efficient genetic algorithm has been developed to induce higher results. It's just a modification of straightforward genetic algorithm. GA is impressed by Darwin's Theory concerning evolution - "survival of the fittest". GA represents an intelligent exploitation of a random search wont to solve optimization problems. Within the simple GA-based approach, the varied stages like evaluation, selection, crossover and mutation are repeatedly executed when initialization till a stopping criterion is met. The algorithm works on multiple solutions at the same time. In this proposed EGA tool the initial population is processed by Nawaz, Enscore, and Ham (NEH) heuristic technique. During this a general purpose schedule optimizer for manufacturing flow shops planning using genetic algorithms. A performance measures for planning is make-span [C.sub.max] that has been used most optimum utilization of resources to extend productivity and stated as maximum completion time of last job to exit from the system:

[C.sub.max]=max{[C.sub.1],[C.sub.2],.......,[C.sub.n]},

where [C.sub.max] is the makespan that needs to be decreased. Effective Genetic algorithm consists of the subsequent steps:

Step 1: Generate Initial Population using NEH principle.

Step 2: evaluate fitness function value of chromosomes.

Step 3: selection procedure is done by roulette wheel technique.

Step 4: Use sub chromosomal level crossover.

Step 5: Use sub chromosomal level mutation (inverse technique, single purpose mutation).

Step 6: Robust- Replace heuristic technique applied.

Step 7: chromosomal level mutation.

The elaborated flow chart of EGA is given in Fig. 1. The planned algorithm can work with these steps that are within the flow chart. The subsequent parameters were described before the program works:
Initial Population: 1000.
Number of generation: 250.
Crossover probability: 0.9.
Mutation probability: 0.05.


5.1. Generation of initial population

A set of initial population are indiscriminately generated in step with the problem size and one initial seed is incorporated by NEH heuristic (Nawaz et al. [16]) for the initial population.

5.2. Evaluate fitness function

In order to mimic the natural process of the survival of the fittest, the fitness analysis function assigns to every member of the population a value reflective their relative superiority (or inferiority). Every chromosome has an evaluation criterion supported the objective function. Since IGA is used for maximization problems, a minimization problem may be appropriately converted into a maximization problem using a fitness function. The fitness function is:

f(x) = [1/[C.sub.max]] (6)

5.3. Selection procedure

In EGA only classical roulette wheel selection technique is incorporated for improving results (Goldberg [15]) is taken into account. In roulette wheel selection, parents are selected according to their fitness value. The higher the fitness the additional chances to be selected. The subsequent procedure is used for selection.

5.4. Sub chromosomal level crossover

In this step the initial chromosomes are reformed by subjecting sub chromosomal crossover. The whole chromosome string length is splited into sub chromosomes of equal length and these sub chromosomes are moved indiscriminately within the string to create a new chromosome.

Then the makespan values of corresponding new chromosome (child) are calculated, and it's compared with parent chromosome. Finally that chromosome is producing less makespan value that chromosome are maintained.

Parent chromosome

[mathematical expression not reproducible] 10

Sub-chromosome length =3

After sub-chromosomal crossover (child)

[mathematical expression not reproducible]

5.5. Sub-chromosomal level mutation

Mutation generates an offspring solution by altering the parent's feature indiscriminately. The most effective chromosome obtained from sub-chromosomal crossover is subjected for mutation operation. During this work, two differing types of mutation operators are used specifically inverse mutation and single point mutation.

5.5.1. Inverse mutation

In this step, indiscriminately choose two positions of i and j from a sequence. The portion of the sequence between these two positions is reversed to get a brand new mutated sequence. The new sequence represents the sequence of operations after mutation. Then the makespan values of corresponding new sequence are calculated, and it's compared with old sequence. Finally that sequence is producing less makespan value that sequence is sustained.
Original Sequence

10  8  9  7  6  4  5  3  2  1

Mutated Sequence

10  2  4  3  8  7  9  6  5  1


Mutation between positions 2 and 9.

5.5.2. Single point mutation

In this mutation technique, a random operation is chosen within the sequence and moved random position within the sequence. Then the makespan values of the resulting sequence are calculated and its value is compared with previous sequence. At last, the sequence which produces lees makespan that might be continued for following step.
Before mutation
10  8  9  7  6  4  5  3  2  1

After mutation
10  8  9  7  4  5  3  2  1  6


5.6. Robust- replace heuristic

In this step, indiscriminately generate ten sequences for implementation supported mutation and their corresponding makespan value and robust factors are calculated as shown in Table 1. Value of robust factor is calculated using the formula Robust Factor:

R = [l/[C.sub.max]]. (7)

Then calculate the average value of the robust factor for the ten set of sequences. The sequences having very less robust factor compared with the typical robust value are selected for making new schedule. The maintained schedules are given in Table 2. For better understanding of this process, here we have a tendency to thought of benchmark problem (IPTA001) proposed by Taillard [10] is chosen. The problem size is 20 jobs and 5 machines

5.7. Chromosomal level mutation

The two mutation processes are allotted among the chromosomes within the population whereas the sub chromosomal level mutation is restricted within a single chromosome. The mutation process includes inverse mutation and single point mutation as given in sec 5.5.

6. Result analysis and discussion

The bench mark issues planned by Taillard [17] are tested against the meta-heuristic technique by Effective genetic algorithmic rule (EGA). Numerous sizes of the issues with twenty jobs and five, 10, twenty machines were tested and therefore the same issues were tested exploitation the EGA methodology and therefore the results are shown in Table 3.

From Table 4, it's found that the planned new metaheuristic algorithmic rule that's EGA is giving higher results in comparison to any or all different algorithms. It's conjointly found that the developed EGA is incredibly abundant appropriate for twenty jobs five machines drawback, as a result of out of ten samples (IPTA001... IPTA010) EGA is giving seven higher results. Conjointly for twenty jobs ten machines drawback EGA is giving seven higher results in comparison different results. Then the program is dead for twenty jobs twenty machines drawback out of eight samples EGA has created seven higher results. From this Table 4 results, it's terminated that the developed EGA is giving higher results in comparison to any or all different algorithms conjointly it's giving best for big sized issues. The secret writing of the each RCGA & EGA were developed in Matlab atmosphere and therefore the programming was tested on associate Intel Core i5 processor 1.6 gigacycle per second system with 4GB RAM.

For the Taillard [10] benchmark drawback the obtained results by planned new meta-heuristic methodology (EGA) is compared with existing algorithms (Rajendran [8] and Ravindran at al [9] and Yagmahan, B., & Yenisey, M. M. [11] and Andrea Rossi [12]). Table 3 Consolidated results of the benchmark issues by EGA (Best makespan sequence) and Table 4 displays the comparison of results of Taillard Benchmark drawback with totally different heuristics. Conjointly the proportion of improvement is calculated are given in Table 5 and Table 6.

Percentage Improvement = ([C.sub.yy] - [C.sub.RCGA])/[C.sub.yy] (8)

where [C.sub.yy] is erformance measure reported by Yagmahan, B., & Yenisey, M. M. [11]; [C.sub.RCGA] is performance measure obtained by RCGA algorithms.

Percentage improvement of RCGA algorithmic rule over the past literature results is delineated in Table 5. From that it is ascertained that RCGA provides a pair of. 94% average improvement in makespan with relevance (Rajendran [8]), conjointly it created three.02%, 5.61% and 5.53% average improvement in makespan over HAMC1, HAMC2 and HAMC3 Ravindran et al. [9] according values. Once more the algorithmic rule is tested with Yagmahan, B., & Yenisey, M. M. [11] however RCGA has created solely zero. 16% of average improvement in makespan. Then the performance of RCGA is tested with NPFA-ACO developed by Andrea Rossi [12] and it's out performed by -1.55%. Then we've got an inspiration that to boost the performance RCGA by Effective genetic algorithmic rule (EGA) by modifying its parameters.

Percentage improvement of EGA algorithmic rule over the past literature results is delineated in Table 6. From that it is ascertained that RGA provides a 5.77% average improvement in makespan with relevance Rajendran [8], conjointly it created 5.83%, 8.35% and 8.26% average improvement in makespan over HAMC1, HAMC2 and HAMC3 Ravindran et al. [9] according values. Once more the algorithmic rule is tested with Yagmahan, B & Yenisey, M. M. [11] however EGA has created 3.08% of average improvement in makespan. Then the performance of EGA is tested with NPFA-ACO developed by Andrea Rossi [12] and it's performed 1.42% of average improvement in makespan. Any have EGA has created 21 best makespan sequences out of 28 benchmark Taillard problems.

Figs. 2 to 4 represents diagrammatically the performance of the important coded genetic algorithmic and Effective Genetic algorithmic over Rajendran [8], Y&Y [11] and NPFS-ACO [12] algorithms. Every bar in Figs. 2 to 4 shows the effectiveness of RCGA and EGA over all different algorithms within the chart.

Based on the higher than discussion show that the planned EGA and RCGA works higher than SGA, HAMC's, ACO by Y& Y [11], hymenopteran colony letter by Andrea Rossi [12] for all the benchmark issues and it giver for higher results. It is ascertained that the planned EGA algorithmic rule is additional economical than the present one for resolution flowshop programming issues with minimizing makespan as criteria, and this work is extended to solve bi-objective or different appropriate objectives either combined or individually.

7. Conclusions

In this paper, a new Effective Genetic algorithm (EGA) and Real Coded Genetic algorithm (RCGA) is planned to solve flow shop scheduling problems to reduce makespan. To verify the computational performance of the EGA and RCGA, an enormous experiment were conducted with Tailard benchmark problem for the various sizes of the problems with 20, 50 & 100 jobs through 5, 10 & 20 machines. The obtained results by planned EGA are one step ahead of all the algorithms for the flow shop scheduling problem. The planned algorithm will be used for single or combinational problems considering completely different conditions like total flow time, total tardiness and maximum tardiness. Furthermore the proposed algorithm will be implemented for scheduling problems in numerous manufacturing systems such as job shops, flexible flow shops, and cellular manufacturing and flexible manufacturing systems with respect to completely different objectives. The future work includes application EGA to combinational optimization problems

References

[1.] Johnson, S.M. 1954. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1(1): 61-68. http://dx.doi.org/10.1002/nav.3800010110.

[2.] Rajendran, C. 1992. Two-stage flowshop scheduling problem with bicriteria. Journal of the Operational Research Society 43(9): 871-884. http://dx.doi.org/10.1057/jors.1992.126.

[3.] Anderson, Rajendran, C.; Ziegler, H. 2004. Ant-colony algorithms for flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research 155(2): 426-438. http://dx.doi.org/10.1016/S0377-2217(02)00908-6.

[4.] Neppalli, V.R.; Chen, C.L.; Gupta, J.N.D. 1996. Genetic algorithms for the twostage bicriteria flowshop problem. European Journal of Operational Research 95(2): 356-373. http://dx.doi.org/ 10.1016/0377-2217(95)00275-8.

[5.] T'kindt, V.; Gupta, J.N.D.; Billaut, J.C. 2003. Two-machine flowshop scheduling with a secondary criterion. Computers and Operations Research 30(4): 505-526. http://dx.doi.org/10.1016/S0305-0548(02)00021-7.

[6.] Jeen Robert, R.B.; Rajkumar, R. 2016. A Hybrid Algorithm for Minimizing Makespan in the Permutation Flow Shop Scheduling Environment. Asian Journal of Research in Social Sciences and Humanities Vol. 6, No. 9, September 2016: 1239-1255. http://dx.doi.org/10.5958/2249-7315.2016.00867.4.

[7.] Yeh, W.C. 2002. A Memetic Algorithm for the n/2/Flowshop/[alpha]F + [beta]Cmax Scheduling Problem. The International Journal of Advanced Manufacturing Technology 20(6): 464-473. http://dx.doi.org/10.1007/s001700200179.

[8.] Rajendran, C. 1995. Heuristics for scheduling in flow-shop with multiple objectives. European Journal of Operational Research 82: 540-555. http://dx.doi.org/10.1016/0377-2217(93)E0212-G.

[9.] Ravindran, D.; Noorul Haq, A.; Selvakuar, S.J.; Sivaraman, R. 2005. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. International Journal of Advanced Manufacturing Technology 25, 1007-1012. http://dx.doi.org/10.1007/s00170-003-1926-1.

[10.] Taillard, E. 1993. Benchmarks for basic scheduling problems. European Journal of Operational Research 64: 278-285. http://dx.doi.org/ 10.1016/0377-2217(93)90182-M.

[11.] Betul Yagmahan; Mehmet Mutlu Yenisey. 2010. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications 37 (2010): 1361-1368. http://dx.doi.org/10.1016/j.eswa.2009.06.105.

[12.] Andrea Rossi; Michele Lanzetta. 2013. Scheduling flow lines with buffers by ant colony digraph. Expert Systems with Applications 40 (2013): 3328-3340. http://dx.doi.org/10.1016/j.eswa.2012.12.041.

[13.] David E. Goldberg. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. ADDISON-WESLEY PUBLISHING COMPANY, INC. 1-405. http://dx.doi.org/10.1023/A:1022602019183.

[14.] Wei-Der Chang. 2007. Non-linear system identification and control using a real-coded genetic algorithm, Applied Mathematical Modelling 31(3): 541-550. http://dx.doi.org/10.1016/j.apm.2005.11.024.

[15.] Goldberg, D.E. 1991. Real-coded genetic algorithms, virtual alphabets and blocking. Complex Systems 5: 139-167. http://dx.doi.org/ 10.1.1.52.9880.

[16.] Nawaz, M.; Enscore, E.; Ham, I. 1983. A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA, 11(1): 91-95. http://dx.doi.org/10.1016/0305-0483(83)90088-9.

[17.] Taillard, E. 1990. Some efficient heuristic methods for the flowshop-sequencing problem. European Journal of Operational Research 47(1): 65-74. http://dx.doi.org/10.1016/0377-2217(90)90090-X. 18 Muthiah, A.R.; Rajkumar, B. Muthukumar, 2015. Minimizing Makespan in Job Shop Scheduling Problem Using Genetic Algorithm, Applied Mechanics and Materials 813-814: 1183-1187. http://dx.doi.org/10.4028/www.scietific.net/AMM.813-814.1183.

R.B. Jeen Robert (*), R. Rajkumar (**)

(*) Department of Mechanical Engineering, AAA College of Engineering and Technology, Sivakasi- 626005, India, E-mail: jeenrb_robert@yahoo. com

(**) Department of Mechanical Engineering, Mepco Schlenk Engineering College, Sivakasi-626005, India

AN EFFECTIVE GENETIC ALGORITHM FOR FLOW SHOP SCHEDULING PROBLEMS TO MINIMIZE MAKESPAN

Summary

In this paper, the flowshop scheduling problem with the objective of minimizing the makespan has important applications in an exceedingly type of industrial systems. The main concern of flow shop scheduling is to get the most effective sequence, that minimizes the makespan, time of flow, time of idle, delay, etc. the objective of minimizing makespan is planned for finding the flowshop scheduling problem with Effective Genetic algorithm (EGA). EGA could be an easy and efficient algorithm that is employed to resolve for each single and multi-objective problem in flow shop environment. This algorithm can works simply for our real life applications. The planned algorithm is tested with well-known problems in literature. EGA's resolution performance has been compared with the present results reported by researchers. The obtained results show that the planned EGA performs higher than NPFS-ACO algorithms in finding the flowshop scheduling problem with the makespan criterion as average percentage improvement of 1.42%. This improvement ends up in two completely different meta-heuristic algorithms for finding flow shop planning problems specifically real coded Genetic algorithm (RCGA) and EGA. However EGA is performed well once comparing with RCGA.

Keywords: Flow shop scheduling, Makespan, Genetic Algorithm, Matlab.

Received May 24, 2016

Accepted August 04, 2017
Table 1 Initial sequences


Sequence

 3  17   9   8  15  14  11  16  13  19   6   4   5  18   1   2  10   7
 3  17  19   8  15  14  11  16  13   9   6   4   5  18   1   2  10   7
 3  13   4  14   5  15   6  16   7  17   8  18   9  19  20   2   1  10
 3  17   9   8   1   5  15  14  11  16  13  19   6   4  12   2  10   7
 3  12  17  20   9   7   8  10  15   2  14   1  11  18  16   5  13   4
17   9   8   3  15  14  11  16  13  19  20  12  10   7   2   1  18   6
 6  15   3   9   7  11   1   2  17  13   4   8  19  16   5  18  12  14
 6  17   7   8   9   1  11  12  15  13   4   3  19  16   5  18   2  14
17   6   3   9   8  15  14  11  16  13  19   4   5  18   1   2  10   7
 6  17   3   9   8  15  14  11  16  13  19   4   5  18   1   2  10   7

                       Robust
Sequence    Makespan   Factor

 3  20  12    1286    0.000778
 3  20  12    1322    0.000756
 3  11  12    1519    0.000658
 3  20  18    1377    0.000726
 3  19   6    1485    0.000673
17   5   4    1497    0.000668
 6  10  20    1311    0.000763
 6  10  20    1377    0.000726
17  20  12    1323    0.000756
 6  20  12    1345    0.000743

Average Robust factor= 0.000725

Table 2 Sequences retained

Sequence

 3  17   9  8  15  14  11  16  13  19   6   4   5  18   1   2  10   7
 3  17  19  8  15  14  11  16  13   9   6   4   5  18   1   2  10   7
 3  17   9  8   1   5  15  14  11  16  13  19   6   4  12   2  10   7
 6  15   3  9   7  11   1   2  17  13   4   8  19  16   5  18  12  14
 6  17   7  8   9   1  11  12  15  13   4   3  19  16   5  18   2  14
17   6   3  9   8  15  14  11  16  13  19   4   5  18   1   2  10   7
 6  17   3  9   8  15  14  11  16  13  19   4   5  18   1   2  10   7

Sequence    Makespan  Robust Factor

 3  20  12    1286      0.000778
 3  20  12    1322      0.000756
 3  20  18    1377      0.000726
 6  10  20    1311      0.000763
 6  10  20    1377      0.000726
17  20  12    1323      0.000756
 6  20  12    1345      0.000743

Table 3 Consolidated results of the benchmark problems by EGA (Best
makespan sequence)

Benchmark
Problem                       Best makespan sequence


No.of jobs=20; No.of machines=5
TA001       3  17   9   8  15  14  11  16  13  19   6   4   5  18   1
TA002       6  10  17   7  19  14  20   3   9  18  12  15   1  13  16
TA003      16  14  19  11   3  20  18   7   1  12  10   5   2   9   4
TA004      13   9  16  17  11  19  10   6   7  15   1  12   5  20   2
TA005       3   5  12  10  19   9  18  17  15  13   4  16   6   2  14
TA006      11   5   8  17  20  13   6  16   1   7  12  14  18  10  15
TA007       5   2  15  11   6  20  13  19   1  17   7   9  12   3   8
TA008      17  12   9   2  14  10  18   4  16  19   7   8   6   5  20
TA009       4   2  10  12   1  18  17   6  16   3  13  11   9   5  20
TA010       7  19  11  12  16   6   1  13  10   2  18  17   5  20   3

No.of jobs=20; No.of machines=10
TA011       4   5   9  10  15  18   2  17   3   6  12  20  13   8  14
TA012      12  17   5  13  15   7  20   9  11  19  10   1   6   2   3
TA013       4   7   9   2  16   5  12  13  11  15   1  20   6  14  17
TA014      18  20   3  11   9  13   4  16  15   1  10   2   7   8   6
TA015      16   8   4  20  18  14  15  13   9   6   1   7   3  17   2
TA016      19   8  20   3  18  16  11  14   6  15  13   4   5   7  12
TA017      19   6   7  10  17   1   4   8  20  18   9   2   5  16  14
TA018      17   8  20   4   7  18  14   2   5   9  19   3   6  11   1
TA019      20  11  16  14  12   8  17   4   2   1  19   3  13  18   7
TA020       5  12  14  13  17   9  19   4   7   8  16   6  20   2  10

No.of jobs=20; No.of machines=20
TA021       8   9  10  12  13  15  16  17  11   5   1  20  14   2  18
TA022      18   3  11   4   5  13   1  12  16  19  15   6  14  10  20
TA023      19   4   1  13   5  20  11   9  16   8  15  17  18   3  12
TA024      14   3  18   5   2   8  12   4   6  20  15  13   1   7  19
TA025      10   2   5  19   9  11  15  13   3  18  17   4  20  12  14
TA026      18   6  11   2   8  20  16   9  17   4  13  15  10  14   5
TA027      10  12  16  14   5  19  18   6   7  17   4   2  11  15  20
TA028       4   2  16  10  20   5   1  14   6   7   3  11  17  19  13

Benchmark                          Objective
Problem    Best makespan sequence  function
                                   Makespan

No.of jobs=20; No.of machines=5
TA001       2  10   7  20  12       1286
TA002       5   4  11   2   8       1359
TA003      17   6   8  13  15       1132
TA004       3   8  14   4  18       1325
TA005      11   1   7   8  20       1250
TA006       9   4  19   3   2       1220
TA007       4  16  14  18  10       1251
TA008      15   1   3  13  11       1221
TA009      14   7  15   8  19       1257
TA010      14   8   4  15   9       1145
No.of jobs=20; No.of machines=10
TA011      19  11   1   7  16       1652
TA012       4  18  16   8  14       1729
TA013      10   3  18  19   8       1534
TA014      19  12  14  17   5       1419
TA015       5  19  12  11  10       1502
TA016      17  10   9   2   1       1433
TA017      15  13  11  12   3       1545
TA018      13  15  10  16  12       1604
TA019      15  10   5   6   9       1617
TA020       3  18   1  15  11       1644
No.of jobs=20; No.of machines=20
TA021       6   7   3   4  19       2380
TA022      17   7   9   8   2       2150
TA023       2  10  14   6   7       2393
TA024      16  10  17   9  11       2250
TA025       1  16   8   7   6       2373
TA026       1   3   7  12  19       2290
TA027       8   9   3   1  13       2362
TA028      12   8  18  15   9       2249

Table 4 Comparison of results of Taillard benchmark problems with
different heuristics

Benchmark  UB/ Best  Rajendran [8]  Ravindran et al. [9]  Yagmahan and
Problem    Known                    HAMC1  HAMC2  HAMC3   Yenisey [11]


No.of jobs=20; No.of machines=5
TA001      1278      1359           1297   1324   1307    1297
TA002      1358      1378           1373   1409   1409    1383
TA003      1073      1230           1206   1210   1210    1203
TA004      1292      1393           1402   1423   1418    1377
TA005      1231      1307           1334   1387   1387    1311
TA006      1193      1282           1238   1281   1281    1245
TA007      1234      1387           1322   1359   1332    1303
TA008      1199      1344           1287   1404   1404    1265
TA009      1210      1335           1307   1382   1382    1303
TA010      1103      1191           1195   1298   1221    1179
No.of jobs=20; No.of machines=10
TA011      1560      1711           1774   1812   1787    1681
TA012      1644      1916           1791   1817   1832    1749
TA013      1486      1617           1643   1784   1783    1554
TA014      1368      1533           1531   1595   1584    1490
TA015      1413      1588           1722   1557   1586    1455
TA016      1369      1565           1612   1674   1667    1564
TA017      1428      1622           1594   1624   1628    1590
TA018      1527      1800           1631   1659   1659    1595
TA019      1586      1717           1769   1842   1823    1689
TA020      1559      1831           1744   1831   1793    1719
No.of jobs=20; No.of machines=20
TA021      2293      2610           2491   2539   2546    2428
TA022      2092      2301           2491   2491   2586    2281
TA023      2313      2411           2422   2433   2506    2515
TA024      2223      2471           2567   2693   2722    2299
TA025      2291      2427           2420   2453   2493    2473
TA026      2221      2466           2557   2641   2663    2339
TA027      2267      2174           2448   2528   2515    2378
TA028      2183      2418           2464   2473   2472    2418

Benchmark  NPFS-  RCGA  EGA
Problem    ACO
           [12]

No.of jobs=20; No.of machines=5
TA001      1290   1297  1286
TA002      1389   1371  1359
TA003      1100   1149  1132
TA004      1344   1355  1325
TA005      1250   1276  1250
TA006      1217   1234  1220
TA007      1258   1259  1251
TA008      1235   1280  1221
TA009      1258   1290  1257
TA010      1127   1162  1145
No.of jobs=20; No.of machines=10
TA011      1693   1685  1652
TA012      1785   1775  1729
TA013      1583   1636  1534
TA014      1452   1490  1419
TA015      1516   1558  1502
TA016      1445   1522  1433
TA017      1524   1576  1545
TA018      1650   1671  1604
TA019      1659   1686  1617
TA020      1670   1718  1644
No.of jobs=20; No.of machines=20
TA021      2396   2446  2380
TA022      2225   2215  2150
TA023      2446   2455  2393
TA024      2346   2363  2250
TA025      2439   2424  2373
TA026      2331   2356  2290
TA027      2428   2396  2362
TA028      2321   2368  2249

Table 5 Percentage improvement of RCGA algorithm over the past
literature

Benchmark Prob-  Imp.% of RCGA  Imp.% of RCGA  Imp.% of RCGA
lem              over [8]       over HAMC1     over HAMC2


No.of jobs=20; No.of machines=5
TA001              4.56          0.00           2.04
TA002              0.51          0.15           2.70
TA003              6.59          4.73           5.04
TA004              2.73          3.35           4.78
TA005              2.37          4.35           8.00
TA006              3.74          0.32           3.67
TA007              9.23          4.77           7.36
TA008              4.76          0.54           8.83
TA009              3.37          1.30           6.66
TA010              2.43          2.76          10.48

No.of jobs=20; No.of machines=10
TA011              1.52          5.02           7.01
TA012              7.36          0.89           2.31
TA013             -1.18          0.43           8.30
TA014              2.80          2.68           6.58
TA015              1.89          9.52          -0.06
TA016              2.75          5.58           9.08
TA017              2.84          1.13           2.96
TA018              7.17         -2.45          -0.72
TA019              1.81          4.69           8.47
TA020              6.17          1.49           6.17

No.of jobs=20; No.of machines=20
TA021              6.28          1.81           3.66
TA022              3.74         11.08          11.08
TA023             -1.82         -1.36          -0.90
TA024              4.37          7.95          12.25
TA025              0.12         -0.17           1.18
TA026              4.46          7.86          10.79
TA027            -10.21          2.12           5.22
TA028              2.07          3.90           4.25

Benchmark Prob-  Imp.% of RCGA  Imp.% of   Imp.% of RCGA over
lem              over HAMC3     RCGA over  NPFS-ACO [12]
                                Y&Y [11]

No.of jobs=20; No.of machines=5
TA001             0.77           0.00      -0.54
TA002             2.70           0.87       1.30
TA003             5.04           4.49      -4.45
TA004             4.44           1.60      -0.82
TA005             8.00           2.67      -2.08
TA006             3.67           0.88      -1.40
TA007             5.48           3.38      -0.08
TA008             8.83          -1.19      -3.64
TA009             6.66           1.00      -2.54
TA010             4.83           1.44      -3.11

No.of jobs=20; No.of machines=10
TA011             5.71          -0.24       0.47
TA012             3.11          -1.49       0.56
TA013             8.24          -5.28      -3.35
TA014             5.93           0.00      -2.62
TA015             1.77          -7.08      -2.77
TA016             8.70           2.69      -5.33
TA017             3.19           0.88      -3.41
TA018            -0.72          -4.76      -1.27
TA019             7.52           0.18      -1.63
TA020             4.18           0.06      -2.87

No.of jobs=20; No.of machines=20
TA021             3.93          -0.74      -2.09
TA022            14.35           2.89       0.45
TA023             2.04           2.39      -0.37
TA024            13.19          -2.78      -0.72
TA025             2.77           1.98       0.62
TA026            11.53          -0.73      -1.07
TA027             4.73          -0.76       1.32
TA028             4.21           2.07      -2.02

Table 6 Percentage improvement of EGA algorithm over the past
literature

Benchmark Prob-  Imp.% of RCGA  Imp.% of RCGA  Imp.% of RCGA  Imp.% of
lem              over [8]       over HAMC1     over HAMC2     RCGA over
                                                              HAMC3

No.of jobs=20; No.of machines=5
TA001             5.37           0.85           2.87           1.61
TA002             1.38           1.02           3.55           3.55
TA003             7.97           6.14           6.45           6.45
TA004             4.88           5.49           6.89           6.56
TA005             4.36           6.30           9.88           9.88
TA006             4.84           1.45           4.76           4.76
TA007             9.81           5.37           7.95           6.08
TA008             9.15           5.13          13.03          13.03
TA009             5.84           3.83           9.04           9.04
TA010             3.86           4.18          11.79           6.22
No.of jobs=20; No.of machines=10
TA011             3.45           6.88           8.83           7.55
TA012             9.76           3.46           4.84           5.62
TA013             5.13           6.63          14.01          13.97
TA014             7.44           7.32          11.03          10.42
TA015             5.42          12.78           3.53           5.30
TA016             8.43          11.10          14.40          14.04
TA017             4.75           3.07           4.86           5.10
TA018            10.89           1.66           3.32           3.32
TA019             5.82           8.59          12.21          11.30
TA020            10.21           5.73          10.21           8.31
No.of jobs=20; No.of machines=20
TA021             8.81           4.46           6.26           6.52
TA022             6.56          13.69          13.69          16.86
TA023             0.75           1.20           1.64           4.51
TA024             8.94          12.35          16.45          17.34
TA025             2.22           1.94           3.26           4.81
TA026             7.14          10.44          13.29          14.01
TA027            -8.65           3.51           6.57           6.08
TA028             6.99           8.73           9.06           9.02

Benchmark Prob-  Imp.% of   Imp.% of RCGA over
lem              RCGA over  NPFS-ACO [12]
                 Y&Y [11]

No.of jobs=20; No.of machines=5
TA001             0.85       0.31
TA002             1.74       2.16
TA003             5.90      -2.91
TA004             3.78       1.41
TA005             4.65       0.00
TA006             2.01      -0.25
TA007             3.99       0.56
TA008             3.48       1.13
TA009             3.53       0.08
TA010             2.88      -1.60
No.of jobs=20; No.of machines=10
TA011             1.73       2.42
TA012             1.14       3.14
TA013             1.29       3.10
TA014             4.77       2.27
TA015            -3.23       0.92
TA016             8.38       0.83
TA017             2.83      -1.38
TA018            -0.56       2.79
TA019             4.26       2.53
TA020             4.36       1.56
No.of jobs=20; No.of machines=20
TA021             1.98       0.67
TA022             5.74       3.37
TA023             4.85       2.17
TA024             2.13       4.09
TA025             4.04       2.71
TA026             2.09       1.76
TA027             0.67       2.72
TA028             6.99       3.10
COPYRIGHT 2017 Kauno Technologijos Universitetas
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Robert, R.B. Jeen; Rajkumar, R.
Publication:Mechanika
Article Type:Report
Date:Jul 1, 2017
Words:6999
Previous Article:Fast fourier transformation of emitted noises from welding machines and their classification with acoustic method.
Next Article:The relationship between different age swimmers' flip turn temporal and kinematic characteristics.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters