The problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c>0 and c⩽n, where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the ith batch is larger than a value b*_i, then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b*_i. Then, we prove that when the same algorithm is applied to batch sizes smaller than b*_i, the error goes to zero as the batch sizes approach the values b*_i.

Pranzo, M. (2004). Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 153(3), 581-592 [10.1016/S0377-2217(03)00264-9].

Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times

PRANZO, MARCO
2004

Abstract

The problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c>0 and c⩽n, where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the ith batch is larger than a value b*_i, then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b*_i. Then, we prove that when the same algorithm is applied to batch sizes smaller than b*_i, the error goes to zero as the batch sizes approach the values b*_i.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/22019
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo