Le problème de l'ordonnancement des paiements de dettes
Disjonctions dans les ordonnancements
Ordonnancements à contraintes disjonctives
Problemes d'ordonnancement à durées égales.
Dans cet article, nous étudions le problème de l'ordonnancement sur une machine de tâches de mème durées disponibles et devant être achevées à des dates différentes. Ce problème a longtemps été ouvert. Dans ce papier, nous présentons une méthode pour le résoudre. Nous montrons également déterminer un ordonnancement ayant un nombre minimal de tâches en retard. Enfin nous généralisons à plusieurs machines identiques.
Une méthode arborescente pour résoudre les problèmes cumulatifs
An exact method for solving the multi-processor flow-shop
An Exact Method for Solving the Multi-Processor Flow-Shop
The aim of this paper is to present a new branch and bound method for solving the Multi-Processor Flow-Shop. This method is based on the relaxation of the initial problem to m-machine problems corresponding to centers. Release dates and tails are associated with operations and machines. The branching scheme consists in fixing the inputs of a critical center and the lower bounds are those of the m-machine problem. Several techniques for adjusting release dates and tails have also been introduced....
Heuristic and metaheuristic methods for computing graph treewidth
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...
Heuristic and metaheuristic methods for computing graph treewidth
The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....
Page 1