Retour au site du LAAS-CNRS

Abstract

This paper presents an improved discrepancy-based method, called CDDS, after being adapted to solve the flexible job shop problem in a precedent work. We propose applying discrepancy on some pertinent variables chosen by using two types of heuristics. The method is tested on different problem instances from literature.

Mots-Clés / Keywords

Abstract

We present a large neighborhood search method based on limited discrepancy search to solve a parallel machine scheduling problem with precedence constraints and sequence-dependent setup times. New dominance rules and filtering techniques are proposed. Considering both maximum lateness and sum of completion times minimization, our method compares favorably to previously proposed tree search-based methods on standard problems.

Mots-Clés / Keywords

Résumé

Cet article concerne l'étude de différentes méthodes de résolution pour les problèmes d'ordonnancement d'opérations sur machines parallèles avec contraintes de précédence et temps de préparation des machines entre l'exécution des différentes opérations. Des méthodes de recherche arborescente à divergences limitées intégrant des concepts de recherche locale, des conditions de dominance et des bornes inférieures spécifiques sont proposées et validées sur des jeux de données générés aléatoirement.

Mots-Clés / Keywords

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a generalization of the classical Job Shop Problem in which each operation must be processed on a given machine chosen among a finite sub-set of candidate machines. The aim is to find an allocation for each operation and to define the se-quence of operations on each machine so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. Experiments have been performed on well-known benchmarks for flexible job shop scheduling.

Mots-Clés / Keywords

Abstract

This paper investigates how to adapt some discrepancy-based search methods to solve Hybrid Flow Shop (HFS) problems in which each stage consists of several identical machines operating in parallel. The objective is to determine a schedule that minimizes the makespan. We present here an adaptation of the Depth-bounded Discrepancy Search (DDS) method to obtain near-optimal solutions with makespan of high quality. This adaptation for the HFS contains no redundancy for the search tree expansion. To improve the solutions of our HFS problem, we propose a local search method, called Climbing Depth-bounded Discrepancy Search (CDDS), which is a hybridization of two existing discrepancy-based methods: DDS and Climbing Discrepancy Search. CDDS introduces an intensification process around promising solutions. These methods are tested on benchmark problems. Results show that discrepancy methods give promising results and CDDS method gives the best solutions.

Abstract

In this paper, we introduce a Yet ImprovEd Limited Discrepancy Search (YIELDS), a complete algorithm for solving Constraint Satisfaction Problems. As indicated in its name, YIELDS is an improved version of Limited Discrepancy Search (LDS). It integrates constraint propagation and variable order learning. The learning scheme, which is the main contribution of this paper, takes benefit from failures encountered during search in order to enhance the efficiency of variable ordering heuristic. As a result, we obtain a search which needs less discrepancies than LDS to find a solution or to state a problem is intractable. This method is then less redundant than LDS. The efficiency of YIELDS is experimentally validated, comparing it with several solving algorithms: Depth-bounded Discrepancy Search, Forward Checking, and Maintaining Arc-Consistency. Experiments carried out on randomly generated binary CSPs and real problems clearly indicate that YIELDS often outperforms the algorithms with which it is compared, especially for tractable problems.