Designing greedy algorithms for the flow‐shop problem by means of Empirically Adjusted Greedy Heuristics (EAGH)

Designing greedy algorithms for the flow‐shop problem by means of Empirically Adjusted Greedy Heuristics (EAGH)

0.00 Avg rating0 Votes
Article ID: iaor20117871
Volume: 62
Issue: 9
Start Page Number: 1704
End Page Number: 1710
Publication Date: Sep 2011
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: combinatorial optimization, programming: nonlinear, heuristics
Abstract:

This paper introduces Empirically Adjusted Greedy Heuristics (EAGH), a procedure for designing greedy algorithms for a given combinatorial optimization problem and illustrates the way in which EAGH works with an application to minimize the makespan in the permutation flow‐shop problem. The basic idea behind EAGH is that a greedy heuristic can be seen as a member of an infinite set of heuristics, this set being defined by a function that depends on several parameters. Each set of values of the parameters corresponds to a specific greedy heuristic. Then, the best element of the set, for a training set of instances of the problem, is found by applying a non‐linear optimization algorithm to a function that measures the quality of the obtained solutions to the instances of the training set, and which depends on the parameters that characterize each specific algorithm. EAGH allows improving known heuristics or finding good new ones.

Reviews

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