Scheduling hybrid flowshop with parallel batching machines and compatibilities.

Adrien Bellanger 1 Ammar Oulamara 1
1 ORCHIDS - Operations research for Complex HybrId Decision Sytems
LORIA - NSS - Department of Networks, Systems and Services
Abstract : This paper considers a two-stage hybrid flowshop problem in which the first stage contains several identical discrete machines, and the second stage contains several identical batching machines. Each discrete machine can process no more than one task at time, and each batching machine can process several tasks simultaneously in a batch with the additional feature that the tasks of the same batch have to be compatible. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The batch processing time is equal to the maximal processing time of the tasks in this batch, and all tasks of the same batch start and finish together. The goal is to make batching and sequencing decisions in order to minimize the makespan. Since the problem is NP-hard, we develop several heuristics along with their worst cases analysis. We also consider the case in which tasks have the same processing time on the first stage, for which a polynomial time approximation scheme (PTAS) algorithm is presented.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2008, 36 (6), pp.1982-1992. 〈10.1016/j.cor.2008.06.011〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00582858
Contributeur : Adrien Bellanger <>
Soumis le : lundi 4 avril 2011 - 11:58:06
Dernière modification le : mardi 24 avril 2018 - 13:34:14
Document(s) archivé(s) le : mardi 5 juillet 2011 - 02:58:43

Fichier

COR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Adrien Bellanger, Ammar Oulamara. Scheduling hybrid flowshop with parallel batching machines and compatibilities.. Computers and Operations Research, Elsevier, 2008, 36 (6), pp.1982-1992. 〈10.1016/j.cor.2008.06.011〉. 〈inria-00582858〉

Partager

Métriques

Consultations de la notice

242

Téléchargements de fichiers

174