Lot Scheduling in a Two-Machine Cell with Swapping Devices

Abstract

This paper deals with the problem of part input sequencing in an automated flow shop system. The system consists of one input/output station, two machines and one AGV, which is used for all part transfer operations throughout the cell. The objective is the minimization of the makespan. This cell architecture has recently received considerable attention in the literature. Here we consider the case in which the two machines are equipped by a swapping device, allowing the AGV to exchange a new part for the one released by the machine. A similar device exists for the input/output station. If the transportation times are small enough, the problem can be formulated as a two-machine flow shop with limited intermediate buffer, which is NP-hard. Here we analyze the problem in the context of lot processing, i.e., when identical parts must be processed consecutively. Each set of identical parts forms a lot. The number of parts in the lot is the size of the lot. If the size of the ith lot is larger than a value b*_i, the problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP generalizes that defined for the two-machine no-wait flow shop. Finally, we give a closed form expression for b*_i.