Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-28T05:00:56.841Z Has data issue: false hasContentIssue false
  • English
  • Français

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 ,
P. Lopez  and
B. Pradin
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.

Keywords

Scheduling; temporal decompositonfeasibility.
Type
Research Article
Information
RAIRO - Operations Research , Volume 33 , Issue 2 , April 1999 , pp. 185 - 208
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.)