Two- and three-machine flow shop scheduling problems with equal sized transfer batches

Transfer batches permit the processing of part of a job-lot on downstream machines before completion of the lot on the current machine. This paper studies the effects of transfer batches in two- and three-machine flow shops. It establishes conditions under which each unit of a job can optimally be viewed as a separate transfer batch. Issues of interrupted versus continuous production on downstream machines, and job-splitting (lot-sizing) are discussed. Examples are provided which show that even with a regular measure of performance and no setup times, job-splitting can yield a better solution than is possible without splitting jobs. A modification of Johnson's Algorithm for makespan minimization is derived under suitable conditions in two-machine flow shops and in special three-machine flow shops. An empirical study of transfer batch effects in two-machine flow shops is undertaken for both the makespan and the total flow time criteria under the assumption that jobs are not split. The no-split jobs restriction allows a meaningful comparison to be made between schedules with and without transfer batches.