Variants of the Two Machine Flow Shop Problem connected with factorization of matrix functions

In this paper we consider a number of variants of the Two Machine Flow Shop Problem. In these variants the makespan is given and the problem is to find a schedule that meets this makespan, thereby minimizing the infeasibilities of the jobs in a prescribed sense: in the max-variant the maximum infeasibility of the jobs is to be minimized, whereas in the sum-variant the objective is to minimize the sum of the infeasibilities of the jobs. For both variants observations about the structure of the optimal schedules are presented. In particular, it is proved that every instance of these problems has an optimal permutation schedule. It is also shown that the max-variant can be solved by Johnson's Rule. For the sum-variant this is not the case: for solving this problem to optimality something quite different is necessary. Both variants are connected with factorization problems for certain rational matrix functions. The factorizations involved are optimal in some sense and generalize the notion of complete factorization. In this way a connection is established between job scheduling theory on one hand, and mathematical systems theory on the other.