Applications of max-plus algebra to flow shop scheduling problems

In this paper we consider applications of max-plus algebra to flow shop scheduling problems. Our aim is to show that max-plus algebra is useful for flow shop scheduling. We present two new solvable conditions in m-machine permutation flow shops using max-plus algebra. One of the conditions is found by considering a max-plus algebraic analogue of a proposition in linear algebra. The other is derived using a new framework, which associates a machine with a matrix and is the dual of the max-plus approach associating a job with a matrix by Bouquard, Lenté, and Billaut (2006). The framework is the first one which can deal with non-permutation flow shop problems based on max-plus algebra. Moreover, using the framework, we provide new simple proofs of some known results.