The 2-machine FJSP with tooling constraints: a theoretical analysis - Laboratoire d'Informatique Fondamentale et Appliquée de Tours Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

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.
Fichier principal
Vignette du fichier
ANOR 2019.pdf (574.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03010258 , version 1 (17-11-2020)

Identifiants

  • HAL Id : hal-03010258 , version 1

Citer

Luc Libralesso, Vincent Jost, Khadija Hadj Salem, Florian Fontan, Frédéric Maffray. The 2-machine FJSP with tooling constraints: a theoretical analysis. 2021. ⟨hal-03010258⟩
114 Consultations
106 Téléchargements

Partager

Gmail Facebook X LinkedIn More