Multi-objective Iterated Local Search based on decomposition for job scheduling problems with machine deterioration effect

• Published in: Engineering applications of artificial intelligence 2022-06, Vol.112, p.104826, Article 104826
• Main Authors: Santos, Vívian Ludimila Aguiar, Carvalho, Thales Francisco Mota, de Assis, Luciana Pereira, Weiss-Cohen, Miri, Guimarães, Frederico Gadelha
• Format: Article
• Language: English
• Subjects: Decomposition and aggregation; Deterioration effect; Job scheduling; Meta-heuristics; Multi-objective optimization; Unrelated parallel machine
• ISSN: 0952-1976; 1873-6769
• DOI: 10.1016/j.engappai.2022.104826

This work addresses an unrelated parallel machine scheduling problem in which the jobs cause deterioration of the machines. This factor decreases the performance of the machines, increasing the processing times of the jobs over time. We propose a mixed-integer nonlinear programming model for the problem that has two objectives: to minimize the maximum completion time of jobs (makespan) and to minimize the total time of delay of the jobs. In this paper, we also develop a different approach to extend Iterated Local Search (ILS) meta-heuristic to multi-objective problems. The Iterated Local Search Based on Decomposition (ILS/D) employs the decomposition strategy similar to the Multi-objective Evolutionary Algorithm Based on Decomposition (MOEA/D), in which the ILS is used as the search engine to improve the search process within the structure of the MOEA/D. We compared the ILS/D, MOEA/D and Non-dominated Sorting Genetic Algorithm II (NSGA-II) algorithms. The results show that the ILS/D outperforms the MOEA/D and NSGA-II algorithms by a significant margin. These findings show that the decomposition strategy is beneficial not only for evolutionary algorithms, but is also an efficient way to extend the ILS to multi-objective problems. •Multi-objective approach to job scheduling problem with machine deterioration effect.•Presentation of the multi-objective mixed-integer nonlinear programming model.•A new heuristic called Iterated Local Search Based on Decomposition (ILS/D).•The ILS/D outperforms MOEA/D and NSGA-II by a significant margin.•Decomposition is an effective way to extend ILS to multi-objective problems.