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.
Type de document :
Article dans une revue
IIE Transactions on Scheduling and Logistics, 2004, 31 p
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:04
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00100090, version 1



Ammar Oulamara, Mikhail Y. Kovalyov, Gerd Finke. Scheduling a No-Wait Flow Shop with Unbounded Batching Machines. IIE Transactions on Scheduling and Logistics, 2004, 31 p. 〈inria-00100090〉



Consultations de la notice