Retour au site du LAAS-CNRS

Abstract

To solve problems with Local Search procedures, neighborhoods have to be defined. During the resolution, a solution is typically replaced by the best solution found in its neighborhood. A question concerns the size of the neighborhood. If a small neighborhood can be explored in polynomial time, a large neighborhood search may bring a faster convergence to a local optimum of good quality. In this paper, we propose a class of large neighborhood search which can be implemented on some extensions of the Traveling Salesman Problem.

Mots-Clés / Keywords

Abstract

In this paper, we present a solution approach based on Chv\'{a}tal's Resolution Search [Chvatal 1997] to solve combinatorial optimization problems. Resolution Search constitutes an alternative to classical enumeration methods and possesses strong connections to nogood recording approaches, and in particular dynamic backtracking, though it is designed to deal with binary linear programming problems. Accordingly, we suggest to hybridize the procedure using constraint programming techniques, in order to apply it to Constraint Satisfaction Problems (CSP). Furthermore, the introduction of such techniques allows some specific improvements that speed up the process and let many outcomes for further research. In order to evaluate the interest of the proposed method, we use it to tackle some particular graph coloring instances, known as the Queens_n2 problem. The experimental results obtained so far prove the validity of the approach and compete with state-of-the-art complete solution methods.

Mots-Clés / Keywords

Abstract

The purpose of this work is to provide the decision-maker a characterization of possible modifications of predictive schedules while preserving optimality. In the context of machine scheduling, the anticipated modifications are changes in the predictive order of operations on the machines. To achieve this goal, a flexible solution is provided. It represents a set of semi-active schedules and is characterized by a partial order on each machine, so that the total order can be set on-line, as required Flexible solutions in disjunctive scheduling [...] by the decision maker. A flexible solution is optimal if all the complete schedules that can be obtained by extension are also optimal. We consider the problem of evaluating the worst case performance of flexible solutions in disjunctive scheduling. We show that this problem can be modeled as an elementary longest path problem in the disjunctive graph representing the scheduling problem with additional constraints. In the flow-shop context, we give a polynomial algorithm to solve the problem and propose a method to issue optimal flexible solutions. Computational experiments show that significant flexibility is obtained.

Abstract

We propose a flexible model and several integer linear programming and constraint programming formulations for integrated employee timetabling and production scheduling problems. A hybrid constraint and linear programming exact method is designed to solve a basic integrated employee timetabling and job-shop scheduling problem for lexicographic minimization of makespan and labor costs. Preliminary computational experiments show the potential of hybrid methods.

Abstract

We consider the job-shop problem with sequence-dependent setup times. We focus on the formal definition of schedule generation schemes (SGSs) based on the semi-active, active, and non-delay schedule categories. We study dominance properties of the sets of schedules obtainable with each SGS. We show how the proposed SGSs can be used within single-pass and multi-pass priority rule based heuristics. We study several priority rules for the problem and provide a comparative computational analysis of the different SGSs on sets of instances taken from the literature. The proposed SGSs significantly improve previously best-known results on a set of hard benchmark instances.