Contributions of Inclusion-Exclusion to exact or approximate solution of scheduling problems

Apports de l’Inclusion-Exclusion à la résolution exacte ou approchée de problèmes d’ordonnancement

Olivier Ploton (1)

1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours

We study the resolution of scheduling problems by Inclusion-Exclusion. This combinatorial formula makes it possible to evaluate the number of solutions of coverage or permutation problems, and consequently to explicit optimal solutions. From a theoretical point of view, we solve to optimality and with a moderately exponential worst-case time complexity and a pseudopolynomial worst-case space complexity, any parallel machine or permutation flowshop scheduling problem, with any interval time constraint and any maximum cost or total cost regular objective. The strength of Inclusion-Exclusion is to simplify problems by relaxing their coverage constraint. We establish a link between Inclusion-Exclusion and Lagrangian penalties, and we describe a new iterative method to derive a lower bound of the optimum objective of a permutation problem, based only on the resolution of relaxed problems.

Nous étudions la résolution de problèmes d’ordonnancement par Inclusion-Exclusion. Cette formule de combinatoire permet d’évaluer le nombre de solutions de problèmes de couverture ou de permutation, et par contrecoup d’en expliciter des solutions optimales. D'un point de vue théorique, nous résolvons à l’optimalité et avec une complexité au pire cas modérément exponentielle en temps et pseudopolynomiale en espace, tout problème d’ordonnancement à machines parallèles ou d’atelier à cheminement unique, avec n’importe quelle contrainte temporelle d’intervalle et n’importe quel objectif régulier du type coût maximum ou coût total. La force de l’Inclusion-Exclusion est de simplifier des problèmes en relâchant leur contrainte de couverture. Nous établissons un lien entre Inclusion-Exclusion et pénalités Lagrangiennes, et nous décrivons une nouvelle méthode itérative pour minorer l’objectif optimum d’un problème de permutation, fondée uniquement sur la résolution de problèmes relâchés.

Mots clés: scheduling; worst case complexity; exact methods; approximation; Inclusion-Exclusion

Mots clés: ordonnancement; complexité au pire cas; méthodes exactes; approximation; Inclusion-Exclusion

Domaines: Recherche opérationnelle [math.OC]

Olivier Ploton. Contributions of Inclusion-Exclusion to exact or approximate solution of scheduling problems. Operations Research [math.OC]. Université de Tours, 2022. English. ⟨NNT : ⟩. ⟨tel-03895382⟩