Two-machine lot streaming with attached setup times

Lot streaming is a fundamental production scheduling technique to squeeze manufacturing lead times by splitting a large lot of n identical items into sublots. This article presents a full characterization of optimal solutions for two-stage lot streaming with attached machine setup times to minimize the makespan. An O(n 3) time dynamic programming algorithm is presented for the discrete variant of the problem, in which all sublot sizes need to be integral. Since this running time can be prohibitively long for larger n, the continuous variant is also analyzed and an O(n) time algorithm for its solution is presented. Also, rounding procedures for the optimal continuous solution to obtain an approximate solution for the discrete problem are designed and analyzed. It is shown that a particular class of rounding procedures, using dynamic programming, has a compelling absolute worst-case and empirical performance.