The 2-machine FJSP with tooling constraints: a theoretical analysis
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)