Structural properties of lot streaming in a flow shop

Lot streaming is the process of splitting a given lot or job to allow the o verlapping of successive operations in multi-stage production systems, ther eby reducing the makespan of the corresponding schedule. This paper conside rs the problem of finding sublet sizes to minimize the makespan for a singl e job in an in-machine flow shop. On each machine, the job is to be partiti oned into a given number of sublets, and sublet sizes are the same on each machine. We introduce the concept of machine dominance, and propose an algo rithm to reduce the problem so that only dominant machines are considered e xplicitly. After defining a network representation in which it is required to find the shortest critical path length, we identify the structure of cri tical paths fur optimal sublot sizes. Knowledge of this structure considera bly reduces the search for an optimal solution, which we illustrate by pres enting algorithms for finding optimal sublet sizes.