A new graphical approach for solving single-machine scheduling problems approximately

Abstract : Often the problem of determining an optimal or approximate production schedule in a company can be reduced to the problem of solving a scheduling problem on a bottleneck machine. However, even the majority of the resulting single-machine scheduling problems are NP-hard from a computational point of view and, therefore, it is difficult to solve large instances of such problems exactly. In this paper, we consider five such single-machine problems, where a dynamic programming algorithm of pseudo-polynomial complexity exists. The running time of such an algorithm can often be improved by so-called graphical algorithms which do not need to consider all states in a dynamic programming algorithm separately. Based on such graphical algorithms, we present fully polynomial-time approximation schemes (FPTASes) for five single-machine total tardiness problems. The new FPTASes have the best running time among the known approximation schemes for these problems. The presented approach is rather general and can be applied to many other scheduling and combinatorial optimisation problems as well.
Type de document :
Article dans une revue
International Journal of Production Research, Taylor & Francis, 2014, Volume 52 (Issue 13), p. 3762-3777. 〈http://www.tandfonline.com/〉. 〈10.1080/00207543.2014.922708〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01083341
Contributeur : Florent Breuil <>
Soumis le : lundi 17 novembre 2014 - 10:25:16
Dernière modification le : mardi 23 octobre 2018 - 14:36:09

Identifiants

Citation

Evgeny R. Gafarov, Alexandre Dolgui, Frank Werner. A new graphical approach for solving single-machine scheduling problems approximately. International Journal of Production Research, Taylor & Francis, 2014, Volume 52 (Issue 13), p. 3762-3777. 〈http://www.tandfonline.com/〉. 〈10.1080/00207543.2014.922708〉. 〈emse-01083341〉

Partager

Métriques

Consultations de la notice

237