Quasicomplete factorization and the two machine flow shop problem
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.
|Keywords||factorization, rational matrix function, two machine flow shop problem|
|Persistent URL||dx.doi.org/10.1016/S0024-3795(97)10082-9, hdl.handle.net/1765/14310|
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