A connection is made between the Two Machine Flow Shop Problem (2MFSP) from job scheduling theory and the issue of quasicomplete factorization of rational matrix functions. A quasicomplete factorization is a factorization into elementary (i.e., degree one) factors such that the number of factors is minimal. For a companion based matrix function W, the number of factors in a quasicomplete factorization of W is related in a simple way to the minimum makespan of an instance J of 2MFSP which can be associated to W. As a consequence of this result, variants of the 2MFSP and other types of factorization can be related too.

factorization, rational matrix function, two machine flow shop problem
dx.doi.org/10.1016/S0024-3795(97)10082-9, hdl.handle.net/1765/14310
Linear Algebra and Its Applications
Erasmus School of Economics

Bart, H, Kroon, L.G, & Zuidwijk, R.A. (1999). Quasicomplete factorization and the two machine flow shop problem. Linear Algebra and Its Applications, 219–215. doi:10.1016/S0024-3795(97)10082-9