×

zbMATH — the first resource for mathematics

An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria. (English) Zbl 1458.90294
Summary: In this paper, a general local search approach for the multi-objective flexible job-shop scheduling problem (MOFJSP) is proposed to determine a Pareto front for any combination of regular criteria. The approach is based on a disjunctive graph, a fast estimation function to evaluate moves and a hierarchical test to efficiently control the set of non-dominated solutions. Four search strategies using two neighborhood structures are developed. Numerical experiments are conducted on test instances of the literature with three sets of criteria to minimize and using metrics to evaluate and compare Pareto fronts. The results show that our approach provides sets of non-dominated solutions of good quality.
MSC:
90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Amjad, M.; Butt, S.; Kousar, R.; Ahmad, R.; Hassam, M.; Faping, Z.; Anjum, N.; Asgher, U., Recent research trends in genetic algorithm based flexible job shop scheduling problems, Math. Prob. Eng., 2018, 1-32, (2018)
[3] Bagheri, A.; Zandieh, M., Bi-criteria flexible job-shop scheduling with sequence-dependent setup times-variable neighborhood search approach, J. Manuf. Syst., 30, 1, 8-15, (2011)
[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] Chaudhry, I. A.; Khan, A. A., A research survey: review of flexible job shop scheduling techniques, Int. Trans. Oper. Res., 23, 3, 551-591, (2016) · Zbl 1338.90162
[6] Chiang, T.-C.; Lin, H.-J., A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling, Int. J. Prod. Econ., 141, 1, 87-98, (2013)
[7] Chun, W.; Zhicheng, J.; Yan, W., A novel memetic algorithm based on decomposition for multiobjective flexible job shop scheduling problem, Math. Prob. Eng., 2017, 1-20, (2013)
[8] Dauzère-Pérès, 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
[9] Dauzère-Pérès, S.; Roux, W.; Lasserre, J., Multi-resource shop scheduling with resource flexibility, Eur. J. Oper. Res., 107, 2, 289-305, (1998) · Zbl 0943.90028
[10] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, vol. 2012, (2001), John Wiley and Sons Chichester · Zbl 0970.90091
[11] Gao, J.; Gen, M.; Sun, L.; Zhao, X., A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems, Comput. Ind. Eng., 53, 1, 149-162, (2007)
[12] Gao, K.; Suganthan, P.; Pan, Q.; Chua, T.; Cai, T.; Chong, C., Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives, J. Intell. Manuf., 1-12, (2014)
[13] García-León, A.; Dauzère-Pérès, S.; Mati, Y., Minimizing regular criteria in the flexible job job-shop scheduling problem, 7th Multidisciplinary International Scheduling Conference: Theory and Applications, 443-456, (2015)
[14] Genova, K.; Kirilov, L.; Guliashki, V., A survey of solving approaches for multiple objective flexible job shop scheduling problems, Cybern. Inf. Technol., 15, 2, 3-22, (2015)
[15] González, M. A.; Vela, C. R.; Varela, R., Scatter search with path relinking for the flexible job shop scheduling problem, Eur. J. Oper. Res., 245, 1, 35-45, (2015) · Zbl 1346.90348
[16] He, Z.; Yang, T.; Deal, D., A multiple-pass heuristic rule for job shop scheduling with due dates, Int. J. Prod. Res., 31, 11, 2677-2692, (1993)
[17] Jia, S.; Hu, Z.-H., Path-relinking tabu search for the multi-objective flexible job shop scheduling problem, Comput. Oper. Res., 47, 11-26, (2014) · Zbl 1348.90274
[18] Johnzen, C.; Dauzère-Pérès, S.; Vialletelle, P., Flexibility measures for qualification management in wafer fabs, Prod. Plann. Control, 22, 1, 81-90, (2011)
[19] Lei, D.; Li, M.; Wang, L., A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold, IEEE Trans. Cybern., 1-13, (2018)
[20] Li, J. J.W. M.L., Hybrid genetic algorithm for flexible job-shop scheduling with multi-objective, J. Inf. Comput. Sci., 8, 11, 2197, (2011)
[21] Li, J.-Q.; Pan, Q.-K.; Gao, K.-Z., Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems, Int. J. Adv. Manuf.Technol., 55, 9, 1159-1169, (2011)
[22] Li, J.-Q.; Pan, Q.-K.; Tasgetiren, M. F., A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities, Appl. Math. Modell., 38, 3, 1111-1132, (2014) · Zbl 1427.90149
[23] Liu, H.; Abraham, A.; Choi, O.; Moon, S. H., Variable neighborhood particle swarm optimization for multi-objective flexible job-shop scheduling problems, Simulated Evolution and Learning, 197-204, (2006), Springer
[24] Lu, C.; Li, X.; Gao, L.; Liao, W.; Yi, J., An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times, Comput. Ind. Eng., 104, 156-174, (2017)
[25] Mati, Y.; Dauzère-Pérès, S.; Lahlou, C., A general approach for optimizing regular criteria in the job-shop scheduling problem, Eur. J. Oper. Res., 212, 1, 33-42, (2011) · Zbl 1237.90093
[26] Mokhtari, H.; Hasani, A., An energy-efficient multi-objective optimization for flexible job-shop scheduling problem, Comput. Chem. Eng., 104, 339-352, (2017)
[27] Mousakhani, M., Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness, Int. J. Prod. Res., 51, 12, 3476-3487, (2013)
[28] Nguyen, S.; Kachitvichyanukul, V., Movement strategies for multi-objective particle swarm optimization, Int. J. Appl. Metaheuristic Comput., 1, 3, 59-79, (2010)
[29] Nie, L.; Gao, L.; Li, P.; Li, X., A gep-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates, J. Intell. Manuf., 24, 4, 763-774, (2013)
[30] Pérez, M. A.F.; Raupp, F. M.P., A newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem, J. Intell. Manuf., 27, 2, 409-416, (2016)
[31] Rahmati, S. H.A.; Zandieh, M.; Yazdani, M., Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem, Int. J. Adv. Manuf.Technol., 64, 5, 915-932, (2013)
[32] Sadrzadeh, A., Development of both the ais and pso for solving the flexible job shop scheduling problem, Arab. J. Sci. Eng., 38, 12, 3593-3604, (2013)
[33] Schott, J. R., Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization., Technical Report, (1995), ir Force Inst of Tech Wright-Patterson AFB OH
[34] Shao, X.; Liu, W.; Liu, Q.; Zhang, C., Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem, Int. J. Adv. Manuf.Technol., 67, 9, 2885-2901, (2013)
[35] Shen, X.-N.; Han, Y.; Fu, J.-Z., Robustness measures and robust scheduling for multi-objective stochastic flexible job shop scheduling problems, Soft Comput., 21, 21, 6531-6554, (2017)
[36] Shi-Jin, W.; Bing-Hai, Z.; Li-Feng, X., A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem, Int. J. Prod. Res., 46, 11, 3027-3058, (2008) · Zbl 1141.90415
[37] Singh, M. R.; Singh, M.; Mahapatra, S. S.; Jagadev, N., Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem, Int. J. Adv. Manuf.Technol., 85, 9, 2353-2366, (2016)
[38] Tay, J. C.; Ho, N. B., Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems, Comput. Ind. Eng., 54, 3, 453-473, (2008)
[39] Trkylmaz, A.; Bulkan, S., A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel vns execution, Int. J. Prod. Res., 53, 6, 1832-1848, (2015)
[40] 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)
[41] Wang, L.; Wang, S.; Liu, M., A pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem, Int. J. Prod. Res., 51, 12, 3574-3592, (2013)
[42] Wisittipanich, W.; Kachitvichyanukul, V., A pareto-archived differential evolution algorithm for multi-objective flexible job shop scheduling problems, Logist. Oper. Supply Chain Manag.Sustain., 325-339, (2014)
[43] Xia, W.; Wu, Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Comput. Ind. Eng., 48, 2, 409-425, (2005)
[44] Xing, L.-N.; Chen, Y.-W.; Yang, K.-W., An efficient search method for multi-objective flexible job shop scheduling problems, J. Intell. Manuf., 20, 3, 283-293, (2009)
[45] Xiong, J.; Tan, X.; Yang, K.-w.; Xing, L.-n.; Chen, Y.-w., A hybrid multiobjective evolutionary approach for flexible job-shop scheduling problems, Math. Prob. Eng., 2012, 1-27, (2012)
[46] Xiong, J.; ning Xing, L.; wu Chen, Y., Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns, Int. J. Prod. Econ., 141, 1, 112-126, (2013)
[47] Yuan, Y.; Xu, H., Multiobjective flexible job shop scheduling using memetic algorithms, IEEE Trans. Autom. Sci.Eng., 12, 1, 336-353, (2015)
[48] Zhang, G.; Shao, X.; Li, P.; 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)
[49] Zhang, R.; Wu, C., A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective, Comput. Oper. Res., 38, 5, 854-867, (2011) · Zbl 1202.90150
[50] Zitzler, E., Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, (1999), ETH Zurich, Switzerland, Ph.D. thesis
[51] Zitzler, E.; Brockhoff, D.; Thiele, L., The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration, Evolutionary multi-criterion optimization, 862-876, (2007), Springer
[52] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 2, 117-132, (2003)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.