Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/68441
Type: Artigo de periódico
Title: Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times
Author: Armentano, VA
de Araujo, OCB
Abstract: This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.
Subject: single machine scheduling
setup times
tardiness
memory mechanisms
greedy randomized adaptive search procedures
Country: Holanda
Editor: Springer
Rights: fechado
Identifier DOI: 10.1007/s10732-006-6662-x
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.