FACTORIZATION AND JOB SCHEDULING - A CONNECTION VIA COMPANION BASED MATRIX FUNCTIONS

A connection is made between two sets of problems. The first set invol ves factorization problems of specific rational matrix functions, the companion based matrix functions. The second set is concerned with var iants of the two machine flow shop problem (2MFSP) from job scheduling theory. In particular, it is shown that with each companion based mat rix function one can associate an instance of 2MFSP and vice versa. Th e latter can be done in such a way that the factorization properties o f the companion based matrix function correspond to the combinatorial properties of the instance of 2MFSP.