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.

, ,
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., & Zuidwijk, R. (1999). Quasicomplete factorization and the two machine flow shop problem. Linear Algebra and Its Applications, 219–15. doi:10.1016/S0024-3795(97)10082-9