Skip to Main content Skip to Navigation
Journal articles

Scheduling a No-Wait Flow Shop with Unbounded Batching Machines

Ammar Oulamara 1 Mikhail Y. Kovalyov Gerd Finke 2
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study a problem of scheduling $n$ jobs in a no-wait flow shop consisting of $m$ batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should immediately be transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For $m=2,$ we prove that there exists an optimal schedule with at most two batches and construct such a schedule in $O(n\log n)$ time. For $m=3,$ we prove that the number of batches can be limited by 9 and give an example where all optimal schedules have 7 batches. Furthermore, we prove that the best schedules with at most one, two and three batches are $3$-, $2$- and $3/2$-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with $m$ machines and at most $r$ batches in $O(n^{m(r-2)+1+\lfloor m/r\rfloor})$ time, if $m$ and $r$ are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00100090
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:14:04 AM
Last modification on : Friday, April 10, 2020 - 4:20:05 PM

Identifiers

  • HAL Id : inria-00100090, version 1

Collections

Citation

Ammar Oulamara, Mikhail Y. Kovalyov, Gerd Finke. Scheduling a No-Wait Flow Shop with Unbounded Batching Machines. IIE Transactions, Taylor & Francis, 2004, 31 p. ⟨inria-00100090⟩

Share

Metrics

Record views

261