On discrete lot streaming in no-wait flow shops

Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a substantially shorter makespan for the corresponding schedule. In this paper, we study the discrete lot streaming problem for a single job in no-wait flow shops. We present a new linear programming formulation for the problem. We show that the optimal solutions are the same for the m 2 2 case with or without no-wait constraints. We also present a fast, polynomial-time solution method for this case. For the general case, we prove that any solution which is 'close' to the continuous optimal solution will be a good approximation for the discrete problem. This property allows us to present two quickly obtainable approximations of very good quality.