Published
Minimising Total Flowtime in a No-Wait Flow Shop (NWFS) using Genetic Algorithms
Minimizar el tiempo de flujo total en un Flow shop sin escalas (NWFS) utilizando algoritmos genéticos
DOI:
https://doi.org/10.15446/ing.investig.v38n3.75281Keywords:
Genetic algorithm (GA), Scheduling, No-wait, Flow shop (en)Algoritmo genético (AG), Secuenciación, Líneas de flujo sin espera, Flow shop (es)
This paper considers a no-wait flow shop scheduling (NWFS) problem, where the objective is to minimise the total flowtime. We propose a genetic algorithm (GA) that is implemented in a spreadsheet environment. The GA functions as an add-in in the spreadsheet. It is demonstrated that with proposed approach any criteria can be optimised without modifying the GA routine or spreadsheet model. Furthermore, the proposed method for solving this class of problem is general purpose, as it can be easily customised by adding or removing jobs and machines. Several benchmark problems already published in the literature are used to demonstrate the problem-solving capability of the proposed approach. Benchmark problems set ranges from small (7-jobs, 7 machines) to large (100-jobs, 10-machines). The performance of the GA is compared with different meta-heuristic techniques used in earlier literature. Experimental analysis demonstrate that solutions obtained in this research offer equal quality as compared to algorithms already developed for NWFS problems.
Este documento considera un problema de secuenciación de líneas de flujo sin espera (NWFS), donde el objetivo es minimizar el tiempo de flujo total. Proponemos un algoritmo genético (GA) que se implementa en un entorno de hoja de cálculo. El GA funciona como un complemento en la hoja de cálculo. Se demuestra que, con el enfoque propuesto, cualquier criterio puede optimizarse sin modificar la rutina del GA o el modelo de hoja de cálculo. Además, el método propuesto para resolver este problema de clase es de propósito general, ya que se puede personalizar fácilmente agregando o eliminando tareas y máquinas. Varios problemas de referencia ya publicados en la literatura se usan para demostrar la capacidad de resolución de problemas del enfoque propuesto. El conjunto de problemas de la evaluación tiene un rango que varía desde pequeños (7 trabajos, 7 máquinas) hasta grandes (100 trabajos, 10 máquinas). El rendimiento del GA se compara con diferentes técnicas meta-heurísticas utilizadas en la literatura anterior. El análisis experimental demuestra que las soluciones obtenidas en esta nueva búsqueda ofrecen igual calidad que los algoritmos ya desarrollados para el problema NWFS.
References
Akhshabi, M., Tavakkoli-Moghaddam, R., & Rahnamay-Roodposhti, F. (2014). A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time. The International Journal of Advanced Manufacturing Technology, 70(5-8), 1181-1188. DOI: 10.1007/s00170-013-5351-9.
Aldowaisan, T., & Allahverdi, A. (2004). New heuristics for m-machine no-wait flowshop to minimize total completion time. Omega, 32(5), 345-352. DOI: 10.1016/j.omega.2004.01.004.
Astaiza A, L. G. (2005). A practical approach to scheduling examinations. Ingeniería e Investigación, 25(3), 92-100.
Bertolissi, E. (2000). Heuristic algorithm for scheduling in the no-wait flow-shop. Journal of Materials Processing Technology, 107(1–3), 459-465. DOI: 10.1016/S0924- 0136(00)00720-2.
Bewoor, L., Chandra Prakash, V., & Sapkal, S. (2017a). Evolutionary Hybrid Particle Swarm Optimization Algorithm for Solving NP-Hard No-Wait Flow Shop Scheduling Problems. Algorithms, 10(4), 121. DOI: 10.3390/a10040121.
Bewoor, L. A., Prakash, V. C., & Sapkal, S. U. (2017b). Comparative Analysis of Metaheuristic Approaches for m-Machine No Wait Flow Shop Scheduling for minimizing Total Flow Time with Stochastic Input. International Journal of Engineering and Technology, 8(6), 3021-3026. DOI: 10.21817/ ijet/2016/v8i6/160806265.
Bewoor, L. A., Prakash, V. C., & Sapkal, S. U. (2018). Production scheduling optimization in foundry using hybrid Particle Swarm Optimization algorithm. Procedia Manufacturing, 22, 57-64. DOI: 10.1016/j.promfg.2018.03.010.
Carlier, J. (1978). Ordonnancements a contraintes disjonctives. R.A.I.R.O. Recherche operationelle/Operations Research, 12(4), 333-350. DOI: 10.1051/ro/1978120403331.
Chaudhry, I. A., Ahmed, R., & Khan, A. M. (2014). Genetic Algorithm to minimize flowtime in a no-wait flowshop scheduling problem. IOP Conference Series: Materials Science and Engineering, 65(1), 1-6. DOI: 10.1088/1757- 899X/65/1/012007.
Chaudhry, I. A., & Elbadawi, I. A. Q. (2017). Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm. Sadhana - Academy Proceedings in Engineering Sciences, 42(1), 11-21. DOI: 10.1007/ s12046-016-0575-7.
Chaudhry, I. A., & Khan, A. M. (2012). Minimizing makespan for a no-wait flowshop using genetic algorithm. Sadhana - Academy Proceedings in Engineering Sciences, 37(6), 695- 707. DOI: 10.1007/s12046-012-0105-1.
Davis, L. (1985). Job Shop Scheduling with Genetic Algorithms. Paper presented at the Proceedings of the 1st International Conference on Genetic Algorithms.
Delgado, E., Rodríguez, C. J. C., & Velasco, Ó. G. D. (2005). Applying genetic algorithms for programming manufactoring cell tasks. Ingeniería e Investigación, 25(2), 24-31.
Díaz Ramírez, J., & Huertas, J. I. (2018). A continuous time model for a short-term multiproduct batch process sche duling. Ingeniería e Investigación, 38(1), 96-104. DOI: 10.15446/ing.investig.v38n1.66425.
Dong, B., Gao, K.-z., Pan, Q.-k., & Sun, Q.-q. (2010). Hybrid differential evolution optimization algorithm for no-wait flow shop problem with total flow time criterion. Application Research of Computers, 27(8), 2875-2877. DOI: 10.1007/978-3-642-24728-6_81.
Framinan, J. M., & Leisten, R. (2003). An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega - International Journal of Management Science, 31(4), 311-317. DOI: 10.1016/s0305-0483(03)00047-1.
Frutos, M., & Tohmé, F. (2012). Evolutionary multi-objective scheduling procedures in non-standardized production processes. DYNA, 79(172), 101-107.
Gao, K.-Z., Pan, Q.-K., & Li, J.-Q. (2011a). Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion. International Journal of Advanced Manufacturing Technology, 56(5-8), 683-692. DOI: 10.1007/s00170-011-3197-6.
Gao, K.-Z., Pan, Q.-K., Li, J.-Q., & Jia, B.-X. (2011b). Improved Harmony Search Algorithm for No-Wait Flow Shop Schedule. Computer Engineering, 37(8), 178-180. DOI: 10.3969/j.issn.1000-3428.2011.08.061.
Gao, K.-Z., Pan, Q.-K., Li, J.-Q., Wang, Y.-T., & Liang, J. (2012). A hybrid harmony search algorithm for the no-wait flowshop scheduling problems. Asia-Pacific Journal of Operational Research, 29(2), 1250012/1250011-1250023. DOI: 10.1142/S0217595912500121.
Gao, K.-z., Pan, Q., Li, J., & He, Y. (2010). A novel grouping harmony search algorithm for the no-wait flow shop scheduling problems with total flow time criteria. Paper presented at the 2010 International Symposium on Computer Communication Control and Automation (3CA) Tainan, Taiwan. DOI: 10.1109/3CA.2010.5533729.
Gao, K.-z., Pan, Q., Suganthan, P. N., & Li, J. (2013). Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization. International Journal of Advanced Manufacturing Technology, 66(9-12), 1563- 1572. DOI: 10.1007/s00170-012-4440-5.
Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research, 12(5), 655-679. DOI: 10.1287/opre.12.5.655.
Guang, X., & Junqing, L. (2012). Evolved Discrete Harmony Search Algorithm for Multi-objective No-wait Flow Shop Scheduling Problem. Paper presented at the 2nd International Conference on Computer Application and System Modeling, Taiyuan Institute of Science and Technology, Taiyuan, Shanxi, China. DOI: 10.2991/iccasm.2012.200.
Gupta, J. N. D., & Stafford Jr, E. F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169(3), 699-711. DOI: 10.1016/j. ejor.2005.02.001.
Hall, N., & Sriskandarajah, C. (1996). A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Operations Research, 44(3), 510-525. DOI: 10.2307/171711.
Hans, R. (1984). The Three-Machine No-Wait Flow Shop is NP-Complete. Journal of the Association for Computing Machinery, 31(2), 336-345. DOI: 10.1145/62.65.
Heller, J. (1960). Some Numerical Experiments for an M × J Flow Shop and Its Decision - Theoretical Aspects. Operations Research, 8(2), 178-184. DOI: 10.1287/opre.8.2.178.
Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.
Huang, R.-H., Yang, C.-L., & Liu, S.-C. (2015). No-Wait Flexible Flow Shop Scheduling with Due Windows. Mathematical Problems in Engineering, 9 pages. DOI: 10.1155/2015/456719.
Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68. DOI: 10.1002/ nav.3800010110.
Laha, D., & Chakraborty, U. K. (2008). A constructive heuristic for minimizing makespan in no-wait flow shop scheduling. International Journal of Advanced Manufacturing Technology, 41(1-2), 97-109. DOI: 10.1007/s00170-008-1454-0.
Laha, D., Gupta, J. N. D., & Sapkal, S. U. (2014a). A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops. Journal of the Operational Research Society, 65(10), 1611-1624. DOI: 10.1057/ jors.2013.118.
Laha, D., & Sapkal, S. U. (2011). An Efficient Heuristic Algorithm for m-Machine No-wait flow shops. Paper presented at the International MultiConference of Engineers and Computer Scientists, Hong Kong.
Laha, D., & Sapkal, S. U. (2014b). An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop. Computers & Industrial Engineering, 67, 36-43. DOI: 10.1016/j.cie.2013.08.026.
Miyata, H. H., Nagano, M. S., & Gupta, J. N. D. (2018). Incorporating preventive maintenance into the m-machine no-wait flow-shop scheduling problem with total flow-time minimization: a computational study. Engineering Optimization, 1-19. DOI: 10.1080/0305215X.2018.1485903.
Nagano, M. S., Miyata, H. H., & Araújo, D. C. (2015). A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times. Journal of Manufacturing Systems, 36, 224–230. DOI: 10.1016/j.jmsy.2014.06.007.
Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega - International Journal of Management Science, 11(1), 91-95. DOI: 10.1016/0305-0483(83)90088-9.
Qi, X., Wang, H., Zhu, H., Zhang, J., Chen, F., & Yang, J. (2016). Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization. International Journal of Production Research, 54(16), 4957- 4972. DOI: 10.1080/00207543.2016.1150615.
Rajendran, C., & Chaudhuri, D. (1990). Heuristic algorithms for continuous flow-shop problem. Naval Research Logistics, 37(5), 695-705. DOI: 10.1002/1520-6750(199010)37:53.0.CO;2-L.
Reddi, S. S., & Ramamoorthy, C. V. (1972). On the Flow-Shop Sequencing Problem with No Wait in Process. Journal of the Operational Research Society, 23(3), 323-331. DOI: 10.1057/jors.1972.52.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), 5-13. DOI: 10.1016/0305-0548(93)E0014-K.
Sapkal, S. U., & Laha, D. (2013). A heuristic for no-wait flow shop scheduling. International Journal of Advanced Manufacturing Technology, 68(5-8), 1327-1338. DOI: 10.1007/ s00170-013-4924-y.
Shafaei, R., Moradinasab, N., & Rabiee, M. (2011). Efficient meta heuristic algorithms to minimize mean flow time in no-wait two stage flow shops with parallel and identical machines. International Journal of Management Science and Engineering Management, 6(6), 421-430. DOI: 10.1080/17509653.2011.10671192.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285. DOI: 10.1016/0377-2217(93)90182-M.
Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Buyukdagli, O. (2013). A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Computers & Operations Research, 40(7), 1729-1743. DOI: 10.1016/j.cor.2013.01.005.
Tyagi, N., Varshney, N. G., & Chandramouli, A. B. (2013). Six decades of flowshop scheduling research. International Jouranal of Scientific & Engineering Research, 4(9), 854-864.
Whitley, D., & Kauth, K. (1988). GENITOR: A different genetic algorithm. Paper presented at the Proceedings of the 1988 Rocky Mountain Conference on Artificial Intelligence.
Ying, K.-C., Lin, S.-W., & Wu, W.-J. (2016). Self-adaptive ruin-and-recreate algorithm for minimizing total flow time in no-wait flowshops. Computers & Industrial Engineering, 101(C), 167-176. DOI: 10.1016/j.cie.2016.08.014.
Zhu, X., & Li, X. (2015). Iterative search method for total flowtime minimization no-wait flowshop problem. International Journal of Machine Learning and Cybernetics, 6(5), 747–761. DOI: 10.1007/s13042-014-0312-7.
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2018 Imran Ali Chaudhry, Isam AbdulQader Elbadawi, Muhammad Usman, Muhammad Tajammal Chughtai
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
