A new constructive heuristic for the No-Wait Flowshop Scheduling Problem

A new constructive heuristic for the No-Wait Flowshop Scheduling Problem

Constructive heuristics have a great interest as they manage to find in a very short time, solutions of relatively good quality. Such solutions may be used as initial solutions for metaheuristics for example. In this work, we propose a new efficient constructive heuristic for the No-Wait Flowshop Scheduling Problem. This proposed heuristic is based on observations on the structure of best solutions of small instances as well as on analyzes of efficient constructive heuristics principles of the literature. Experiments have been conducted and results show the efficiency of the proposed heuristic compared to ones from the literature.

An Iterated Greedy-based Approach Exploiting Promising Sub-Sequences of Jobs to solve the No-Wait Flowshop Scheduling Problem

An Iterated Greedy-based Approach Exploiting Promising Sub-Sequences of Jobs to solve the No-Wait Flowshop Scheduling Problem

The no-wait flowshop scheduling problem is a variant of the classical permutation flowshop problem , with the additional constraint that jobs have to be processed by the successive machines without waiting time. To efficiently address this NP hard combinatorial problem we conducted an analysis of the structure of good quality solutions. This study shows that the No-Wait specificity gives them a common structure: they share identical sub-sequences of jobs. After a discussion on the way to identify these sub-sequences, we propose to exploit them into the well-known Iterated Greedy algorithm. Experiments are conducted on Taillard's instances. The experimental results show the proposed approach is efficient and robust, and is able to find out new best solutions for all the largest instances.

De nouvelles meilleures solutions pour le problème d’ordonnancement No-Wait Flowshop

De nouvelles meilleures solutions pour le problème d’ordonnancement No-Wait Flowshop

Le problème No-Wait Flowshop (NWFSP) est une variante du problème d’ordonnancement de type flowshop de permutation où aucun temps d’attente n’est autorisé entre l’exécution de chaque tâche sur les machines successives. Ainsi l’exécution d’une tâche est exactement le temps nécessaire pour effectuer chaque tâche par chaque machine contrairement au problème classique. Cette particularité lui confère des propriétés et une structure intéressantes qui peuvent être utilisées dans des algorithmes de résolution tels que les heuristiques ou les métaheuristiques. Partant de cette observation, nous proposons une méthode rapide pour construire des solutions initiales meilleure que celles construites par les heuristiques constructives de la littérature. Cette méthode d’initialisation sera ensuite utilisée comme point de départ à une nouvelle métaheuristique nous permettant d’obtenir de nouvelles meilleures solutions ayant des qualités non encore atteintes actuellement pour les instances de Taillard.

Feature selection using tabu search with learning memory : Learning tabu search

Feature selection using tabu search with learning memory : Learning tabu search

Feature selection in classification can be modeled as a com-binatorial optimization problem. One of the main particularities of this problem is the large amount of time that may be needed to evaluate the quality of a subset of features. In this paper, we propose to solve this problem with a tabu search algorithm integrating a learning mechanism. To do so, we adapt to the feature selection problem, a learning tabu search algorithm originally designed for a railway network problem in which the evaluation of a solution is time-consuming. Experiments are conducted and show the benefit of using a learning mechanism to solve hard instances of the literature.

Sélection d’attributs par Learning Tabu Search

Sélection d’attributs par Learning Tabu Search

Le nombre de données disponibles étant en constante augmentation, les algorithmes d'extraction de connaissances ont de plus en plus de mal à extraire les informations pertinentes. En effet, dans cette masse de données, beaucoup sont non-significatives ou redondantes, ce qui crée du bruit pour les algorithmes d'extraction de connaissances et rend ainsi les modèles incapables de faire de la prédiction sur de nouvelles données. Pour remédier à ce problème, nous utilisons la sélection d'attributs comme une phase préliminaire aux algorithmes d'apprentissage qui va réduire la taille des données afin de permettre de découvrir de meilleurs modèles. Le problème de sélection d'attributs consiste donc à choisir parmi un ensemble d'attributs de très grande taille, un sous-ensemble plus petit d'attributs qui sont significatifs pour le problème étudié. De nombreuses méthodes de résolution pour la sélection d'attributs ont été proposées. 

Ce problème étant un problème combinatoire, nous avons choisi de le modéliser comme un problème d'optimisation combinatoire. La qualité du sous-ensemble d'attributs choisi est mesurée en appliquant une méthode de classification sur ces données et en calculant le pourcentage de bonne classification des données. Ce procédé d'évaluation d'un sous-ensemble devient rapidement coûteux lorsque la taille de données est grande. De ce fait, si nous voulons avoir une chance d'avoir une bonne solution, nous devons utiliser une méta-heuristique efficace. C'est pourquoi nous avons choisi pour notre problème d'utiliser un Learning Tabu Search (LTS), une recherche taboue avec un mécanisme d'apprentissage pour guider la recherche.

A Comparison of Decoding Strategies for the 0/1 Multi-objective Unit Commitment Problem

In the single objective Unit Commitment Problem (UCP) the problem is usually separated in two sub-problems : the commitment problem which aims to fix the on/off scheduling of each unit and the dispatching problem which goal is to schedule the production of each turned on unit. The dispatching problem is a continuous convex prob-lem that can easily be solved exactly. For the first sub-problem genetic algorithms (GA) are often applied and usually handle binary vectors rep-resenting the solutions of the commitment problem.Then the solutions are decoded in solving the dispatching problem with an exact method to obtain the precise production of each unit. In this paper a multi-objective version of the UCP taking the emission of gas into account is presented. In this multi objective UCP the dispatching problem re-mains easy to solve whereas considering it separatly remains interesting. A multi-objective GA handling binary vectors is applied. However for a binary representation there is a set of solutions of the dispatching prob-lem that are pareto equivalent. Three decoding strategies are proposed and compared. The main contribution of this paper is the third decoding strategy which attaches an approximation of the Pareto front from the associated dispatching problem to each genotypic solution. It is shown that this decoding strategy leads to better results in comparison to the other ones.