Scheduling a No-Wait Flow Shop with Unbounded Batching Machines

Article dans revue scientifique avec comité de lecture. internationale.International audienceWe 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