Two-machine lot streaming with attached setup times

A Alfieri, CA Glass, Steef van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)695-710
Number of pages16
JournalIISE Transactions
Issue number8
Publication statusPublished - 2012
Externally publishedYes

Research programs



Dive into the research topics of 'Two-machine lot streaming with attached setup times'. Together they form a unique fingerprint.

Cite this