Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem
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-mak...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/11/2/61 |
| _version_ | 1797482713735757824 |
|---|---|
| author | Leo Hernández-Ramírez Juan Frausto-Solís Guadalupe Castilla-Valdez Javier González-Barbosa Juan-Paulo Sánchez Hernández |
| author_facet | Leo Hernández-Ramírez Juan Frausto-Solís Guadalupe Castilla-Valdez Javier González-Barbosa Juan-Paulo Sánchez Hernández |
| author_sort | Leo Hernández-Ramírez |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T22:36:24Z |
| format | Article |
| id | doaj.art-0f5d6d293c8147c4bef80185a7aef6cf |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-09T22:36:24Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-0f5d6d293c8147c4bef80185a7aef6cf2023-11-23T18:47:03ZengMDPI AGAxioms2075-16802022-01-011126110.3390/axioms11020061Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling ProblemLeo Hernández-Ramírez0Juan Frausto-Solís1Guadalupe Castilla-Valdez2Javier González-Barbosa3Juan-Paulo Sánchez Hernández4Tecnológico Nacional de México/IT Cd Madero, Ciudad Madero 89440, MexicoTecnológico Nacional de México/IT Cd Madero, Ciudad Madero 89440, MexicoTecnológico Nacional de México/IT Cd Madero, Ciudad Madero 89440, MexicoTecnológico Nacional de México/IT Cd Madero, Ciudad Madero 89440, MexicoDirección de Informática, Electrónica y Telecomunicaciones, Universidad Politécnica del Estado de Morelos, Jiutepec 62574, MexicoThe 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.https://www.mdpi.com/2075-1680/11/2/61JJSPScatter SearchCMOSACMOTAhybrid algorithms |
| spellingShingle | Leo Hernández-Ramírez Juan Frausto-Solís Guadalupe Castilla-Valdez Javier González-Barbosa Juan-Paulo Sánchez Hernández Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem Axioms JJSP Scatter Search CMOSA CMOTA hybrid algorithms |
| title | Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem |
| title_full | Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem |
| title_fullStr | Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem |
| title_full_unstemmed | Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem |
| title_short | Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem |
| title_sort | three hybrid scatter search algorithms for multi objective job shop scheduling problem |
| topic | JJSP Scatter Search CMOSA CMOTA hybrid algorithms |
| url | https://www.mdpi.com/2075-1680/11/2/61 |
| work_keys_str_mv | AT leohernandezramirez threehybridscattersearchalgorithmsformultiobjectivejobshopschedulingproblem AT juanfraustosolis threehybridscattersearchalgorithmsformultiobjectivejobshopschedulingproblem AT guadalupecastillavaldez threehybridscattersearchalgorithmsformultiobjectivejobshopschedulingproblem AT javiergonzalezbarbosa threehybridscattersearchalgorithmsformultiobjectivejobshopschedulingproblem AT juanpaulosanchezhernandez threehybridscattersearchalgorithmsformultiobjectivejobshopschedulingproblem |