Intensification, diversification, and learning via relaxation adaptive memory programming: a case study on resource constrained project scheduling

R. Christopher L. Riley () and Cesar Rego ()
Additional contact information
R. Christopher L. Riley: Delta State University
Cesar Rego: University of Mississippi

Journal of Heuristics, 2019, vol. 25, issue 4, No 12, 793-807

Abstract: Abstract Learning, clearly, can only occur in the presence of memory. Moreover, intensification and diversification strategies are widely recognized for their importance in the metaheuristics literature as the building blocks for adaptive memory programming (AMP). It is safe to say that any metaheuristic approach that isn’t blindly mechanistic uses some sort of adaptive memory to guide the search beyond local optimality, during which intensification and diversification always take place explicitly or implicitly. From this perspective, adaptive memory lies in the heart of what may be generally called the intensification, diversification, and learning (IDL) triangle. This paper focuses on the importance of solution landscape information in the design of AMP structures based on the IDL triangle. More specifically, we argue that a metaheuristic algorithm can only perform as good as the quality of information it is provided about the search space. To illustrate, we consider the computationally intractable Resource Constrained Project Scheduling Problem as a benchmark and take the approach of adding Lagrangian dual information to a rudimentary tabu search approach and integrate the two approaches via the Relaxation Adaptive Memory Programming (RAMP) framework. We show that while our simple tabu search component alone is not competitive with the best performing tabu search algorithms of the literature, when dual information is added to the procedure the resulting integrated RAMP algorithm outperforms all of them, thus supporting our premise.

Keywords: Project scheduling; Mathematical relaxation; Heuristics; Primal–dual search; Adaptive memory; Intensification; Diversification; Learning (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9368-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9368-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9368-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().