A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times. (English) Zbl 1510.90123
Summary: This paper addresses a many-objective flexible job-shop scheduling problem with transportation and setup times (MaOFJSP\(\_\)T/S) where the objective is to minimize the makespan, total workload, workload of the critical machine, and penalties of earliness/tardiness. We first present a mathematical model as the representation of the problem, and then establish a network graph model to describe the structural characteristics of the problem and develop a new neighborhood structure. The neighborhood structure defines four move types for different objectives. Next, we propose a hybrid many-objective evolutionary algorithm (HMEA), which is designed to better balance exploitation and exploration. In this algorithm, the tabu search with the neighborhood structure is proposed to improve the local search ability. A reference-point based non-dominated sorting selection is presented to guide the algorithm to search towards the Pareto-optimal front and maintain diversity of solutions. Through three sets of experiments based on 28 benchmark instances, the partial and overall effects of this algorithm are evaluated. The experimental results demonstrate the effectiveness of the proposed HMEA in solving the MaOFJSP\(\_\)T/S.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
many-objective evolutionary algorithm; flexible job-shop scheduling problem; transportation and setup times; neighborhood structure; reference-pointReferences:
| [1] | Abdelmaguid, T. F., A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times, Appl. Math. Comput., 260, 188-203 (2015) · Zbl 1410.90081 |
| [2] | Ahmadi, E.; Zandieh, M.; Farrokh, M.; Emami, S. M., A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms, Comput. Oper. Res., 73, 56-66 (2016) · Zbl 1349.90302 |
| [3] | Amiri, F.; Shirazi, B.; Tajdin, A., Multi-objective simulation optimization for uncertain resource assignment and job sequence in automated flexible job shop, Appl. Soft Comput., 75, 190-202 (2019) |
| [4] | Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Ann. Oper. Res., 41, 3, 157-183 (1993) · Zbl 0775.90227 |
| [5] | Brucker, P.; Schlie, R., Job-shop scheduling with multi-purpose machinesScheduling-Probleme in Jop-Shops mit Mehrzweckmaschinen, Computing, 45, 4, 369-375 (1990) · Zbl 0813.90058 |
| [6] | Chaudhry, I. A.; Khan, A. A., A research survey: Review of flexible job shop scheduling techniques, Int. Trans. Operat. Res., 23, 3, 551-591 (2016) · Zbl 1338.90162 |
| [7] | Cruz-Chávez, M. A.; Martínez-Rangel, M. G.; Cruz-Rosales, M. H., Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem, Int. Trans. Oper. Res., 24, 5, 1119-1137 (2017) · Zbl 1371.90053 |
| [8] | Das, I.; Dennis, J. E., Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 3, 631-657 (1998) · Zbl 0911.90287 |
| [9] | Dauzere-Peres, S.; Paulli, J., An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Ann. Oper. Res., 70, 281-306 (1997) · Zbl 0890.90097 |
| [10] | De Giovanni, L.; Pezzella, F., An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, Eur. J. Oper. Res., 200, 2, 395-408 (2010) · Zbl 1177.90195 |
| [11] | Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints, IEEE Trans. Evol. Comput., 18, 4, 577-601 (2014) |
| [12] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002) |
| [13] | Deng, Q.; Gong, G.; Gong, X.; Zhang, L.; Liu, W.; Ren, Q., A bee evolutionary guiding nondominated sorting genetic algorithm II for multiobjective flexible job-shop scheduling, Comput. Intell. Neurosci., 2017, 1-20 (2017) · Zbl 1426.90142 |
| [14] | Enayatifar, R.; Yousefi, M.; Abdullah, A. H.; Darus, A. N., MOICA: A novel multi-objective approach based on imperialist competitive algorithm, Appl. Math. Comput., 219, 17, 8829-8841 (2013) · Zbl 1291.65174 |
| [15] | Gao, K. Z.; Suganthan, P. N.; Pan, Q. K.; Chua, T. J.; Cai, T. X.; Chong, C. S., Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives, J. Intell. Manuf., 27, 2, 363-374 (2014) · Zbl 1355.90024 |
| [16] | Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1, 2, 117-129 (1976) · Zbl 0396.90041 |
| [17] | Jain, H.; Deb, K., An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach, IEEE Trans. Evol. Comput., 18, 4, 602-622 (2014) |
| [18] | Karimi, S.; Ardalan, Z.; Naderi, B.; Mohammadi, M., Scheduling flexible job-shops with transportation times: mathematical models and a hybrid imperialist competitive algorithm, Appl. Math. Model., 41, 667-682 (2017) · Zbl 1443.90039 |
| [19] | Kung, H. T.; Luccio, F.; Preparata, F. P., On finding the maxima of a set of vectors, J. Assoc. Comput. Mach., 22, 4, 469-476 (1975) · Zbl 0316.68030 |
| [20] | Mastrolilli, M.; Gambardella, L. M., Effective neighbourhood functions for the flexible job shop problem, J. Sched., 3, 1, 3-20 (2000) · Zbl 1028.90018 |
| [21] | Mokhtari, H.; Hasani, A., An energy-efficient multi-objective optimization for flexible job-shop scheduling problem, Comput. Chem. Eng., 104, 339-352 (2017) |
| [22] | Mousakhani, M., Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness, Int. J. Prod. Res., 51, 12, 3476-3487 (2013) |
| [23] | Nouiri, M.; Bekrar, A.; Jemai, A.; Niar, S.; Ammari, A. C., An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem, J. Intell. Manuf., 29, 3, 603-615 (2018) |
| [24] | Nouri, H. E.; Driss, O. B.; Ghedira, K., Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic multiagent model, Comput. Ind. Eng., 102, 488-501 (2016) |
| [25] | Shahsavari-Pour, N.; Ghasemishabankareh, B., A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling, J. Manuf. Syst., 32, 4, 771-780 (2013) |
| [26] | Shen, L. J.; Dauzere-Peres, S.; Neufeld, J. S., Solving the flexible job shop scheduling problem with sequence-dependent setup times, Eur. J. Oper. Res., 265, 2, 503-516 (2018) · Zbl 1374.90171 |
| [27] | Shivasankaran, N.; Kumar, P. S.; Raja, K. V., Hybrid sorting immune simulated annealing algorithm for flexible job shop scheduling, Int. J. Comput. Intell. Syst., 8, 3, 455-466 (2015) |
| [28] | Song, W. J.; Zhang, C. Y.; Lin, W. W.; Shao, X. Y., Flexible job-shop scheduling problem with maintenance activities considering energy consumption, Appl. Mech. Mater., 521, 707-713 (2014) |
| [29] | Sun, X.; Guo, S.; Guo, J.; Du, B., A hybrid multi-objective evolutionary algorithm with heuristic adjustment strategies and variable neighbor-hood search for flexible job-shop scheduling problem considering flexible rest time, IEEE Access, 7, 157003-157018 (2019) |
| [30] | Vilcot, G.; Billaut, J. C., A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem, Int. J. Prod. Res., 49, 23, 6963-6980 (2011) |
| [31] | Vital-Soto, A.; Azab, A.; Baki, M. F., Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility, J. Manuf. Syst., 54, 74-93 (2020) |
| [32] | Wang, C.; Ji, Z.; Wang, Y., Many-objective flexible job shop scheduling using NSGA-III combined with multi-attribute decision making, Mod. Phys. Lett. B, 32, 34n36, 1840110 (2018) |
| [33] | Wang, L.; Cai, J.; Li, M.; Liu, Z., Flexible job shop scheduling problem using an improved ant colony optimization, Sci. Program., 2017, 1-11 (2017) |
| [34] | Wang, Y. M.; Yin, H. L.; Qin, K. D., A novel genetic algorithm for flexible job shop scheduling problems with machine disruptions, Int. J. Adv. Manuf. Technol., 68, 5-8, 1317-1326 (2013) |
| [35] | Xie, N. M.; Chen, N. L., Flexible job shop scheduling problem with interval grey processing time, Appl. Soft Comput., 70, 513-524 (2018) |
| [36] | Xing, L. N.; Chen, W. Y.; Wang, P., Knowledge-based ant colony optimization for flexible job shop scheduling problems, Appl. Soft Comput., 10, 3, 888-896 (2010) |
| [37] | Xu, Y.; Sahnoun, M. H.; Abdelaziz, F. B.; Baudry, D., A simulated multi-objective model for flexible job shop transportation scheduling, Ann. Oper. Res., 1-22 (2020) |
| [38] | Yuan, Y.; Xu, H., Multiobjective flexible job shop scheduling using memetic algorithms, IEEE Trans. Autom. Sci. Eng., 12, 1, 336-353 (2015) |
| [39] | Zarrouk, R.; Bennour, I. E.; Jemai, A., A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem, Swarm Intell., 13, 2, 145-168 (2019) |
| [40] | Zhang, G.; Hu, Y.; Sun, J.; Zhang, W., An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints, Swarm Evol. Comput., 54, 100664 (2020) |
| [41] | Zhang, G. H.; Shao, X. Y.; Li, P. G.; Gao, L., An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Comput. Ind. Eng., 56, 4, 1309-1318 (2009) |
| [42] | Zhang, G. H.; Sun, J. H.; Liu, X.; Wang, G. D.; Yang, Y. Y., Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm, Math. Biosci. Eng., 16, 3, 1334-1347 (2019) · Zbl 1497.90103 |
| [43] | Zhang, M.; Tan, Y.; Zhu, J.; Chen, Y.; Chen, Z., A competitive and cooperative migrating birds optimization algorithm for vary-sized batch splitting scheduling problem of flexible job-shop with setup time, Simul. Model. Pract. Theory, 100, 102065 (2020) |
| [44] | Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007) |
| [45] | Zhang, Q.; Manier, H.; Manier, M. A., A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times, Comput. Oper. Res., 39, 7, 1713-1723 (2012) · Zbl 1251.90208 |
| [46] | Zhang, S.; Li, X.; Zhang, B.; Wang, S., Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system, Eur. J. Oper. Res., 283, 2, 441-460 (2020) · Zbl 1431.90073 |
| [47] | Zhang, X.; Ji, Z.; Wang, Y., An improved SFLA for flexible job shop scheduling problem considering energy consumption, Mod. Phys. Lett. B, 32, 34n36, 1840112 (2018) |
| [48] | Zhang, Z.; Wu, L.; Peng, T.; Jia, S., An improved scheduling approach for minimizing total energy consumption and makespan in a flexible job shop environment, Sustainability, 11, 1, 179 (2019) |
| [49] | Zhou, B. H.; Liao, X. M., Particle filter and Levy flight-based decomposed multi-objective evolution hybridized particle swarm for flexible job shop greening scheduling with crane transportation, Appl. Soft Comput., 91, 1-18 (2020) |
| [50] | Zhu, Z.; Zhou, X., An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints, Comput. Ind. Eng., 140, 106280 (2020) |
| [51] | Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (1999) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
