QUASICOMPLETE FACTORIZATION AND THE 2 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 factorizati on of rational matrix functions. A quasicomplete factorization is a fa ctorization into elementary (i.e., degree one) factors such that the n umber 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 whi ch can be associated to W. As a consequence of this result, variants o f the 2MFSP and other types of factorization can be related too. (C) 1 998 Published by Elsevier Science Inc. All rights reserved.