The week's pick
Reseach Article
An Evolutionary Approach for Solving the N-Jobs M-Machines Permutation Flow-Shop Scheduling Problem with Break-Down Times
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 83 - Number 1 |
| Year of Publication: 2013 |
| Authors: Armando Rosas-gonzalez, Dulce-maria Clemente-guerrero, Santiago-omar Caballero-morales, Jorge-carmen Flores-juan |
10.5120/14409-2488
|
Armando Rosas-gonzalez, Dulce-maria Clemente-guerrero, Santiago-omar Caballero-morales, Jorge-carmen Flores-juan . An Evolutionary Approach for Solving the N-Jobs M-Machines Permutation Flow-Shop Scheduling Problem with Break-Down Times. International Journal of Computer Applications. 83, 1 ( December 2013), 1-6. DOI=10.5120/14409-2488
Abstract
In this paper a Genetic Algorithm (GA) approach is presented to solve the N-Jobs M-Machines Permutation Flow-Shop Scheduling Problem (PFSP) with Break-down times. In comparison with other methods that start with a solution obtained with the Johnson's Algorithm (or another greedy approach), the presented GA method starts with randomly generated solutions and within 100 iterations is able to obtain a solution better than other methods. Also, while in other works the sequence of jobs to be processed in the machines is obtained prior to the occurrence of break-down times, the GA finds the solution considering from the beginning the occurrence of the break-down times. Thus, the presented GA method considers the effect of the break-down times in the overall process. A selection of standard 20×20 PFSPs was used for validation of the GA, finding that in 86% of the selected PFSPs the GA was able to provide job sequences with better makespans when compared with another method. The makespan improvements were statistically significant at the 0. 10 and 0. 01 levels. Then, evaluation of the GA was performed on one PFSP case with break-down times. As in the validation cases with standard PFSPs, the GA outperformed the results obtained with another method.
References
- Gupta, D. , Sharma, S. , and Sharma, S. 2011. Heuristic Approach for n-Jobs, 3-Machines Flow Shop Scheduling Problem, Processing Time Associated With Probabilities Involving Transportation Time, Break-Down Interval, Weightage of Jobs and Job Block Criteria. Mathematical Theory and Modeling. 1(1), 30–36.
- Singhal, E. , Singh, S. , and Dayma, A. 2012. An Improved Heuristic for Permutation Flow Shop Scheduling (NEH ALGORITHM). International Journal of Computational Engineering Research. 2(6), 30–36.
- Emmons, H. and Vairaktarakis, G. 2013. Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications. International Series in Operations Research & Management Science, Springer, New York.
- Baskar, N. , Balasundaram, N. , and Siva, R. 2012. A New Approach to Generate Dispatching Rules for Two Machine Flow Shop Scheduling Using Data Mining. In Proc. of the International Conference on Modeling, Optimization and Computing (ICMOC2012), 238–245.
- Baskar, A. and Xavior, A. 2012. A Simple Model to Optimize General Flow-Shop Scheduling Problems with Known Break Down Time and Weights of Jobs. In Proc. of the International Conference on Modeling, Optimization and Computing (ICMOC 2012), 191–196.
- Chandramouli, A. B. 2005. Heuristic Approach for n-Job, 3-Machine Flow Shop Scheduling Problem Involving Transportation Time, Break Down Time and Weights of Jobs. Mathematical and Computational Applications. 10(2), 301–305.
- Allahverdi, A. and Mittenthal, J. 1994. Two-machine ordered flowshop scheduling under random break-downs. Mathl. Comput. Modelling. 20(2), 9–17.
- Wang, K. and Choi, S. H. 2009. A decomposition based algorithm for flexible flowshop scheduling with machine breakdown. In The IEEE International Conference on Computational Intelligence for Measurement Systems and Applications (CIMSA 2009). 134-139.
- Khodadadi, A. 2012. Solving Weighted Flow-Shop Scheduling Problem Involving Break-Down Time of Jobs for Machines. Journal of International Academic Research. 12(1), 10–15.
- Gupta, D. 2012. Branch and Bound Technique for three stage Flow Shop Scheduling Problem Including Breakdown Interval and Transportation Time. Journal of Information Engineering and Applications. 2(1), 24–29.
- Finke, G. and Jiang, H. 1997. A variant of the permutation flowshop model with variable processing times. Discrete Applied Mathematics. 76, 123–140.
- Akhshabi, M. , Haddadnia, J. , and Akhshabi, M. 2012. Solving flow-shop scheduling problem using a parallel genetic algorithm. Procedia Technology. 1, 351–355.
- Goldberg, D. E. 1989. Genetic Algorithms: in Search, Optimization and Machine Learning. Addison Wesley, Massachusetts.
- Cerrolaza, M. and Annicchiarico, W. 1996. Algoritmos de optimización estructural basados en simulación genética. U. C. V. -Consejo de Desarrollo Científico y Humanístico, Caracas.
- Chan, F. and Choy, K. L. 2011. A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert systems with Applications. 38, 8703–8715.
- Martín, E. and Valeiras, G. 2004. Sistemas Evolutivos y Selección de Indicadores. Universidad de Sevilla-Secretariado de Publicaciones, Sevilla.
- Alander, J. T. 1992. On optimal population size of genetic algorithms. In Proc. of the 6th Annual European Computer Conference.
- Escolano, F. , Cazorla, M. A. , Alfonso, M. I. , Colomina, O. , and Lozano, M. A. 2003. Inteligencia Artificial: Modelos, Técnicas y Áreas de Aplicación. Thomson Ediciones, Madrid.
- Kumar, R. 2012. Blending roulette wheel selection & rank selection in genetic algorithms. International Journal of Machine Learning and Computing. 2(4), 365-370.
- Firas, A. and Reyadh, N. 2012. Comparison of Selection Methods and Crossover Operations using Steady State Genetic Based Intrusion Detection System. Journal of Emerging Trends in Computing and Information Sciences. 3(7), 1053-1058.
- Deep, K. and Mebrahtu, H. 2012. Variant of partially mapped crossover for the Travelling Salesman problems. International Journal of Combinatorial Optimization Problems and Informatics. 3(1), 47–69.
- Watson, J. P. , Barbulescu, L. , Whitley, D. L. , and Howe, A. E. 2002. Contrasting structured and random permutation flow-shop scheduling problems: Search space topology and algorithm performance. INFORMS Journal on Computing. 14(2), 98–123.
Index Terms
Keywords