Structural properties of lot streaming in a flow shop

Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in multi-stage production systems, thereby reducing the makespan of the corresponding schedule. This paper considers the problem of finding sublet sizes to minimize the makespan for a single job in an in-machine flow shop. On each machine, the job is to be partitioned 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 algorithm to reduce the problem so that only dominant machines are considered explicitly. After defining a network representation in which it is required to find the shortest critical path length, we identify the structure of critical paths fur optimal sublot sizes. Knowledge of this structure considerably reduces the search for an optimal solution, which we illustrate by presenting algorithms for finding optimal sublet sizes.