Sequencing a single machine with due dates and deadlines: an ILP-based approach

Philippe Baptiste 1 Federico Della Croce 2 Andrea Grosso 3 Vincent T'Kindt 4
1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 DAUIN - Department of Computer Engineering
3 Dipartimento di Informatica [Torino]
4 ERL CNRS 6305 Ordonnancement et Conduite
LI - T'kindt
Abstract : We consider the problem of minimizing the weighted number of tardy jobs on a single machine where each job is also subject to a deadline that cannot be vio- lated. We propose an exact method based on a compact in- teger linear programming formulation of the problem and an effective reduction procedure that allows to solve to op- timality instances with up to 30,000 jobs in size, and up to 50,000 jobs in size for the special deadline-free case
Keywords : Sequencing and scheduling Single machine Tardy jobs Deadlines
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2010, 13 (1), pp.39-47. 〈10.1007/s10951-008-0092-6〉
Liste complète des métadonnées
https://hal-univ-tours.archives-ouvertes.fr/hal-01003768
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 16:16:05
Dernière modification le : jeudi 10 mai 2018 - 02:06:15

Lien texte intégral

openaccess

Identifiants

Collections

LIX | X-LIX | X | PARISTECH | ROOT-TOURS | X-DEP-INFO

Citation

Philippe Baptiste, Federico Della Croce, Andrea Grosso, Vincent T'Kindt. Sequencing a single machine with due dates and deadlines: an ILP-based approach. Journal of Scheduling, Springer Verlag, 2010, 13 (1), pp.39-47. 〈10.1007/s10951-008-0092-6〉. 〈hal-01003768〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

123

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD