Simultaneous semi-eigenvectors for matrices over an extremal algebra

The paper considers a process with n jobs which is repeated in a periodic manner. This problem can be described by a ‘simultaneous semi-eigenvector problem’: Find all feasible periods for which there exists a time schedule x fulfilling and . Let be the minimum duration of one single process during one cycle under the restriction that the complete system is operated with period . The paper shows that is a decreasing and piecewise linear function and it presents a polynomial algorithm to calculate this function explicitly.