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

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

0.00 Avg rating0 Votes
Article ID: iaor20051311
Country: Netherlands
Volume: 153
Issue: 3
Start Page Number: 581
End Page Number: 592
Publication Date: Mar 2004
Journal: European Journal of Operational Research
Authors:
Keywords: programming: travelling salesman
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 cn, 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 bi*, 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 bi*. Then, we prove that when the same algorithm is applied to batch sizes smaller than bi*, the error goes to zero as the batch sizes approach the values bi*.

Reviews

Required fields are marked *. Your email address will not be published.