Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

0.00 Avg rating0 Votes
Article ID: iaor20071764
Country: Netherlands
Volume: 12
Issue: 6
Start Page Number: 427
End Page Number: 446
Publication Date: Dec 2006
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.