In this paper the authors consider permutation flow shop scheduling problems with batch setup times. Each job has to be processed on each machine once and the technological routes are identical for all jobs. The set of jobs is divided into groups. There are given processing times tij of job i on machine j and setup times srj on machine j when a job of the r-th group is processed after a job of another group. It is assumed that the same job order has to be chosen on each machine. The authors consider both the problems of minimizing the makespan and of minimizing the sum of completion times, where batch or item availability of the jobs is assumed. For these problems they give various constructive and iterative algorithms. The constructive algorithms are based on insertion techniques combined with beam search. The authors introduce suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on local search and reinsertion techniques. The developed algorithms have been tested on a large collection of problems with up to 80 jobs.
