Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Adrien Bellanger Connect in order to contact the contributor
Submitted on : Monday, April 4, 2011 - 11:58:06 AM
Last modification on : Tuesday, August 30, 2022 - 5:04:23 PM
Long-term archiving on: : Tuesday, July 5, 2011 - 2:58:43 AM


Files produced by the author(s)




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



Record views


Files downloads