Multiple-Machine Lower Bounds for Shop Scheduling Problems

F. Sourd, W. Nuijten

LIP6 2000/015: Rapport de Recherche LIP6 / LIP6 research reports
19 pages - Mai/May 2000 - Document en anglais.

Get it : 122 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Nouvelles bornes inférieures pour les problèmes d'ateliers
Titre anglais : Multiple-Machine Lower Bounds for Shop Scheduling Problems

Résumé : En ordonnancement, la plupart des techniques de calcul de bornes inférieures pour les problèmes d'ateliers sont basées sur des techniques d'ajustement issues de la relaxation au problème à une machine. Nous présentons une nouvelle technique fondée sur ce principe mais, partant de l'observation que les machines sont reliées entre elles par des contraintes de précédence, nous avons également étudié des techniques basées sur la combinaison de ces contraintes de précédence et des contraintes disjonctives. Une étude expérimentale montre l'efficacité de ces nouvelles techniques sur des problèmes de job-shop et de flow-shop.

Abstract : In order to compute lower bounds for shop scheduling problems, a lot of attention has been paid to adjustment techniques based on one-machine relaxations. We present such a new technique but, following the observation that machines are connected to each other through precedence constraints, we also study techniques that are based on the combination of precedence constraints and disjunctive constraints between operations that are processed on different machines. A computational study of the effectiveness of these new techniques is performed on job shop and flow shop instances.

Published in INFORMS Journal of Computing 12 (vol. 4) 2000.

Mots-clés : Problèmes d'atelier, bornes inférieures, séparation et évaluation

Key-words : Shop scheduling problems, lower bounds, branch and bound

Publications internes LIP6 2000 / LIP6 research reports 2000

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr