Precedence theorems and dynamic programming for the single-machine weighted tardiness problem

Salim Rostami, Stefan Creemers and Roel Leus ()
Additional contact information
Salim Rostami: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Stefan Creemers: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Roel Leus: ORSTAT - Operations Research and Business Statistics - KU Leuven - Catholic University of Leuven = Katholieke Universiteit Leuven

Post-Print from HAL

Abstract: 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.

Keywords: Scheduling; Single machine; Precedence constraints; Weighted tardiness; Dynamic programming (search for similar items in EconPapers)
Date: 2019-01-01
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Published in European Journal of Operational Research, 2019, 272 (1), pp.43 - 49. ⟨10.1016/j.ejor.2018.06.004⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-01914859

DOI: 10.1016/j.ejor.2018.06.004

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().