Precedence theorems and dynamic programming ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
Auteur(s) :
Rostami, Salim [Auteur]
Lille économie management - UMR 9221 [LEM]
Creemers, Stefan [Auteur]
Lille économie management - UMR 9221 [LEM]
Leus, Roel [Auteur]
Operations Research and Business Statistics [ORSTAT]
Lille économie management - UMR 9221 [LEM]
Creemers, Stefan [Auteur]
Lille économie management - UMR 9221 [LEM]
Leus, Roel [Auteur]
Operations Research and Business Statistics [ORSTAT]
Titre de la revue :
European Journal of Operational Research
Pagination :
43 - 49
Éditeur :
Elsevier
Date de publication :
2019-01-01
ISSN :
0377-2217
Mot(s)-clé(s) en anglais :
Scheduling
Single machine
Precedence constraints
Weighted tardiness
Dynamic programming
Single machine
Precedence constraints
Weighted tardiness
Dynamic programming
Discipline(s) HAL :
Sciences de l'Homme et Société/Gestion et management
Résumé en anglais : [en]
We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory ...
Lire la suite >We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems.Lire moins >
Lire la suite >We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://lirias.kuleuven.be/retrieve/465066
- Accès libre
- Accéder au document
- https://lirias.kuleuven.be/bitstream/123456789/624896/2/PCSP-accepted.pdf
- Accès libre
- Accéder au document
- PCSP-accepted.pdf
- Accès libre
- Accéder au document