Search results for "Heuristics"

Resource-constrained project scheduling: A critical activity reordering heuristic

2003

Abstract In this paper, we present a new metaheuristic algorithm for the resource-constrained project-scheduling problem. The procedure is a non-standard implementation of fundamental concepts of tabu search without explicitly using memory structures embedded in a population-based framework. The procedure makes use of a fan search strategy to intensify the search, whereas a strategic oscillation mechanism loosely related to the forward/backward technique provides the necessary diversification. Our implementation employs the topological order (TO) representation of schedules. To explore the TO vector space we introduce three types of moves, two of them based on the concept of relative critic…

Solving dynamic memory allocation problems in embedded systems with parallel variable neighborhood search strategies

2015

International audience; Embedded systems have become an essential part of our lives, thanks to their evolution in the recent years, but the main drawback is their power consumption. This paper is focused on improving the memory allocation of embedded systems to reduce their power consumption. We propose a parallel variable neighborhood search algorithm for the dynamic memory allocation problem, and compare it with the state of the art. Computational results and statistical tests applied show that the proposed algorithm produces significantly better outcomes than the previous algorithm in shorter computing time.

Randomized heuristics for the Capacitated Clustering Problem

2017

In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent l…

Performance of Understanding: Pragmatics and Fast and Frugal Heuristics

2019

What determines the meaning of an utterance is a logical matter and as such must be treated independently of the bio-cognitive constraints that operate in our bodies. This thesis, whose great supporter was Frege, implies a clear notion of rationality that seems not to bear comparison with what we know on the limits of our rationality. Various theories (Kahneman and Tversky 1983; Gigerenzer et al., 1999), thematizing the need to consider our rationality beginning from the bio- cognitive constraints that our body imposes on a mass of information, can be of great utility for facing the problem of what type of rationality operates in phenomena of linguistic understanding (Ferreira and Patson 20…

An Efficient Distributed Algorithm for Generating Multicast Distribution Trees

2005

Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in Networks) is prohibitively expensive. For this reason, heuristic methods are generally employed. Conventional centralized Steiner heuristics provide effective solutions, but they are unpractical for large networks, since they require complete knowledge of the network topology. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem. The algorithm allows the construction of effective distribution trees using a coordination protocol among the network nodes. The algorithm has been i…

2018

A comprehensive monitoring of fitness, fatigue, and performance is crucial for understanding an athlete's individual responses to training to optimize the scheduling of training and recovery strategies. Resting and exercise-related heart rate measures have received growing interest in recent decades and are considered potentially useful within multivariate response monitoring, as they provide non-invasive and time-efficient insights into the status of the autonomic nervous system (ANS) and aerobic fitness. In team sports, the practical implementation of athlete monitoring systems poses a particular challenge due to the complex and multidimensional structure of game demands and player and te…

Heuristic Algorithm for the Analysis of Fast Field Cycling (FFC) NMR Dispersion Curves

2021

Evaluation of nuclear magnetic relaxation dispersion (NMRD) curves obtained by the fast field cycling nuclear magnetic resonance (FFC-NMR) relaxometry technique is a valuable tool for analyzing the microscopic dynamics of condensed matter systems. However, quantitative data analysis involves several conceptual and practical issues. Moving forward from previous literature approaches, we propose a new analysis method, relying on the elaboration of the inverse integral transform of the NMRD curve. Our approach results in a true heuristic method, able to unambiguously individuate the dynamic domains in the system, thereby avoiding the possible introduction of any element of discretion. The anal…

Heuristics for solving the parameter tuning problem in motion cueing algorithms.

2017

[ES] Diversos tipos de plataformas robóticas son empleadas habitualmente para la generación de claves gravito-inerciales en simuladores. Además del control de los actuadores, dichas plataformas deben ejecutar complejos algoritmos de control conocidos como algoritmos de washout, que deben ser ajustados para que el movimiento generado sea similar al simulado. El ajuste de dichos algoritmos es complejo por el elevado número de parámetros que poseen. Además, dicho ajuste se ha venido realizando tradicionalmente de modo manual mediante evaluaciones subjetivas. En este trabajo, los autores proponen un método automático de ajuste basado en optimización heurística, métricas objetivas, y simulación …

Greedy and K-Greedy algoritmhs for multidimensional data association

2011

[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimen…

Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics

2015

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem. The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies. The result…