Lot streaming in three-stage production processes

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 develops algorithms to minimize the makespan for a single job in three-stage production processes. At each stage, the job is split into s sublots. For both the flow shop and job shop problems, an algorithm is proposed which computes the minimum makespan in O(log s) time. However, for the open shop, it is shown that to evaluate the minimum makespan requires constant time. Various results are derived which are applicable when the number of stages of production exceeds three.