Hostname: page-component-7479d7b7d-767nl Total loading time: 0 Render date: 2024-07-08T16:50:03.230Z 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 scheduling problem with ready times and due dates. A set of feasible schedules is characterized by means of constraint-based analysis rules. They permit the determination of the feasible locations of each task in a sequence, represented by rank intervals. A decomposition procedure based on comparisons of rank intervals is developed in order to group tasks to be sequenced in the neighbourhood 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.)