Moving policies in cyclic assembly line scheduling

We consider an assembly line problem that occurs in various kinds of production automation. Our original motivation lies in the automated manufacturing of PC boards. The assembly line has to process a (potentially infinite) number of identical workpieces in a cyclic fashion. In contrast to common variants of assembly line scheduling, the forward steps are variable and may be smaller than the distance of two stations. Therefore, each station may process parts of several workpieces at the same time, and parts of a workpiece may be processed by several stations at the same time. The throughput rate is determined by the number of (cyclic) forward steps, the offsets of the individual forward steps, and the distribution of jobs over the stationary stages between the forward steps. The number of forward steps as well as the offsets are part of the output. However, no matter whether they are part of the input or the output, the optimal assignment of the jobs to the stationary stages is NP-hard.