Quasicomplete factorization and the two machine flow shop problem
Linear Algebra and Its Applications p. 219- 15
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|
|Linear Algebra and Its Applications|
|Organisation||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