Displaying similar documents to “Consistency checking within local search applied to the frequency assignment with polarization problem”

About the choice of the variable to unassign in a decision repair algorithm

Cédric Pralet, Gérard Verfaillie (2010)

RAIRO - Operations Research

Similarity:

The algorithm (Jussien and Lhomme, (2002) 21–45), which has been designed to solve (CSP), can be seen, either (i) as an extension of the classical algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between and . Experiments reported in Pralet and Verfailllie (2004) show that some heuristics...

New algorithms for coupled tasks scheduling – a survey

Jacek Blazewicz, Grzegorz Pawlak, Michal Tanas, Wojciech Wojciechowicz (2012)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various...

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira do Lago, Ilya Muchnik, Casimir Kulikowski (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions...

Three tabu search methods for the MI-FAP applied to 802.11 networks

Sacha Varone, Nicolas Zufferey (2009)

RAIRO - Operations Research

Similarity:

Wireless LAN using IEEE 802.11 networks are now widely deployed at home by residential users or in hot spots by telecommunication operators. A hot spot is a place where a set of access points (APs) are located nearby each other and can serve many users. Since perturbations can degrade the quality of the signal, a careful channel assignment to each AP has to be done. Channel assignment of APs at hot spots, and more generally setup configuration and management, is still often done manually....

Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine

Philippe Chrétienne (2010)

RAIRO - Operations Research

Similarity:

Assume that tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey have proposed a nice log) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to...

Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List

Saïd Hanafi, Arnaud Fréville (2010)

RAIRO - Operations Research

Similarity:

The Reverse Elimination Method (REM) is a dynamic strategy for managing the tabu list. It is based on logical interdependencies between the solutions encountered during recent iterations of the search. REM provides both a necessary and sufficient condition to prevent cycling. The purpose of this paper is first to incorporate in REM a when cycling is unavoidable, thereby assuring the finite convergence of Tabu Search. Secondly, we correct a generalization of REM, the so-called REM-...

An Improved Algorithm for a Bicriteria Batching Scheduling Problem

Cheng He, Xiumei Wang, Yixun Lin, Yundong Mu (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

This note is concerned with the bicriteria scheduling problem on a series-batching machine to minimize maximum cost and makespan. An ( ) algorithm has been established previously. Here is an improved algorithm which solves the problem in ( ) time.

On Minimizing Total Tardiness in a Serial Batching Problem

Philippe Baptiste, Antoine Jouglet (2010)

RAIRO - Operations Research

Similarity:

We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time occurs. This problem | ∑ is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.

Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2010)

RAIRO - Operations Research

Similarity:

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum , and where the integer variables are subject to difference constraints of the form . An important application area where such problems occur is deterministic scheduling with the as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical...

Solving multi-agent scheduling problems on parallel machines with a global objective function

F. Sadi, A. Soukhal, J.-C. Billaut (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this study, we consider a scheduling environment with ( ≥ 1) parallel machines. The set of jobs to schedule is divided into disjoint subsets. Each subset of jobs is associated with one agent. The agents compete to perform their jobs on common resources. The objective is to find a schedule that minimizes a global objective function , while maintaining the regular objective function of each agent, , at a level no greater than a fixed value, ...