Search

We introduce a new problem, which is an extension of the classical job shop with tooling constraints. We study it from 3 different aspects: scheduling, matrix visualization and vertex ordering in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to prove several of its NP-Hard and polynomial subcases. This problem allows to find more elegant (and arguably shorter) proofs for several combinatorial problems. Including "Can a matrix can be made triangular by permuting rows and columns?", weak k-visit and a generalization of Johnson's argument for the two-machines flowshop.

This paper addresses the triangle width problem, which generalizes the classic 2-machine flexible job-shop problem (FJSP) with tooling constraints. This new problem can be studied from 3 different angles: scheduling, matrix visualization, and the order of vertices in hypergraphs. We prove the equivalence of the different formulations of the problem and use them to establish the NP-Hardness and polynomiality of several of its sub-cases. This problem allows us to find more elegant (and probably shorter) proofs for several combinatorial problems in our analysis setting. Our study provides an elegant generalization of Johnson’s argu- ment for the two-machine flow-shop. It also shows if a matrix can be triangular by permuting rows and columns and a low k -visit.