{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T04:14:57Z","timestamp":1768796097345,"version":"3.49.0"},"reference-count":41,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>The Job Shop Scheduling Problem (JSSP) consists of finding the best scheduling for a set of jobs that should be processed in a specific order using a set of machines. This problem belongs to the NP-hard class problems and has enormous industrial applicability. In the manufacturing area, decision-makers consider several criteria to elaborate their production schedules. These cases are studied in multi-objective optimization. However, few works are addressed from this multi-objective perspective. The literature shows that multi-objective evolutionary algorithms can solve these problems efficiently; nevertheless, multi-objective algorithms have slow convergence to the Pareto optimal front. This paper proposes three multi-objective Scatter Search hybrid algorithms that improve the convergence speed evolving on a reduced set of solutions. These algorithms are: Scatter Search\/Local Search (SS\/LS), Scatter Search\/Chaotic Multi-Objective Threshold Accepting (SS\/CMOTA), and Scatter Search\/Chaotic Multi-Objective Simulated Annealing (SS\/CMOSA). The proposed algorithms are compared with the state-of-the-art algorithms IMOEA\/D, CMOSA, and CMOTA, using the MID, Spacing, HV, Spread, and IGD metrics; according to the experimental results, the proposed algorithms achieved the best performance. Notably, they obtained a 47% reduction in the convergence time to reach the optimal Pareto front.<\/jats:p>","DOI":"10.3390\/axioms11020061","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T08:20:29Z","timestamp":1643617229000},"page":"61","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem"],"prefix":"10.3390","volume":"11","author":[{"given":"Leo","family":"Hern\u00e1ndez-Ram\u00edrez","sequence":"first","affiliation":[{"name":"Tecnol\u00f3gico Nacional de M\u00e9xico\/IT Cd Madero, Ciudad Madero 89440, Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9307-0734","authenticated-orcid":false,"given":"Juan","family":"Frausto-Sol\u00eds","sequence":"additional","affiliation":[{"name":"Tecnol\u00f3gico Nacional de M\u00e9xico\/IT Cd Madero, Ciudad Madero 89440, Mexico"}]},{"given":"Guadalupe","family":"Castilla-Valdez","sequence":"additional","affiliation":[{"name":"Tecnol\u00f3gico Nacional de M\u00e9xico\/IT Cd Madero, Ciudad Madero 89440, Mexico"}]},{"given":"Javier","family":"Gonz\u00e1lez-Barbosa","sequence":"additional","affiliation":[{"name":"Tecnol\u00f3gico Nacional de M\u00e9xico\/IT Cd Madero, Ciudad Madero 89440, Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9448-1946","authenticated-orcid":false,"given":"Juan-Paulo","family":"S\u00e1nchez Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Direcci\u00f3n de Inform\u00e1tica, Electr\u00f3nica y Telecomunicaciones, Universidad Polit\u00e9cnica del Estado de Morelos, Jiutepec 62574, Mexico"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","article-title":"PageRank: The complexity of flowshop and jobshop scheduling","volume":"1","author":"Garey","year":"1976","journal-title":"Math. Oper. Res."},{"key":"ref_2","unstructured":"Pinedo, M. (2016). Scheduling Theory Algorithm, and Systems, Springer. [5th ed.]."},{"key":"ref_3","unstructured":"Yang, Y.B. (2021, November 29). Methods and Techniques Used for Job Shop Scheduling, MSc. Research Project, Florida Technological University. Available online: https:\/\/stars.library.ucf.edu\/cgi\/viewcontent.cgi?article=1389&context=rtd."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/j.asoc.2008.04.013","article-title":"Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling","volume":"9","author":"Xing","year":"2009","journal-title":"Appl. Soft Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1109\/TASE.2013.2274517","article-title":"Multiobjective flexible job shop scheduling using memetic algorithms","volume":"12","author":"Yuan","year":"2015","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.eswa.2015.09.050","article-title":"An object-oriented approach for multi-objective flexible job-shop scheduling problem","volume":"45","author":"Kaplanoglu","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_7","first-page":"217","article-title":"Variational principles in set optimization with domination structures and application to changing jobs","volume":"1","author":"Bao","year":"2019","journal-title":"J. Appl. Numer. Optim."},{"key":"ref_8","first-page":"1","article-title":"Optimality and duality for nonsmooth multiobjective fractional problems using convexificators","volume":"2021","author":"Luu","year":"2021","journal-title":"J. Nonlinear Funct. Anal."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10957-018-1258-9","article-title":"Inexact Multi-Objective Local Search Proximal Algorithms: Application to Group Dynamic and Distributive Justice","volume":"177","author":"Pereira","year":"2018","journal-title":"J. Optim. Theory Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1111\/j.1540-5915.1977.tb01074.x","article-title":"Heuristics for integer programming using surrogate constraints","volume":"8","author":"Glover","year":"1977","journal-title":"Decis. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Frausto-Solis, J., Hern\u00e1ndez-Ram\u00edrez, L., Castilla-Valdez, G., Gonz\u00e1lez-Barbosa, J., and S\u00e1nchez, J. (2021). Chaotic multi-objective simulated annealing and threshold accepting for job shop scheduling problem. Math. Comput. Appl., 26.","DOI":"10.3390\/mca26010008"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/s00170-004-2492-x","article-title":"Pareto archived simulated annealing for job shop scheduling with multiple objectives","volume":"29","author":"Suresh","year":"2006","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/TEVC.2007.900837","article-title":"A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA","volume":"12","author":"Bandyopadhyay","year":"2008","journal-title":"Evol. Comput. IEEE Trans."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II. International Conference on Parallel Problem Solving from Nature, Spring.","DOI":"10.1007\/3-540-45356-3_83"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s10845-009-0294-6","article-title":"A two-stage genetic algorithm for multiobjective job shop scheduling problems","volume":"22","author":"Kachitvichyanukul","year":"2009","journal-title":"J. Intell. Manuf."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1080\/0951192X.2016.1187301","article-title":"An improved MOEA\/D for multiobjective job shop scheduling problem","volume":"30","author":"Zhao","year":"2016","journal-title":"Int. J. Comput. Integr. Manuf."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1162\/106365600568202","article-title":"Comparison of Multiobjective Evolutionary Algorithms: Empirical Results","volume":"8","author":"Zitzler","year":"2000","journal-title":"Evol. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"4024","DOI":"10.1016\/j.eswa.2009.09.005","article-title":"Bi-objective group scheduling in hybrid flexible flowshop: A multi-phase approach","volume":"37","author":"Karimi","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez, M., Oddi, A., and Rasconi, R. (2017, January 18\u201323). Multiobjective optimization in a job shop with energy costs through hybrid evolutionary techniques. Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, Pittsburgh, PA, USA.","DOI":"10.1609\/icaps.v27i1.13809"},{"key":"ref_20","first-page":"225","article-title":"Probabilistic learning combinations of local job-shop scheduling rules","volume":"1","author":"Fisher","year":"1963","journal-title":"Ind. Sched."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"M\u00e9ndez-Hern\u00e1ndez, B., Rodriguez Bazan, E.D., Martinez, Y., Libin, P., and Nowe, A. (2019, January 17\u201319). A Multiobjective Reinforcement Learning Algorithm for JSSP. Proceedings of the 28th International Conference on Artificial Neural Networks, Munich, Germany.","DOI":"10.1007\/978-3-030-30487-4_44"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1809","DOI":"10.1007\/s10845-017-1350-2","article-title":"Review of job shop scheduling research and its new perspectives under Industry 4.0","volume":"30","author":"Zhang","year":"2019","journal-title":"J. Intell. Manuf."},{"key":"ref_23","unstructured":"Deb, K. (2001). Multiobjective Optimization Using Evolutionary Algorithms, Wiley."},{"key":"ref_24","unstructured":"Coello, C., Veldhuizen, D., and Lamont, G. (2007). Evolutionary Algorithms for Solving Multiobjective Problems, Springer. [2nd ed.]."},{"key":"ref_25","first-page":"878","article-title":"A critical survey of performance indices for multiobjective optimisation","volume":"Volume 2","author":"Okabe","year":"2003","journal-title":"Proceedings of the 2003 Congress on Evolutionary Computation, 2003. CEC \u201903, Canberra, ACT, Australia, 8\u201312 December 2003"},{"key":"ref_26","unstructured":"Schott, J.R. (1995). Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. [Master\u2019s Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology]."},{"key":"ref_27","unstructured":"Veldhuizen, D.A.V. (1999). Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. [Ph.D. Thesis, Air Force Institute of Technology, Wright-Patterson AFB]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s10710-005-6164-x","article-title":"Solving Multiobjective Optimization Problems Using an Artificial Immune System","volume":"6","author":"Coello","year":"2005","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_29","unstructured":"Sawaragi, Y., Nakagama, H., and Tanino, T. (1985). Theory of Multiobjective Optimization, Springer."},{"key":"ref_30","unstructured":"Bakuli, D.L. (2015). A Survey of Multiobjective Scheduling Techniques Applied to the Job Shop Problem (JSP). Applications of Management Science: In Productivity, Finance, and Operations, Emerald Group Publishing Limited."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1287\/mnsc.30.9.1093","article-title":"Sequencing rules and due-date assignments in job shop","volume":"30","author":"Baker","year":"1984","journal-title":"Manag. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.ejor.2011.01.046","article-title":"A general approach for optimizing regular criteria in the job-shop scheduling problem","volume":"212","author":"Yazid","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0021-9991(90)90201-B","article-title":"Threshold Accepting: A General Purpose Algorithm Appearing Superior to Simulated Annealing","volume":"90","author":"Dueck","year":"1990","journal-title":"J. Comput. Phys."},{"key":"ref_34","first-page":"671","article-title":"Optimization by simulated annealing. Am. Assoc","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Adv. Sci."},{"key":"ref_35","unstructured":"Sanvicente, S.H., and Frausto, J. (2004, January 14\u201317). A method to establish the cooling scheme in simulated annealing like algorithms. Proceedings of the International Conference on Computational Science and Its Applications, Assisi, Italy."},{"key":"ref_36","first-page":"457","article-title":"Simple Mathematical Models with Very Complicated Dynamics","volume":"26","author":"May","year":"1976","journal-title":"Nature"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The shifting bottleneck procedure for job shop scheduling","volume":"34","author":"Adams","year":"1988","journal-title":"Manag. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1287\/ijoc.3.2.149","article-title":"A computational study of the job-shop scheduling problem","volume":"3","author":"Applegate","year":"1991","journal-title":"ORSA J. Comput."},{"key":"ref_39","unstructured":"Lawrence, S. (1984). Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University."},{"key":"ref_40","unstructured":"Yamada, T., and Nakano, R. (, January 28\u201330). A genetic algorithm applicable to large-scale job-shop problems. Proceedings of the Second International Conference on Parallel Problem Solving from Nature, Brussels, Belgium."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0377-2217(93)90182-M","article-title":"Benchmarks for basic scheduling problems","volume":"64","author":"Taillard","year":"1993","journal-title":"Eur. J. Oper. Res."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/2\/61\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:11:52Z","timestamp":1760134312000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/2\/61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":41,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["axioms11020061"],"URL":"https:\/\/doi.org\/10.3390\/axioms11020061","relation":{},"ISSN":["2075-1680"],"issn-type":[{"value":"2075-1680","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]}}}