Document Type : Research Paper

Authors

1 Department of Industrial Management, Vali-e-Asr University, Rafsanjan, Iran.

2 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Kerman, Iran

3 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.

4 Department of Mechanical Engineering, University of Birjand, Birjand, Iran.

Abstract

Various procedures, methods, constraints and objectives are studied in a flow shop problem during the past decades. In order to adapt the problem to the reality form, its parameters are considered as a fuzzy model. In this problem, we consider the processing time as the trapezoidal fuzzy numbers. The purpose of this problem is to find an optimum sequence in a way that the makespan or the completing time of jobs to be minimized. In order to solve this problem, in this paper, the Random-Elitist Genetic Algorithm (REGA) is presented in this regard. Observing the performance and the efficiency of this algorithm, we code it by the VBA and compare with the other results. We first test the performance of different crossover operators for our algorithm. Next, using a specific example, we examine the performance of our algorithm. The results indicated that due to very good searching; this algorithm has the good performance in finding the optimal solution and reaching the optimum solution in a very short time.

Keywords

[1]                 Johnson, S.M. (1954). Optimal two and three–stage production schedules with setup times included. Naval Research logistics Quarterly, Vol. 1, No. 1, pp.61-68.
[2]                 Ogbu, F. A. and Smith, D. K. (1991). Simulated annealing for the permutation flow shop problem. Omega, Vol. 19, No. 1, pp. 64-67.
[3]                 Van Laarhoven, P. J. M. and Aarts, E. H. L. (1987). Simulated annealing: theory and applications. Dordrecht: D.Reidelpubl.Co.
[4]                 Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-wesley, Reading, MA.
[5]                 Reeves, C. (1995). A genetic algorithm for flow shop sequencing. Computers and Operations Research, Vol. 22, No. 1,pp. 5-13.
[6]                 Holland, J.H. (1975). Adaptation in natural and artificial systems, The university of Michigan Press, Ann Arbor.
[7]                 Mccahon, C. S. and Stanley, L. E. (1992). Fuzzy job sequencing for a flow shop.
European Journal of Operational Research, Vol. 62,No.3,pp. 294-301.
[8]                 Tsujimura, Y., Park, S.H., Chang, I. S., and Gen, M. (1993). An effective method for solving flow shop scheduling problems with fuzzy processing times. Computers and Industrial Engineering, Vol. 25, No., pp.239-242.
[9]                 KhademiZare, H. and Fakhrzad, M.B. (2011). Solving flexible flow-shop problem with a hybrid genetic algorithm and data mining: A fuzzy approach. Expert Systems with Applications, Vol. 38,No. 6, pp.7609-7615.
[10]             Sadinezhad, S. and GhalehAssadi, R. (2008). Preference ratio-based maximum operator approximation and its application in fuzzy flow shop scheduling. Applied Soft Computing, Vol. 8,No. 1,pp. 759-766.
[11]             Lai, P. J. and Wu, H.C. (2011). Evaluate the fuzzy completion times in the fuzzy flow shop scheduling problems using the Virus-Evolutionary genetic algorithms. Applied Soft Computing, Vol. 11,No. 8,pp. 4540-4550.
[12]             Deng, Y., Zhenfu, Z. and Qi, L. (2006). Ranking fuzzy numbers with an area method using radius of gyration. Computers and Mathematics with Applications, Vol. 51,No. 6, pp.1127-1136.
 
N. ShahsavariPour et al. /IJRIE 3(4) (2014) 1-12         12
 
[13]             Darwin, C. (1859). On the origin of species by means of natural selection or the preservation of favored races in the struggle for life. Murray, London.
[14]             Whitley, D. (1989). The GENITOR algorithm and selection pressure: Why rank- based allocation of reproductive trials is best.In Proceedings of Third International Conference on Genetic Algorithms, pp. 116-121.
[15]             Eshelman, L.J. (1991). The CHC adaptive search algorithm: How to have safe search when engaging in non-traditional genetic recombination. In: Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, pp. 265-283.
[16]             Deb, K., Agrawal, S., Pratap, P., and Meyarivan, T. (2000). A Fast Elitist Non- Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II.  In Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849- 858.
[17]             Zitzler, E. and Thiele, L. (1999). Multi objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. Evolutionary Computation, IEEE Transactions, Vol. 3,No. 4,pp. 257-271.
[18]             Goldberg, D. E. and Deb, k. (1991). A comparative Analysis of selection schemes  used in genetic algorithm, in: G.J.E. Rawlins (Ed.), Foundations of genetic algorithms, Morgan Kaufman, Los Altos, pp. 69-93.
[19]             Back, T. (1994). Selective pressure in evolutionary algorithms: a characterization of selection mechanisms. In Proceedings of the First IEEE Conference on Evolutionary Computation, Piscataway, NJ: IEEE press, pp. 57-62.
[20]             Oliver, I.M., Smith, D. J. and Holland, J.R.C. (1987). A study of permutation crossover operators on the traveling salesman problem," Genetic Algorithms and their Applications. Proceedings of the Second International Conference on Genetic Algorithms, Cambridge, MA: Lawrence.
[21]             Syswerda, G. (1989). Uniform crossover in genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, CA: Morgan Kaufmann,pp. 2- 9.
[22]             Michalewics, Z. (1992). Genetic algorithms+ Data structures= Evolution Programs.Springer-Verlag.
[23]             Kalczynski, P. J. and Kamburowski, J. (2008). An improved NEH heuristic to minimize makespan in permutation Flow shops. Computers & Operations Research, Vol. 35, pp.3001-3008.