DECOM - Departamento de Computação
URI Permanente desta comunidade
Navegar
Navegando DECOM - Departamento de Computação por Assunto "Adaptive large neighborhood search"
Agora exibindo 1 - 2 de 2
Resultados por página
Opções de Ordenação
Item An adaptive multi-objective algorithm based on decomposition and large neighborhood search for a green machine scheduling problem.(2019) Cota, Luciano Perdigão; Guimarães, Frederico Gadelha; Ribeiro, Roberto Gomes; Meneghini, Ivan Reinaldo; Oliveira, Fernando Bernardes de; Souza, Marcone Jamilson Freitas; Siarry, PatrickGreen machine scheduling consists in the allocation of jobs in order to maximize production, in view of the sustainable use of energy. This work addresses the unrelated parallel machine scheduling problem with setup times, with the minimization of the makespan and the total energy consumption. The latter takes into account the power consumption of each machine in different operation modes. We propose multi-objective extensions of the Adaptive Large Neighborhood Search (ALNS) metaheuristic with Learning Automata (LA) to improve the search process and to solve the large scale instances efficiently. ALNS combines ad-hoc destroy and repair (also named removal and insertion) operators and a local search procedure. The LA is used to adapt the selection of insertion and removal operators within the framework of ALNS. Two new algorithms are developed: the MO-ALNS and the MO-ALNS/D. The first algorithm is a direct extension of single objective ALNS by using multi-objective local search. As this method does not offer much control of the diversification of the Pareto front approximation, a second strategy employs the decomposition approach similar to MOEA/D algorithm. The results show that the MO-ALNS/D algorithm has better performance than MO-ALNS and MOEA/D in all indicators. These findings show that the decomposition strategy is beneficial not only for evolutionary algorithms, but it is indeed an efficient way to extend ALNS to multi-objective problems.Item Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem.(2021) Santos, Vinícius Gandra Martins; Carvalho, Marco Antonio Moreira deThe cutwidth minimization problem (CMP) consists in determining a linear layout (i.e., a one-dimensional arrangement), of the vertices of a graph that minimizes the maximum number of edges crossing any consecutive pair of vertices. This problem has applications, for instance, in design of very large-scale integration circuits, graph drawing, and compiler design. The CMP is an N P-Hard problem and presents a challenge to exact methods and heuristics. In this study, the metaheuristic adaptive large neighborhood search is applied to the CMP. The computational experiments include 11,786 benchmark instances from four sets in the literature, and the obtained results are compared with state-of-the-art methods. The proposed method was demonstrated to be competitive, as it matched most optimal and best known results, improved some of the (not proved optimal) best known solutions, and provided the first upper bounds for unsolved instances.