Study on partial flexible job-shop scheduling problem under tooling constraints: complexity and related problems

Étude sur le problème d'ordonnancement de job-shop flexible avec contraintes de tooling: complexité et problèmes reliés

Luc Libralesso (1) , Vincent Jost (1) , Khadija Hadj Salem , Florian Fontan (1) , Frédéric Maffray (2)

1 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
2 G-SCOP_OC - Optimisation Combinatoire

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.

Mots clés: Combinatorial Optimization; Scheduling; Graph theory; Binary matrix visualization

Domaines: Optimisation et contrôle [math.OC]

Luc Libralesso, Vincent Jost, Khadija Hadj Salem, Florian Fontan, Frédéric Maffray. Study on partial flexible job-shop scheduling problem under tooling constraints: complexity and related problems. 2019. ⟨hal-02183503⟩