This paper deals with 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. This problem is known to be NP-hard for any c > 0 and c < n - 1, where n is the number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively Each set of identical parts forms a batch. The number of parts in the batch is the size of the batch. Here we consider the case in which each batch is made up of at least c + 1 parts. We first prove that the problem is still NP-hard for any value of c > 0. 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 generalizes the one defined for the two-machine no-wait flow shop, i.e., when c = 0. 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)*.
Agnetis, A., Pacciarelli, D., Rossi, F. (1997). Batch Scheduling in a Two Machine Flow Shop with limited buffer. DISCRETE APPLIED MATHEMATICS, 72(3), 243-260 [10.1016/0166-218X(95)00114-7].
Batch Scheduling in a Two Machine Flow Shop with limited buffer
AGNETIS, ALESSANDRO;
1997-01-01
Abstract
This paper deals with 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. This problem is known to be NP-hard for any c > 0 and c < n - 1, where n is the number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively Each set of identical parts forms a batch. The number of parts in the batch is the size of the batch. Here we consider the case in which each batch is made up of at least c + 1 parts. We first prove that the problem is still NP-hard for any value of c > 0. 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 generalizes the one defined for the two-machine no-wait flow shop, i.e., when c = 0. 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)*.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/17629
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo