Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T22:09:18.597Z Has data issue: false hasContentIssue false

Décomposition temporelle et caractérisation de solutions admissibles pour le problème d'ordonnancement à une machine

Published online by Cambridge University Press:  15 August 2002

M.-L. Levy
Affiliation:
LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse Cedex 4, France
P. Lopez
Affiliation:
LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse Cedex 4, France
B. Pradin
Affiliation:
INSA, Complexe Scientifique de Rangueil, 31077 Toulouse Cedex 4, France e-mail: [email protected]
Get access

Abstract

We propose a temporal decomposition approach for the one-machine schedulingproblem with ready times and due dates. A set of feasible schedules ischaracterized by means of constraint-based analysis rules. They permit thedetermination of the feasible locations of each task in a sequence, representedby rank intervals. A decomposition procedure based on comparisons of rankintervals is developed in order to group tasks to be sequenced in theneighbourhood of each other in a feasible solution. Computational results are reported so that the capability of our approach to prepare the problem for a solution computation, achieved either by a human operator or by an automatic solving procedure, can be evaluated.

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)