Reference group genetic algorithm for flexible job shop scheduling problem with multiple objective functions

Document Type: Research Paper

Authors

Industrial Engineering Department, Semnan University, Semnan, Iran

Abstract

This article studies flexible job-shop scheduling problem (FJSSP) considering three objective functions. The objectives are minimizing maximum completion time (Cmax), the maximum machine workload (Wmax), and the total workload (WT). After presenting the mathematical model of the problem, a genetic algorithm called Reference Group Genetic Algorithm(RGGA) is used to solve the problem. RGGA implements the reference group concept in the sociology to the genetic algorithm. The term " reference group" is credited to sociologist Robert K. Merton. Three standard data sets are used to evaluate the performance of RGGA. On the first data set, RGGA is compared to six algorithms in the literature, on the second data set RGGA is compared to four algorithms in the literature, and on the third data set RGGA is compared to three algorithms in the literature. Moreover, RGGA is compared with optimum solution in small size problem. Results show the superiority of RGGA in comparison to other algorithms.

Keywords

Main Subjects


Abdelmaguid, T. F. (2015). A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times. Applied Mathematics and Computation, 260(188-203.

Al-Hinai, N., &ElMekkawy, T. Y. (2011). Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. International Journal of Production Economics, 132(2), 279-291.

Bagheri, A.,  Zandieh, M.,  Mahdavi, I., &Yazdani, M. (2010). An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems, 26(4), 533-541.

Beheshtinia, M. A., &Ghasemi, A. (2018). A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system. Engineering Optimization, 50(9), 1415-1433.

Beheshtinia, M. A.,  Ghasemi, A., &Farokhnia, M. (2018). Supply chain scheduling and routing in multi-site manufacturing system (case study: a drug manufacturing company). Journal of Modelling in Management, 13(1), 27-49.

Borumand, A., &Beheshtinia, M. A. A developed genetic algorithm for solving the multi-objective supply chain scheduling problem. Kybernetes, 0(0), null.

Bożejko, W.,  Uchroński, M., &Wodecki, M. (2010). Parallel hybrid metaheuristics for the flexible job shop problem. Computers & Industrial Engineering, 59(2), 323-333.

Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183.

Chen, J. C.,  Wu, C.-C.,  Chen, C.-W., &Chen, K.-H. (2012). Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm. Expert Systems with Applications, 39(11), 10016-10021.

Chiang, T.-C., &Lin, H.-J. (2013). A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. International Journal of Production Economics, 141(1), 87-98.

De Giovanni, L., &Pezzella, F. (2010). An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem. European Journal of Operational Research, 200(2), 395-408.

Farazmand, N., &Beheshtinia, M. (2018). Multi-objective optimization of time-cost-quality-carbon dioxide emission-plan robustness in construction projects. Journal of Industrial and Systems Engineering, 11(3), 0-0.

Fattahi, P.,  Saidi Mehrabad, M., &Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18(3), 331-342.

Gao, J.,  Sun, L., &Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35(9), 2892-2907.

Gen, M.,  Gao, J., &Lin, L. (2009). Multistage-Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem. Intelligent and Evolutionary Systems. Springer Berlin Heidelberg.

Gong, G.,  Deng, Q.,  Gong, X.,  Liu, W., &Ren, Q. (2018). A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators. Journal of Cleaner Production, 174(560-576.

Huang, R.-H.,  Yang, C.-L., &Cheng, W.-C. (2013). Flexible job shop scheduling with due window—a two-pheromone ant colony approach. International Journal of Production Economics, 141(2), 685-697.

Jia, H. Z.,  Nee, A. Y. C.,  Fuh, J. Y. H., &Zhang, Y. F. (2003). A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing, 14(3/4), 351-362.

Kacem, I.,  Hammadi, S., &Borne, P. (2002). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 32(1), 1-13.

Kaplanoğlu, V. (2016). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications, 45(71-84.

Karimi, H.,  Rahmati, S. H. A., &Zandieh, M. (2012). An efficient knowledge-based algorithm for the flexible job shop scheduling problem. Knowledge-Based Systems, 36(236-244.

Li, J.-q., &Pan, Q.-k. (2013). Chemical-reaction optimization for solving fuzzy job-shop scheduling problem with flexible maintenance activities. International Journal of Production Economics, 145(1), 4-17.

Liu, B.,  Fan, Y., &Liu, Y. (2015). A fast estimation of distribution algorithm for dynamic fuzzy flexible job-shop scheduling problem. Computers & Industrial Engineering, 87(193-201.

Merton, R. K. (2011). Sociology of Science and Sociology as Science (Vol. NewYork: Columbia University Press.

Moslehi, G., &Mahnam, M. (2011). A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics, 129(1), 14-22.

Najian, M. H., &Beheshtinia, M. A. (2018). Supply Chain Scheduling Using a Transportation System Composed of Vehicle Routing Problem and Cross-Docking Approaches. International Journal of Transportation Engineering, -.

Ong, Z. X.,  Tay, J. C., &Kwoh, C. K. (2005). Applying the Clonal Selection Principle to Find Flexible Job-Shop Schedules. Artificial Immune Systems. Springer Berlin Heidelberg.

Pezzella, F.,  Morganti, G., &Ciaschetti, G. (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, 35(10), 3202-3212.

Shahsavari-Pour, N., &Ghasemishabankareh, B. (2013). A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. Journal of Manufacturing Systems, 32(4), 771-780.

Shen, L.,  Dauzère-Pérès, S., &Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265(2), 503-516.

Shi-Jin, W.,  Bing-Hai, Z., &Li-Feng, X. (2008). A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem. International Journal of Production Research, 46(11), 3027-3058.

Sreekara Reddy, M. B. S.,  Ratnam, C. h.,  Agrawal, R.,  Varela, M. L. R.,  Sharma, I., &Manupati, V. K. (2017). Investigation of reconfiguration effect on makespan with social network method for flexible job shop scheduling problem. Computers & Industrial Engineering, 110(231-241.

Tang, J.,  Zhang, G.,  Lin, B., &Zhang, B. (2011). A Hybrid Algorithm for Flexible Job-Shop Scheduling Problem. Procedia Engineering, 15(3678-3683.

Thammano, A., &Phu-ang, A. (2013). A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-shop Scheduling Problem. Procedia Computer Science, 20(96-101.

Wang, L.,  Wang, S.,  Xu, Y.,  Zhou, G., &Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62(4), 917-926.

Wu, X., &Sun, Y. (2018). A green scheduling algorithm for flexible job shop with energy-saving measures. Journal of Cleaner Production, 172(3249-3264.

Xia, W., &Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409-425.

Yin, L.,  Li, X.,  Gao, L.,  Lu, C., &Zhang, Z. (2017). A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem. Sustainable Computing: Informatics and Systems, 13(15-30.

Zegordi, S. H.,  Abadi, I. N. K., &Nia, M. A. B. (2010). A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain. Computers & Industrial Engineering, 58(3), 373-381.

Zhang, Q.,  Manier, H., &Manier, M. A. (2012). A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Computers & Operations Research, 39(7), 1713-1723.