Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/inria-00582858
Contributor : Adrien Bellanger <>
Submitted on : Monday, April 4, 2011 - 11:58:06 AM
Last modification on : Tuesday, December 18, 2018 - 4:42:06 PM
Long-term archiving on: : Tuesday, July 5, 2011 - 2:58:43 AM

File

COR.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

310

Files downloads

346