Lot streaming in three-stage production processes (Q1331614)

Lot streaming models for multi-stage production systems with the makespan (maximum completion time) as an objective are considered. A single job is to be partitioned into \(s\) sublots. A machine, which processes the job on the concrete stage, can process a sublot only when it has finished processing any previous sublot and when all sublots at any previous stage which contain items of the current sublot have been processed. Let \(p_ i\) denote the positive processing time of the job on stage \(i\) and let \(x_{ij}\) denote the proportion of processing on stage \(i\) of sublot \(j\). Thus, the processing time of sublot \(j\) is \(p_ i x_{ij}\). Throughout the paper the case when \(x_{ij}= x_{i+ 1,j}= x_ j\) for all \(1\leq i\leq m- 1\) and \(1\leq j\leq s\) is considered. Here \(x_{ij}\) and \(x_{i+ 1,j}\) is supposed to contain the same items of the job. The authors suggest algorithms for three-stage flow and job shop problems. They find a minimum makespan value in \(O(\log s)\) time and optimal sublot sizes and optimal schedules in \(O(s)\) time. For open shop problems the results are as follows. If \(s\geq m\), then minimum makespan value may be found in \(O(m)\) time (it is equal to \(\max\{p_ 1,\dots, p_ m\}\)) optimal sublot sizes are \(1/m\) for \(1\leq j\leq m\) and 0 for \(m< j\leq s\), and an optimal schedule may be found in \(O(ms)\) time. For \(s= 2\) optimal sublot sizes both are 1/2, the minimum makespan value and the optimal schedule may be found in \(O(m)\) time.