Permutation Flowshop Scheduling Problems with Maximal and Minimal Time Lags

Julien Fondrevelle 1 Ammar Oulamara 1 Marie-Claude Portmann 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time-lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2004, 26 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00100091
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:04
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00100091, version 1

Collections

Citation

Julien Fondrevelle, Ammar Oulamara, Marie-Claude Portmann. Permutation Flowshop Scheduling Problems with Maximal and Minimal Time Lags. Computers and Operations Research, Elsevier, 2004, 26 p. 〈inria-00100091〉

Partager

Métriques

Consultations de la notice

263