A hybrid genetic-gravitational search algorithm for a multi-objective flow shop scheduling problem

Abstract: Many real-world problems in manufacturing system, for instance, the scheduling problems, are formulated by defining several objectives for problem solving and decision making. Recently, research on dispatching rules allocation has attracted substantial attention. Although many dispatching rules methods have been developed, multi-objective scheduling problems remain inherently difficult to solve by any single rule. In this paper, a hybrid genetic-based gravitational search algorithm (GSA) in weighted dispatching rule is proposed to tackle a scheduling problem by achieving both time and job-related objectives. Genetic algorithm (GA) is used to select two appropriate dispatching rules to combine as a weighted multi-attribute function, while the GSA is used to optimize the contribution weightage of each rule in each stage of the flow shop. The results show that the proposed algorithm is significantly better than the traditional dispatching rules and the rules allocation algorithm. The proposed algorithm not only improved the quality of the schedule in multi-objective problems but also maintained the advantages of traditional dispatching rules in terms of ease of implementation.

How to cite this paper

 Lee, T., Loong, Y & Tan, S. (2019). A hybrid genetic-gravitational search algorithm for a multi-objective flow shop scheduling problem.International Journal of Industrial Engineering Computations , 10(3), 331-348.

Refrences

Abraham, A., Grosan, C., & Pedrycz, W. (2008). Engineering Evolutionary Intelligent Systems. Springer Berlin Heidelberg.
Chen, T., Rajendran, C,. & Wu, C.W. (2013). Advanced dispatching rules for large-scale manufacturing systems. The International Journal of Advanced Manufacturing Technology, 67(1-4), 1-3.
Choi, S. H., & Wang, K. (2012). Flexible flow shop scheduling with stochastic processing times: A decomposition-based approach. Computers & Industrial Engineering, 63(2), 362-373. doi:10.1016/j.cie.2012.04.001
El Bouri, A. & Amin, G.R. (2015). A combined OWA–DEA method for dispatching rule selection. Computers & Industrial Engineering, 88, 470-478.
Eldos, T. & Qasim, R.A. (2013). On the performance of gravitational search algorithm. International Journal of Advanced Computer Science and Applications, 4(8), 74-78.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company.
Jayamohan, M. S., & Rajendran, C. (2000). A comparative analysis of two different approaches to scheduling in flexible flow shops. Production Planning & Control, 11(6), 572-580. doi:10.1080/095372800414133
Joo, B. J., Choi, Y. C., & Xirouchakis, P. (2013). Dispatching rule-based algorithms for a dynamic flexible flow shop scheduling problem with time-dependent process defect rate and quality Feedback. Procedia CIRP, 7, 163-168.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2008). Algorithm for flexible flow shop problems with unrelated parallel machines, setup times and dual criteria. International Journal of Advance Manufacturing Technology, 37(3-4), 354-370. doi:10.1007/s00170-007-0977-0
Khalouli, S., Ghedjati, F., & Hamzaoui, A. (2010). A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop. Engineering Applications of Artificial Intelligence, 23, 765-771.
Kim, Y.-D., Joo, B.-J., & Shin, J.-H. (2007). Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint. Journal of Heuristics, 15(1), 19-42. doi:10.1007/s10732-007-9061-z
Kumar, Y. & Sahoo, G. (2014). A review on gravitational search algorithm and its applications to data clustering & classification. International Journal of Intelligent Systems and Applications, 6(6), 79-93.
Korytkowski, P., Wiśniewski, T., & Rymaszewski, S. (2013a). An evolutionary simulation-based optimization approach for dispatching scheduling. Simulation Modelling Practice and Theory, 35, 69-85. doi:10.1016/j.simpat.2013.03.006
Korytkowski, P., Rymaszewski, S., & Wiśniewski, T. (2013b). Ant colony optimization for job shop scheduling using multi-attribute dispatching rules. The International Journal of Advanced Manufacturing Technology, 67(1-4), 231-241.
Liptak, B.G. (2005). Instrument Engineers' Handbook, Fourth Edition, Volume Two: Process Control and Optimization. CRC Press.
Li, D., Meng, X., Liang, Q., & Zhao, J. (2014). A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines. Journal of Intelligent Manufacturing, 26(5), 873-890.
Li, D. (2014). A multi-objective TLBO algorithm for balancing two-sided assembly line with multiple constraints. Journal of Intelligent Manufacturing, 27(4), 725-739.
Lu, M.-S., & Liu, Y.-J. (2010). Dynamic dispatching for a flexible manufacturing system based on fuzzy logic. International Journal of Advanced Manufacturing Technology, 54(9-12), 1057-1065.
Morita, H., & Shio, N. (2005). Hybrid branch and bound method with genetic algorithm for flexible flowshop scheduling problem. JSME International Journal Series C-Mechanical Systems Machine Elements and Manufacturing, 48(1), 46-52.
Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013). Learning iterative dispatching rules for job shop scheduling with genetic programming. International Journal of Advanced Manufacturing Technology, 67(1-4), 85-100.
Pérez, M.A.F. and Raupp, F.M.P. (2014). A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, 27(2), 409-416.
Pinedo, M. (2008). Scheduling: Theory, algorithm, and systems (3rd ed.). New York: Springer.
Rashedi, E., Nezamabadi-pour, H., & Saryazdi, S. (2009). GSA: A Gravitational Search Algorithm. Information Sciences, 179(13), 2232-2248.
Ribas, I., Leisten, R., & Framiñan, J. M. (2010). Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers & Operations Research, 37(8), 1439-1454.
Rodriguez, J. A. V., & Salhi, A. (2005, September). Performance of single stage representation genetic algorithms in scheduling flexible flow shops. In 2005 IEEE Congress on Evolutionary Computation (Vol. 2, pp. 1364-1371). IEEE.
Ruiz, R., & Vázquenz-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.
Sabri, N.M., Puteh, M., & Mahmood, M.R. (2013). A review of gravitational search algorithm. International Journal of Advance in Soft Computing, 5(3).
Simon, D. (2013). Evolutionary Optimization Algorithms. Wiley.
Singh, A. & Deep, K. (2015). Real coded genetic algorithm operators embedded in gravitational search algorithm for continuous optimization. International Journal of Intelligent Systems and Applications, 7(12), 1-12.
Spears, W.M. (2000). Evolutionary Algorithms: The Role of Mutation and Recombination. Springer Berlin Heidelberg.
Tian, Y., Li, D., Zhou, P., Guo, R., & Liu, Z. (2018). An ACO-based hyperheuristic with dynamic decision blocks for intercell scheduling. Journal of Intelligent Manufacturing, 29(8), 1905–1921.
Vázquez-Rodríguez, J.A. & Petrovic, S. (2009). A new dispatching rule based genetic algorithm for the multi-objective job shop problem. Journal of Heuristics, 16(6), 771-793.
Wang, K., & Choi, S. H. (2012). A decomposition-based approach to flexible flow shop scheduling under machine breakdown. International Journal of Production Research, 50(1), 215-234. doi:10.1080/00207543.2011.571456
Wang, K., & Choi, S. H. (2014). A holonic approach to flexible flow shop scheduling under stochastic processing times. Computers & Operations Research, 43, 157-168.
Xu, Y. (2013). An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks. The International Journal of Advanced Manufacturing Technology, 67(1-4), 121-135.