Heuristics for permutation flow shop scheduling with batch setup times

In this paper we 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 t(ij) of job i on machine j and setup times s(rj) 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. We 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 we give various constructive and iterative algorithms. The constructive algorithms are based on insertion techniques combined with beam search. We 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.