Artigos

URI permanente para esta coleçãohttps://locus.ufv.br/handle/123456789/11798

Navegar

Agora exibindo 1 - 2 de 2

A GRASP heuristic for the multi-objective permutation flowshop scheduling problem
(The International Journal of Advanced Manufacturing Technology, 2011-07) Arroyo, José Elias Claudio; Pereira, Ana Amélia de Souza
This paper presents a multi-objective greedy randomized adaptive search procedure (GRASP)-based heuristic for solving the permutation flowshop scheduling problem in order to minimize two and three objectives simultaneously: (1) makespan and maximum tardiness; (2) makespan, maximum tardiness, and total flowtime. GRASP is a competitive metaheuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a multi-objective problem and a new algorithm named multi-objective GRASP algorithm is proposed. In order to find a variety of non-dominated solutions, the heuristic blends two typical approaches used in multi-objective optimization: scalarizing functions and Pareto dominance. For instances involving two machines, the heuristic is compared with a bi-objective branch-and-bound algorithm proposed in the literature. For instances involving up to 80 jobs and 20 machines, the non-dominated solutions obtained by the heuristic are compared with solutions obtained by multi-objective genetic algorithms from the literature. Computational results indicate that GRASP is a promising approach for multi-objective optimization.
Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows
(Electronic Notes in Theoretical Computer Science, 2011-12-29) Arroyo, José Elias Claudio; Ottoni, Rafael dos Santos; Oliveira, Alcione de Paiva
In this paper, we compare three multi-objective algorithms based on Variable Neighborhood Search (VNS) heuristic. The algorithms are applied to solve the single machine scheduling problem with sequence dependent setup times and distinct due windows. In this problem, we consider minimizing the total weighted earliness/tardiness and the total flowtime criteria. We introduce two intensification procedures to improve a multi-objective VNS (MOVNS) algorithm proposed in the literature. The performance of the algorithms is tested on a set of medium and larger instances of the problem. The computational results show that the proposed algorithms outperform the original MOVNS algorithm in terms of solution quality. A statistical analysis is conducted in order to analyze the performance of the proposed methods.