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

Salim Rostami, Stefan Creemers and Roel Leus

No 590520, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: Schrage and Baker (1978) proposed a generic dynamic programming (DP) algorithm to tackle precedenceconstrained sequencing on a single machine. The performance of their DP method, however, is limited due to excessive memory requirements, particularly when the precedence network is not very dense. Emmons (1969) and Rinnooy Kan et al. (1975) described a set of precedence theorems for sequencing jobs on a single machine in order to minimize total weighted tardiness, which were later generalized by Kanet (2007). These theorems 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 aforementioned articles. We develop a framework for applying Kanet’s theorems to the precedence-constrained problem, 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. Furthermore, we empirically verify the computational gain of using Kanet’s rather than Emmons’ theorems.

Keywords: Single-machine scheduling; Precedence constraints; Weighted tardiness; Precedence theorems; Dynamic programming (search for similar items in EconPapers)
Date: 2017-08
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1715

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/465066 Precedence theorems and dynamic programming for the single-machine weighted tardiness problem (application/pdf)

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:ete:kbiper:590520

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().