Retour au site du LAAS-CNRS

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

Abstract

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.

Mots-Clés / Keywords

Abstract

The ROADEF challenge is organized every two years by the French Society of Operations Research and Decision-Making Aid. The goal is to allow industrial partners to witness recent developments in the field of Operations Research and Decision Analysis, and researchers to face up a decisional problem, often complex, occurred in industry. In 2005, the subject of this challenge has been proposed by the car manufacturer RENAULT and concerned a car sequencing problem. This problem involves scheduling cars along an assembly line with hard and soft capacity constraints. The industrial problem considered in the challenge differs from the standard problem since, besides capacity constraints imposed by the assembly shop, it also introduces paint batching constraints to minimize the consumption of solvents in the paint shop. We reviews the exact and heuristic methods of the literature proposed to solve the standard problem and we present the industrial context and the specificities of the challenge problem. We describe the process of the ROADEF'2005 challenge and the methods proposed by the competing teams. We also analyse the results of these methods on the car sequencing instances provided by RENAULT. The final ranking of the candidates is reported and directions for future research based on the results are drawn.

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

Mots-Clés / Keywords

Abstract

In this paper, we are interested in enumerative resolution methods for combinatorial optimization (COP) and constraint satisfaction problems (CSP). We introduce a new approch for the management of branching, called Dynamic Cooperative Search (DCS) inspired from the impact-based search method proposed in Refalo (2004) for CSPs. This method defines in a dynamic way priority rules for variable and value selection in the branching scheme. These rules are meant to be independent of the considered problem. As in Refalo (2004), the principle is to take into account, through learning methods, of the impact of branching decisions in already explored subparts of the search tree. We show the interest of DCS on a real-life rostering problem.

Mots-Clés / Keywords