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: | Corominas A, Pastor R |
Keywords: | combinatorial optimization, programming: nonlinear, heuristics |
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.