Consistency enforcing in scheduling: A general formulation based on energetic reasoningReport as inadecuate

Consistency enforcing in scheduling: A general formulation based on energetic reasoning - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 LAAS - Laboratoire d-analyse et d-architecture des systèmes Toulouse

Abstract : Since the last decade, hard combinatorial problems such as scheduling have been the target of many approaches combining Operations Research and Artificial Intelligence techniques, focussed on constraint satisfaction as a general paradigm for the representation of the efficient solving of such problems. Amongst these approaches, the so-called Constraint-Based-Analysis CBA Erschler 76, Esquirol 87, Lopez 91 has focussed on the characterization of feasible solutions, aiming at proposing a decision-aid based alternative to optimization approaches. CBA can be viewed as a panel of consistency enforcing techniques for scheduling problems defined as a special instance of Constraint Satisfaction Problems CSP. CBA proposes several inference techniques that make resource and time constraints interacting. In order to prevent the combinatorial solving of conflicts between tasks in competition for resources with limited capacities , the last researches on energy-based reasoning have enabled to integrate both resource and time constraints in the same reasoning. The underlying mechanisms are akin to other techniques yet developed in the scheduling field, such as immediate selections Carlier & Pinson, 1989 or edge-finding Applegate & Cook, 1991. Here the concept of energy is addressed to more general scheduling problems than those taken into account in the aforementioned works e.g., resource-constrained scheduling problems; furthermore, the inference rules derived from this concept permit the enforcing of the problem consistency, not only by adjustments of limit times of the tasks, but also by revealing inconsistent dates within their time window. In this direction, a similar study has also been realized by Nuijten 1994 for the case of multiple capacitated job-shop scheduling, but with independent rules, specific to the structural properties of the problem at hand. The purpose of this communication is to propose energy-based inference rules in a more generic way, aiming at enforcing as much as possible the consistency of a general scheduling problem. The benefits concern both the feasibility characterization problem but also the solving strategies, since the search space is reduced by constraint propagation. An implementation of these techniques has been realized through a Constraint Logic Programming tool, and more specifically its CSP-based solver over finite domains. Computational results show the improvment obtained for lower bounds of the makespan in some classical benchmarks Fisher & Thompson, Lawrence,

keyword : Scheduling Energy

Author: Pierre Lopez - Patrick Esquirol -



Related documents