Le 25/05/2004 par FrancisSourd :
La prochaine réunion du GOThA aura lieu à Nancy (au LORIA). Il s'agit en fait de deux journées, les 10 et 11 juin, couplées avec une réunion Bermudes et le séminaire des ordonnanceurs Nancéens.
A priori, les exposés débuteront le 10 juin à 14h et se termineront le 11 juin à 16h30.
Ces journées bénéficient de la présence en France de
- Vitaly Strusevitch
- Federico della Croce
- Wieslaw Kubiak
qui chacun présenteront un exposé. Je vous invite à m'envoyer vos propositions d'exposés pour compléter ce programme.
Bien cordialement,
Francis
Le 08/06/2004 par FrancisSourd :
Voici le résumé proposé par Federico della Croce (le reste à suivre)
Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem
The weakly NP-hard single-machine total tardiness scheduling problem has been extensively studied in the last decades. Various heuristics have been proposed to efficiently solve in practice a problem for which a fully polynomial time approximation scheme exists (though with complexity O(n7/?)). In this note, we show that all known constructive heuristics for the problem, namely AU, MDD, PSK, WI, COVERT, NBR, present arbitrarily bad approximation ratios. The same behavior is shown by the decomposition heuristics DEC/EDD, DEC/MDD, DEC/PSK, and DEC/WI.
