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.

Additional information

Notes on contributors

Alessandro Agnetis

Alessandro Agnetis is Assistant Professor of Industrial Automation in the Department of Computer and System Science at the University ‘La Sapienza’ of Rome, Italy. He graduated in Electronic Engineering in 1987 and received a Ph.D. in Systems Engineering in 1992 from the same University. He also teaches Methods of Operations Research in the MBA program at the LUISS University in Rome. His research interests include combinatorial optimization problems in manufacturing. He has published papers in Management Science, IEEE Transactions on Robotics and Automation, International Journal of Flexible Manufacturing Systems, International Journal of Production Research and others.

Dario Pacciarelli

Dario Pacciarelli is Assistant Professor of Industrial Automation in the department of Computer Science at the Third University of Rome. He graduated in Electronic Engineering at the University of Rome ‘La Sapienza’ in 1991 and he completed his Ph.D. in Operations Research in 1996. His research interests include combinatorial optimization and its applications to manufacturing.

Fabrizio Rossi

Fabrizio Rossi is Ph.D. student of Operations Research at the University of Rome ‘La Sapienza’. He graduated in Electronic Engineering at the University ‘La Sapienza’ of Rome in 1992. His research activity is focused on integer linear programming and production planning and scheduling problems.