期刊
EVOLUTIONARY COMPUTATION
卷 24, 期 4, 页码 609-635出版社
MIT PRESS
DOI: 10.1162/EVCO_a_00183
关键词
Job-shop-scheduling; dispatching rule; heuristic ensemble; hyper-heuristic; genetic programming
资金
- Leverhulme Fellowship [RF-2015-092]
- EPSRC [EP/J021628/1]
- EPSRC [EP/J021628/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/J021628/1] Funding Source: researchfish
We describe a new hyper-heuristic method NELLI-GP for solving job-shop scheduling problems (JSSP) that evolves an ensemble of heuristics. The ensemble adopts a divide-and-conquer approach in which each heuristic solves a unique subset of the instance set considered. NELLI-GP extends an existing ensemble method called NELLI by introducing a novel heuristic generator that evolves heuristics composed of linear sequences of dispatching rules: each rule is represented using a tree structure and is itself evolved. Following a training period, the ensemble is shown to outperform both existing dispatching rules and a standard genetic programming algorithm on a large set of new test instances. In addition, it obtains superior results on a set of 210 benchmark problems from the literature when compared to two state-of-the-art hyper-heuristic approaches. Further analysis of the relationship between heuristics in the evolved ensemble and the instances each solves provides new insights into features that might describe similar instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据